图的广度优先搜索代码

我叫淳子

跟深度优先还是一样，这两个是我在做数据结构作业花大量时间去找的代码，就是老师的要求肯定百度是无法直接满足的，就必须通过各个网站的不同功能的代码综合在一起，然后组成的的代码。有错误的话欢迎大神们来纠正。

1. #include <stdio.h>  
   
2. #include <stdlib.h>
   
3. 
   
4. 
   
5. typedef char VertexType;                //顶点类型应由用户定义
   
6. typedef int EdgeType;                   //边上的权值类型应由用户定义
   
7. 
   
8. #define MAXVEX  100             //最大顶点数，应由用户定义
   
9. #define INFINITY  0                //用0来代表无穷大
   
10. #define DEBUG
    
11. int visit[100] = {};
    
12. typedef struct
    
13. {
    
14.     VertexType vexs[MAXVEX];            //顶点表
    
15.     EdgeType   arc[MAXVEX][MAXVEX];         //邻接矩阵，可看作边
    
16.     int numVertexes, numEdges;      //图中当前的顶点数和边数
    
17. }Graph;
    
18. int locates(Graph *g, char ch)
    
19. {
    
20.     int i = 0;
    
21.     for(i = 0; i < g->numVertexes; i++)
    
22.     {
    
23.         if(g->vexs[i] == ch)
    
24.         {
    
25.             break;
    
26.         }
    
27.     }
    
28.     if(i >= g->numVertexes)
    
29.     {
    
30.         return -1;
    
31.     }
    
32.      
    
33.     return i;
    
34. }
    
35. void CreateGraph(Graph *g)
    
36. {
    
37.     int i, j, k, w;
    
38.     printf("输入顶点数和边数:\n");
    
39.     scanf("%d,%d", &(g->numVertexes), &(g->numEdges));
    
40.      
    
41.     #ifdef DEBUG
    
42.     printf("%d %d\n", g->numVertexes, g->numEdges);
    
43.     #endif
    
44.     printf("输入节点编号:\n");
    
45.     for(i = 0; i < g->numVertexes; i++)
    
46.     {
    
47.         g->vexs[i] = getchar();
    
48.         while(g->vexs[i] == '\n')
    
49.         {
    
50.             g->vexs[i] = getchar();
    
51.         }
    
52.     }
    
53.      
    
54.     #ifdef DEBUG
    
55.     for(i = 0; i < g->numVertexes; i++)
    
56.     {
    
57.            
    
58.         printf("%c ", g->vexs[i]);
    
59.     }
    
60.     printf("\n");
    
61.     #endif
    
62. 
    
63.    
    
64.     for(i = 0; i < g->numEdges; i++)
    
65.     {
    
66.         for(j = 0; j < g->numEdges; j++)
    
67.         {
    
68.             g->arc[i][j] = INFINITY; //邻接矩阵初始化
    
69.         }
    
70.     }
    
71.     for(k = 0; k < g->numEdges; k++)
    
72.     {
    
73.         char p, q;
    
74.         printf("输入边(vi,vj)上的下标i，下标j和权值:\n");
    
75.          
    
76.         p = getchar();
    
77.         while(p == '\n')
    
78.         {
    
79.             p = getchar();
    
80.         }
    
81.         q = getchar();
    
82.         while(q == '\n')
    
83.         {
    
84.             q = getchar();
    
85.         }
    
86.         scanf("%d", &w);   
    
87.          
    
88.         int m = -1;
    
89.         int n = -1;
    
90.         m = locates(g, p);
    
91.         n = locates(g, q);
    
92.         if(n == -1 || m == -1)
    
93.         {
    
94.             fprintf(stderr, "there is no this vertex.\n");
    
95.             return;
    
96.         }
    
97.         //getchar();
    
98.         g->arc[m][n] = w;
    
99.         g->arc[n][m] = g->arc[m][n];  //因为是无向图，矩阵对称
    
100.     }
     
101. }
     
102. void bfs(Graph *g)  
     
103. {  
     
104.     int i, j;  
     
105.     int x;  
     
106.     printf("遍历的节点次序为：") ;
     
107.     for (i = 0; i < g->numVertexes; i++)
     
108.         {  
     
109.         if (visit[i] != 1)
     
110.                 {  
     
111.             visit[i] = 1;  
     
112.             printf("%3c", g->vexs[i]);  
     
113.   
     
114.            
     
115.         }  
     
116.     }  
     
117. }  
     
118. void printGraph(Graph g)
     
119. {
     
120.     int i, j;
     
121.     for(i = 0; i < g.numVertexes; i++)
     
122.     {
     
123.         for(j = 0; j < g.numVertexes; j++)
     
124.         {
     
125.             printf("%d  ", g.arc[i][j]);
     
126.         }
     
127.         printf("\n");
     
128.     }
     
129. }
     
130.   
     
131. int main()  
     
132. {  
     
133.     Graph g;
     
134.    
     
135.     CreateGraph(&g);
     
136.     printGraph(g);
     
137.         bfs(&g);  
     
138.     printf("\n");  
     
139.     printf("0代表无穷大");
     
140.     return 0;  
     
141. }  

复制代码

～风介～

表示数据结构没学好啊~

我叫淳子

～风介～ 发表于 2015-12-31 00:05
表示数据结构没学好啊~

我也没学好。。。不然就自己写了。。不用去网上找。。。我现在在恶补小甲鱼的数据结构和算法。

～风介～

我叫淳子 发表于 2015-12-31 10:35
我也没学好。。。不然就自己写了。。不用去网上找。。。我现在在恶补小甲鱼的数据结构和算法。

我是学着学着就忘了~

lewisyixin

感谢分享