邻接矩阵 + 深度优先遍历 + 广度优先遍历

  1 /**
  2 　　知识点：(有向图)
  3 　　　　强连通图的邻接矩阵存储图；
  4 　　　　强连通图的深度优先遍历(递归方式实现)
  5         强连通图的广度优先遍历(递归+非递归实现)
  6 */
  7 #include <stdio.h>
  8 #include <string.h>
  9 #define N 5
 10 #define ARC 100
 11 int visit[ARC],visitQ[ARC];
 12 typedef struct {
 13     char vex[ARC][N];///顶点
 14     int arc[ARC][ARC];
 15     int numv,nume;///顶点,边的个数
 16 }Graph;
 17 int getIndex(Graph& G,char s[]){
 18     for(int i = 0; i < G.numv; i++){
 19         if(strcmp(s,G.vex[i]) == 0)
 20             return i;
 21     }
 22     return -1;
 23 }
 24 void create(Graph& G){
 25     printf("请分别输入顶点和边的个数:
");
 26     scanf("%d%d",&G.numv,&G.nume);
 27     printf("输入图的顶点信息：
");
 28     for(int i = 0; i < G.numv; i++)
 29         scanf("%s",G.vex[i]);
 30     printf("请输入边的信息:
");
 31     ///初始化数组G.arc
 32     for(int i = 0; i < G.numv; i++)
 33         for(int j = 0; j < G.numv; j++)
 34             G.arc[i][j] = 0;
 35     char s[N],e[N];
 36     int i = 0,u,v;
 37     while(i < G.nume){
 38         scanf("%s%s",s,e);
 39         u = getIndex(G,s);
 40         v = getIndex(G,e);
 41         ///假设输入的起始和终止顶点都存在
 42         G.arc[u][v] = 1;
 43         i++;
 44     }
 45 }
 46 ///输出矩阵
 47 void output(Graph G){
 48     printf("    ");
 49     for(int i = 0; i < G.numv; i++)
 50         printf("%4s",G.vex[i]);
 51     printf("
");
 52     for(int i = 0; i < G.numv; i++){
 53         for(int j = -1; j < G.numv; j++){
 54             if(j == -1)
 55                 printf("%4s",G.vex[i]);
 56             else{
 57                 printf("%4d",G.arc[i][j]);
 58             }
 59         }
 60         printf("
");
 61     }
 62 }
 63 
 64 ///查找图G中位序为s的第一个邻接点
 65 int firstVex(Graph G,int s){
 66     for(int i = 0; i < G.numv; i++){
 67         if(G.arc[s][i] == 1)
 68             return i;
 69     }
 70     return -1;
 71 }
 72 ///返回顶点s的（相对于w的）下一个邻接顶点
 73 ///若w是s的最后一个邻接顶点，则返回-1
 74 int nextVex(Graph G,int s,int w){
 75     for(int i = w+1; i < G.numv; i++){
 76         if(G.arc[s][i] == 1)
 77             return i;
 78     }
 79     return -1;
 80 }
 81 ///递归法 深度优先遍历
 82 void dfs(Graph G,int s){///从位置为s的顶点开始遍历
 83     for(int w=firstVex(G,s);w!=-1;w=nextVex(G,s,w)){
 84         if(!visit[w]){
 85             printf("%4s",G.vex[w]);
 86             visit[w] = 1;
 87             dfs(G,w);
 88         }
 89     }
 90 }
 91 
 92 int r[ARC],F=0,R=0;
 93 ///递归法 广度优先遍历
 94 void bfs(Graph G,int s){
 95     ///判断根节点是否已经遍历
 96     if(!visitQ[s]){
 97         printf("%4s",G.vex[s]);
 98         visitQ[s] = 1;
 99     }
100     ///遍历根节点s的邻接点
101 
102     for(int i = 0; i < G.numv; i++){
103         if(!visitQ[i] && G.arc[s][i]){
104             printf("%4s",G.vex[i]);
105             visitQ[i] = 1;
106             r[R++] = i;
107         }
108     }
109     ///递归遍历s的邻接点
110     if(F<R) bfs(G,r[F++]);
111 }
112 
113 ///广度优先遍历(非递归)
114 int q[2*ARC],Fq=0,Rq=0;
115 int visit_q[2*ARC];
116 void bfs_ND(Graph G,int s){
117     int node;
118     q[Rq++] = s;
119     while(Fq < Rq){
120         node = q[Fq++];
121         if(!visit_q[node]){
122             printf("%4s",G.vex[node]);
123             visit_q[node] = 1;
124             ///将顶点node的邻接点入队列
125             for(int i = 0; i < G.numv; i++){
126                 if(!visit_q[i] && G.arc[node][i])
127                     q[Rq++] = i;
128             }
129         }
130     }
131 }
132 
133 int main(void){
134     Graph G;
135     create(G);
136     output(G);
137     printf("请输入遍历的起始顶点:
");
138     char s[N];
139     scanf("%s",s);
140     for(int i = 0; i < G.numv; i++)
141         visit[i] = visit_q[i] = 0;
142     printf("递归 深度优先遍历:
");
143     printf("%4s",s); visit[getIndex(G,s)] = 1;
144     dfs(G,getIndex(G,s));
145     printf("
递归 广度优先遍历:
");
146     bfs(G,getIndex(G,s)); printf("
");
147     printf("非递归 广度优先遍历:
");
148     bfs_ND(G,getIndex(G,s)); printf("
");
149     return 0;
150 }
测试数据：
8 9
v1 v2 v3 v4 v5 v6 v7 v8
v1 v2
v1 v3
v2 v4
v2 v5
v3 v6
v3 v7
v4 v8
v5 v8
v7 v6
v1