广度优先搜索

    1. bool visited[max_vertex_num];
    2. void BFSTrave(Graph G){
    3.     for(int i=0;i<G.vexnum;++i){
    4.         visited[i]=false;
    5.     }
    6.     Queue Q;
    7.     InitQueue(Q);
    8.     for(i=0;i<G.vexnum;i++){
    9.         if(!visited[i])
    10.             BFS(G,i);
    11.     }
    12. }
    14. void BFS(Graph G,int v0){
    15.     visit(v0);
    16.     visited[v0]=true;
    17.     EnQueue(Q,v0);
    18.     while(isEmpty(Q)){
    19.         DeQueue(Q,v);
    20.         for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
    21.             if(!visited[w]){
    22.                 visit[w];
    23.                 visited[w]=true;
    24.                 EnQueue(Q,w);
    25.             }
    26.         }
    27.     }
    28. }

    深度优先搜索

    1. bool visited[max_vertex_num];
    2. void DFSTrave(Graph G){
    3.     for(int i=0;i<G,vexnum;i++)
    4.         visited[i]=false;
    5.     for(int i=0;i<G.vexnum;i++){
    6.         if(!visited[i])
    7.             DFS(G,i);
    8.     }
    9. }
    10. void DFS(Graph G,int v0){
    11.     visit(v0);
    12.     visited[v0]=true;
    13.     for(w=FirstNeighbor(G,v0);w>=0;w=NextNeighbor(G,v0,w)){
    14.         if(!visited[w])
    15.             visit(w);
    16.         DFS(G,w);
    17.     }
    18. }
    20. //借助栈
    21. void DFS(Graph G,int v0){
    22.     Stack S;
    23.     InitStack(S);
    24.     for(int i=0;i<G.vexnum;i++)
    25.         visited[i]=false;
    26.     Push(S,v0);
    27.     visited[v0]=true;//用visited数组表示顶点是否在栈内
    28.     while(isEmpty(S)){
    29.         int k=Pop(S);
    30.         visit(k);
    31.         for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
    32.             if(!visited[w]){
    33.                 Push(S,w);
    34.                 visited[w]=true;
    35.             }//if
    36.         }//for
    37.     }//while
    38. }

    普利姆算法（选取权值最小边加入，直到所有顶点加入）
    执行过程：1.将v0到其它顶点的所有边当作候选边
    2.重复下面步骤n-1次，使得其它n-1个顶点被并入到生成树中
    ①从侯选边中挑选出权值最小的边输出，并将与该边另一端相接的顶点并入生成树
    ②考察所有剩余顶点vi，如果（v,vi）的权值比lowcost[vi]小，则用（v,vi）的权值更新lowcost[vi]

    1. #definr int INF 255532
    2. typedef struct{
    3.     int edges[maxsize][maxsize];
    4.     int n,e;//顶点数，边数
    5.     VertexType vex[maxtype];//存放结点信息
    6. }MGraph;
    7. void Prim(MGraph G,int v0,int &sum){
    8.     int lowcost[maxsize],vset[maxsize],v;
    9.     int i,j,k,min;
    10.     v=v0;
    11.     for(i=0;i<G.n;++i){
    12.         lowcost[i]=G.edges[v0][i];//初始化lowcost数组
    13.         vset[i]=0;//初始化结点状态数组
    14.     }
    15.     vset[0]=1;//v0并入树中
    16.     sum=0;//累计树的权值
    17.     for(i=0;i<G.n-1;++i){
    18.         min=INF;
    19.         //下面这个循环用于选出侯选边中的最小者
    20.         for(j=0;j<G.n;++j){
    21.             if(vset[j]==0&&lowcost[j]<min){
    22.                 min=lowcost[j];
    23.                 k=j;//k记录要并入结点序号
    24.             }
    25.         }
    26.         vset[k]=1;
    27.         v=k;
    28.         sum+=min;
    29.         //下面这个循环以刚并入的顶点v为媒介更新候选边
    30.         for(j=0;j<G.n;++j)
    31.             if(vset[j]==0&&G.edges[v][j]<lowcost[j])
    32.                 lowcost[j]=G.edges[v][j];//更新lowcost数组
    33.     }
    34. }

    克鲁斯卡尔算法（每次找出候选边中权值最小的边并入生成树，直到所有边都被检测完）

    1. typedef struct{
    2.     int a,b;//a和b是一条边所连的两个顶点
    3.     int w;//边的权值
    4. }Road;
    5. Road road[maxsize];
    6. int v[maxsize]//定义并查集数组
    7. int getRoot(int a){//在并查集中查找根结点的函数
    8.     while(a!=v[a])//v[a]存放的是a的根
    9.         a=v[a];
    10.     return a;
    11. }
    12. //快排
    13. int Partition(Road road[],int low,int high){
    14.     int pivot=road[low].w;
    15.     while(low<high){
    16.         while(low<high&&road[high].w>=pivot)
    17.             --high;
    18.         A[low].w=A[high].w;
    19.         while(low<high&&road[low]<=pivot)
    20.             ++low;
    21.         A[high].w=A[low].w;
    22.     }
    23.     A[low].w=pivot;
    24.     return low;
    25. }
    26. void QuickSort(Road road[],int low,int high){
    27.     if(low<high){
    28.         int pivotpos=Partition(road,low,high);
    29.         QuickSort(road,low,pivotpos-1);
    30.         QuickSore(road,pivotpos+1,high);
    31.     }
    32. }
    33. void Krusal(MGraph G,int &sum,Road road[]){
    34.     int i;
    35.     int N,E,a,b;
    36.     N=G.n;//顶点数
    37.     E=G.e;//边数
    38.     sum=0;
    39.     for(i=0;i<N;++i)
    40.         v[i]=i;
    41.     QuickSort(road,0,E-1);//对road数组中的E条边按其权值从小到大排
    42.     for(i=0;i<E;++i){
    43.         a=getRoot(road[i].a);//获取边的两个端点的根
    44.         b=getRoot(road[i].b);
    45.         if(a!=b){
    46.             v[a]=b;
    47.             sum+=road[i].w;
    48.         }
    49.     }
    50. }

    弗洛伊德算法（任意一对顶点间的最短路径）
    矩阵A记录当前已经求得任意两个顶点最短路径的长度，Path用来记录当前两顶点间最短 路径上要经过的中间顶点。

    1. void Floyd(MGraph *G,int Path[][maxsize],int A[][maxsize]){
    2.     int i,j,k;
    3.     //对两个矩阵初始化
    4.     for(i=0;i<G->n;++i){
    5.         for(j=0;j<G->n;++j){
    6.             A[i][j]=G->edges[i][j];
    7.             Path[i][j]=-1;
    8.         }
    9.     }
    10.     //下面的循环实现以k为中心点对所有顶点对(i,j)进行检测和修改
    11.     for(k=0;k<G->n;++k)
    12.         for(i=0;i<G->n;++i)
    13.             for(j=0;j<G->n;++j)
    14.                 if(A[i][j]>A[i][k]+A[k][j]){
    15.                     A[i][j]=A[i][k]+A[k][j];
    16.                     Path[i][j]=k;
    17.                 }
    18. }
    19. void printPath(int u,int v,int Path[][maxsize],int A[][maxsize]){
    20.     if(A[u][v]==INF)
    21.         printf("无最短路径！");
    22.     else{
    23.         if(Path[u][v]==-1)
    24.             printf("u->v");
    25.         else{
    26.             int mid=path[u][v];
    27.             printPath(u,mid,Path,A);//处理mid前半段路径
    28.             printPath(mid,v,Path,A);//处理mid后半段路径
    29.         }
    30.     }
    31. }

    拓扑排序
    在一个有向图中找到一个拓扑排序序列的过程如下：
    1）从有向图中选择一个没有前驱（入度为0）的顶点输出；
    2）删除1）中的顶点，并且删除从该顶点发出的全部边
    3）重复上述两步，直到剩余的图中不存在没有前驱的顶点为止

    1. typedef struct{
    2.     char data;
    3.     int count;
    4.     ArcNode *firstarc;
    5. }VNode;
    6. int TopSort(AGraph *G){
    7.     int i,j,n=0;
    8.     int stack[maxsize];//定义并初始化栈
    9.     int top=-1;
    10.     ArcNode *p;
    11.     //这个循环将图中入度为0的顶点入栈
    12.     for(i=0;i<G->n;++i){
    13.         if(G->adjList[i].count==0)
    14.             stack[++top]=i;
    15.         while(top!=-1){
    16.             i=stack[top--];//顶点出栈
    17.             ++n;//计数器加一，统计当前顶点
    18.             printf("%d",i);//输出当前顶点
    19.             p=G->adjList[i].firstarc;
    20.             //这个循环实现将所有顶点引出的边所指向的顶点的入度-1，并将在此之后入度变0的顶点入栈
    21.             while(p!=NULL){
    22.                 j=p->adjvex;
    23.                 --(G->adjList[j].count);
    24.                 if(G->adjList[i].count==0)
    25.                     stack[++top]=j;
    26.                 p=p->nextarc;
    27.             }
    28.         }
    29.         if(n==G->n)
    30.             return 1;
    31.         else
    32.             return 0;
    33.     }

    1.设计一个算法，判断一个无向图 G 是否为一棵树。若是一棵树，则算法返回 true，否则返回 false.
    一个无向图G是一棵树的条件，G 必须是无回路的连通图或有n-1 条边的连通图。 这里采用后者作为判断条件。采用深度优先遍历算法在遍历图的过程中统计可能访问到的顶点个数和边的个数，若一次遍历就能访问到 n 个顶点和 n-1 条边，则可断定，此图是一棵树，算法如下：

    1. bool isTree(Graph &G){
    2.     for(int i=0;i<G.vexnum;i++)
    3.         visited[i]=false;
    4.     int Vnum=0,Enum=0;
    5.     DFS(G,1,Vnum,Enum,visited);
    6.     if(Vnum==G.vexnum&&Enum=2*(G.vexnum-1))
    7.         return true;
    8.     else
    9.         return false;
    10. }
    11. void DFS(Graph &G,int v,int &Vnum,int &Enum,int visited[]){
    12.     //深度优先遍历
    13.     visited[v]=true;
    14.     Vnum++;
    15.     int w=FirstNeighbor(G,v);
    16.     while(w!=-1){
    17.         Enum++;
    18.         if(!visited[w])
    19.             DFS(G,w,Vnum,Enum,visited);
    20.         w=NextNeighbor(G,v,w);
    21.     }
    22. }
    1. 分别采用基于深度优先遍历和广度优先遍历算法判别以邻接表方式存储的有向图中是否存在有顶点 Vi到顶点 Vj的路径（i≠j）。
      1. bool visited[maxsize]=false;
      2. int Exit_Path_DFS(ALGraph G,int i,int j){
      3.  int w;//顶点序号
      4.  if(i==j)
      5.      return 1;
      6.  else{
      7.      visited[i]=true;
      8.      for(w=FirstNeighbor(G,i);w>=0;w=NextNeighbor(G,i,w)){
      9.          if(!visited[w]&&Exit_Path_DFS(G,w,j))
      10.              return 1;
      11.      }
      12.  }
      13.  return 0;
      14. }
      3.设计一个算法，求不带权无向连通图 G 中距离顶点 v 最远的一个顶点（所谓最远就是到大 v 的路径长度最大）
      基于图的广度优先搜索遍历方式，其体现了图中由某个顶点开始，以近向远扩展的方式遍历图中结点的过程。因此广度优先搜索遍历过程的最后一个顶点一定是距离给定顶点最远的顶点。 ```c int Maxdist(ALGraph G,int v){ ArcNode p; int Q[maxvexnum],front=rear=0; int visited[maxvexnum],i,j,k; for(i=0;ivexnum;i++)
      1.  visited[i]=0;
      Q[++rear]=v; visited[v]=1; while(front!=rear){
      1.  k=Q[++front];
      2.  p=G->adjlist[k].firstarc;
      3.  while(p!=NULL){
      4.      j=p->adjvex;
      5.      if(visited[j]==0){
      6.          visited[j]=1;
      7.          Q[++rear]=j;
      8.      }
      9.      p=p->nextarc;
      10.  }
      } return k; }
    1. 4.假设图采用邻接表存储，分别写出基于 DFS 和 BPS 遍历的算法来判别顶点 i和顶点 j (i≠j）之间是否有路径。
    2. ```c
    3. int DFSTrave(ALGraph *G,int i,int j){
    4.     int k;
    5.     for(k=0;k<G->vexnum;k++)
    6.         visited[k]=false;
    7.     DFS(G,i);
    8.     if(visited[j]==false)
    9.         return 0;
    10.     else
    11.         return 1;
    12. }
    13. int BFSTrave(ALGraph *G,int i,int j){
    14.     int k;
    15.     for(k=0;k<G.vexnum;k++)
    16.         visited[k]=false;
    17.     BFS(G,i);
    18.     if(visited[j]==false)
    19.         return 0;
    20.     else
    21.         return true;
    22. }
    23. void DFS(ALGraph G,int v0){
    24.     Stack S;
    25.     InitStack(S);
    26.     Push(S,v0);
    27.     visited[v0]=true;
    28.     while(isEmpty(S)){
    29.         int k=Pop(S);
    30.         visit(k);
    31.         for(int w=FirstNeighbor(G,v0);w>=0;w=NextNeighbor(G,v0,w)){
    32.             if(!visited[w]){
    33.                 Push(S,w);
    34.                 visited[w]=true;
    35.             }
    36.         }
    37.     }
    38. }

    5.假设图 G 采用邻接表存储，设计一个算法，判断无向图 G 是否连通。若连通则返回 1;否则返回 0。

    1. int Connect(ALGraph *G){
    2.     int flag=1;
    3.     for(int i=0;i<G->vexnum;i++)
    4.         visited[i]=false;
    5.     DFS(G,0);//BFS(G,0);
    6.     for(i=0;i<G->vexnum;i++){
    7.         if(visited[i]==false){
    8.             flag=0;
    9.             break;
    10.         }
    11.     }
    12.     return flag;
    13. }

    6.假设图 G 采用邻接表存储，设计一个算法，判断图 G 中从顶点 u 到 v 是否存在简单路径。

    1. void ExitPath(ALGraph *G,int u,int v,int &has){
    2.     int w;
    3.     ArcNode *p;
    4.     visited[u]=1;
    5.     if(u==v){
    6.         has=1;
    7.         return;
    8.     }
    9.     p=G->adjlist[u].firstarc;
    10.     while(p!=NULL){
    11.         w=p->adjvex;
    12.         if(visited[w]==0)
    13.             ExitPath(G,w,v,has);
    14.         p=p->nextarc;
    15.     }
    16. }

    7.假设图G 采用邻接表存储，设计一个算法，输出图G 中从顶点 u 到 v 的所有简单路径

    1. void FindPath(ALGraph *G,int u,int v,int path[],int d){
    2.     int w,i;
    3.     ArcNode *p;
    4.     d++;//d为走过的路径长度，初值为-1
    5.     path[d]=u;
    6.     visited[u]=1;
    7.     if(u==v){
    8.         for(int i=0;i<d;i++)
    9.             printf("%2d",path[i]);//输出路径
    10.     }
    11.     p=G->adjlist[u].firstarc;
    12.     while(p!=NULL){
    13.         w=p->adjvex;
    14.         if(!visited[w])
    15.             FindPath(G,w,v,path,d);
    16.         p=p->nextarc;
    17.     }
    18.     visited[u]=0;
    19. }

    8.假设图 G 采用邻接表存储，设计一个算法，判断无向图 G 中任意两点之间是否存在一条长度为 k 的简单路径

    1. int visitd[maxsize];
    2. int PathLenk(ALGraph *G,int i,int j,int k){
    3.     if(i==j&&k==0)
    4.         return 1;
    5.     else if(k>0){
    6.         visited[i]=true;
    7.         ArcNode *p;
    8.         for(p=G.adjlist[i].firstarc;p;p=p->nextarc){
    9.             int w=p->adjvex;
    10.             if(!visited[w]){
    11.                 if(PathLenk(G,v,j,k-1))
    12.                     return 1;
    13.             }
    14.         }
    15.         visited[i]=false;//允许曾经访问过的结点出现在另外一条路径上
    16.     }
    17.     return 0;
    18. }

    9.求AOE网的所有关键活动

    1. int CriticalPath(AGraph *G){
    2.     int i,j,k;
    3.     int ve[maxv],vl[maxv];//事件的最早发生时间和最迟发生时间
    4.     int e[maxe],l[emaxe];//活动的最早发生时间和最迟发生时间
    5.     int d[maxe];//活动的时间余量
    6.     int n=0;//活动的下标
    7.     int Topsq[maxv];//保存拓扑序列
    8.     ArcNode *p;
    9.     if(TopSort(G.Topsq)==0)//拓扑排序不成功
    10.         return 0;
    11.     printf("拓扑序列：");
    12.     for(i=0;i<G->n;i++)
    13.         printf("%d",Topsq[i]);
    14.     printf("\n");
    15.     for(i=0;i<G->n;i++)
    16.         ve[i]=0;//ve[]置初值
    17.     for(i=0;i<G->n;i++){//按拓扑序列求每个事件的最早发生时间
    18.         k=Topsq[i];//取拓扑序列中的顶点 k
    19.         p=G->adjList[k].firstarc;
    20.         while(p!=NULL){//修改顶点k的所有后继顶点的最早发生时间
    21.             j=p->adjvex;//求顶点的后继顶点
    22.             if(ve[j]<ve[k]+p->weight)
    23.                 ve[j]=ve[k]+p->weiht;
    24.             p=p->nexarc;
    25.         }
    26.     }
    27.     printf("各事件的最早发生时间：\n");
    28.     for(i=0;i<G->n;i++){
    29.         printf("ve[%-2d]=%d\t",i,ve[i]);
    30.         if((i+1)%3==0)
    31.             printf("\n");
    32.     }
    33.     printf("\n");
    34.     for(i=0;i<G->n;i++){//给每个事件最迟发生时间置初值
    35.         vl[i]=ve[G->n-1];
    36.     for(i=G->n-1;i>=0;i--){
    37.         k=Topsq[i];
    38.         p=G->adjList[k].firstarc;
    39.         while(p!=NULL){//修改顶点k所有后继顶点的最迟发生时间
    40.             j=p->adjvex;
    41.             if(vl[k]>vl[j]-p->weight)
    42.                 vl[k]=vl[j]-p->weight;
    43.             p=p->nextarc;
    44.         }
    45.     }
    46.     printf("各事件的最迟发生时间：\n");
    47.     for(i=G->n-1;i>=0;i--){
    48.         printf("vl[%-2d]=%d",i,vl[i]);
    49.         if((i+1)%3==0)
    50.             printf("\n");
    51.     }
    52.     printf("\nAOE网的关键活动为\n");
    53.     for(i=0;i<G->n;i++){
    54.         p=G->adjList[i].firstarc;
    55.         while(p!=NULL){
    56.             j=p->adjvex;
    57.             e[n]=ve[i];
    58.             l[n]=vl[i];
    59.             d[n]=e[n]-l[n];
    60.             if(d[n]==0)//输出关键活动
    61.                 printf("%d,%d",i,j);
    62.             n++;
    63.             p=p->nextarc;
    64.         }
    65.     }
    66.     printf("\n");
    67.     return 1;
    68.  }