Skip to content

图

Jump to bottom
suzhouzc edited this page Jul 9, 2022 · 8 revisions

  • 无向完全图的边为：n(n-1)/2

  • 极大连通子图：连通子图； 极小连通子图：生成树

  • 邻接矩阵和邻接表的对比

  • （主要）深度优先遍历

void DFSTraverse(Graph G)
{
 for (v=0 ; v < G.vexnum;++v) visited[v]=o;  //初始化辅助数组
 for (v=0 ; v< G.vexnum;++v)
  if(!visited[v]) 
   DFS(G,V);  //连通分量的个数=循环的次数
}
void DFS(Graph G,int v)
{
 visited[v]=1;
 Visit(v);  //访问顶点v
 for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
 if (!visited[w]) DFS(G,w); //访问v的邻接点
}

  • (递归)若以邻接矩阵法表示图，则DFS算法如下：

void DFS(MGraph G,int v)
{ //从v出发深度优先遍历
 visited[v];
 Visit(v);
 for(w=0;w<G.vexnum:w++)
  if(G.arcs[v][w].adj&&!visited[w])
  DFS(G,w);
}

  • （递归）若以邻接表发表示图，则DFS算法如下：

void DFS(ALGraph G,int v)
{//从v出发的深度优先遍历
 visited[v]=1; Visit(v);
 for (p=G.vertices[V].firstarc; p ;p=p->nextarc)
  if (!visited[p->adjvex])
  DFS(G,p->adjvex);
}

  • 广度优先遍历非递归遍历图G，类似于数的层次遍历

void BFSTraverse(Graph G)
{
 for (v=0;v<G.vexnum;++v) visited[v]=0;
 InitQueue(Q);
 for(v=0;v<G.vexnum:++v)
  if(！visited[v])
   {
     visited[v]=1;
     Visit(v);
     EnQueue(Q,v);
  while(!QueueEmpty=0)
  {
    DeQueue(Q,u);
    for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
     if(!visited[w])
      {visited[w]=1;Visit(w);EnQueue(Q,w); }
  }    
 }
}//BFSTraverse

  • 求顶点u到其他顶点的最短路径（广度优先算法BFS）

void BFS_MIN_Distance(Graph G,int u){
 for(i=0;i<G.vexnum;++i){
  int d[i]=⚮；   //初始化路径长度
  int path[i]=-1;  //最短路径从哪个顶点过来
 }
 d[u]=0;
 visited[u]=TRUE;
 EnQueue(Q,u);
 while(!isEmpty(Q)){
 DeQueue(Q,u);
 for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
  if(!visited[w]){  //w为u尚未访问的邻接顶点
  d[w]=d[u]+1;   //路径长度加一
  path[w]=u; //最短路径应从u到w
  visited[w]=TRUE; //设已访问标记
  EnQueue(Q,w);   //顶点w入队
  }
 }
}

  • 迪杰斯特拉算法（最短路径）

Clone this wiki locally