图

• 无向完全图的边为：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入队
  }
 }
}

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

Dijkstra算法不适合用于有负权值的带权图（跑毒、中途加电）

• 弗洛伊德算法（Floyd算法最短路径–动态规划思想）可解决负权值的问题

//--初始化矩阵A和path
for (int k=0;k<n;k++){ //考虑以vk作为中转点
 for (int i=0;i<n;i++){  --遍历整个矩阵，i为行号，j为列号
  for(int j=0;j<n;j++){
    if(A[i][j]>A[i][k]+A[k][j])  //以vk为中转点的路径更短
       A[i][j]=A[i][k]+A[k][j];  //更新最短路径长度
        path[i][j]=k;            //中转点  
   }
 }
}