无向图，邻接矩阵结构

1. /*  
2.                     图  
3. 采用邻接矩阵存储  
4. DFS采用递归方案  
5. By______H4-breeze[在等带mm来自习的时候]  
6. Apr.28th.2012  
7. */ 
8.  
9. #include<iostream>  
10. using namespace std;  
11.  
12. #define VertexNum 10        //定义顶点数量最多10个，#define不带分号  
13.  
14. //图的相关数据结构  
15. typedef struct{                              //图的数据结构：顶点数据+边数据+顶点数+边数  
16.     char vexs[VertexNum]; //顶点表  
17.     int  edges[VertexNum][VertexNum];  
18.     int v,e;                               //顶点数+边数  
19. }Graph;  
20.  
21. //定义队列数据结构，在BFS时用到  
22. typedef struct qNode{  
23.     int front;  
24.     int rear;  
25.     int count;  
26.     int p[VertexNum];  
27. }queue;  
28.  
29. //全局变量，存放访问信息  
30. int visited[VertexNum];  
31.  
32. void CreatGraph(Graph *G);          //创建一个图  
33. void FS(Graph *G,int choice);       //对图G实行深度优先遍历，choice为选择遍历方式  
34. void dfs(Graph *G,int i);          //对图G从顶点i出发实行DFS遍历的具体算法，采用递归方案  
35. void bfs(Graph *G,int i);          //对图G从顶点i出发实行BFS遍历的具体算法，采用队列方案  
36.  
37. //主函数体  
38. int main(void)  
39. {  
40.     Graph *graph;  
41.     graph = (Graph *)malloc(sizeof(Graph));  
42.     CreatGraph(graph);  
43.     cout << "----DFS----" << endl;  
44.     FS(graph,0);  
45.     cout << "----BFS----" << endl;  
46.     FS(graph,1);  
47.     return 0;  
48. }  
49.  
50. //创建图  
51. void CreatGraph(Graph *G)  
52. {  
53.     int i,j,k;  
54.     cout << "Input number of vertex and number of edges" << endl;  
55.     cin >> G->v >> G->e;  
56.     cout << "Input data of vertex" << endl;  
57.     for(i = 0;i < G->v; i++)  
58.     {  
59.         cin >> G->vexs[i];  
60.     }  
61.     for(i = 0; i < G->v; i++)  
62.         for(j = 0;j < G->v; j++)  
63.         {  
64.             G->edges[i][j] = 0;              //初始化为独立顶点  
65.         }  
66.     cout << "Input information of edges.e.g:input 1 and 2 represents vertex 1 connects with 2" << endl;  
67.     for(k = 0; k < G->v; k++)  
68.     {  
69.         cin >> i >> j;  
70.         G->edges[i-1][j-1]=1;          //设定各个顶点间的链接情况：1为相连；0为断开  
71.     }  
72. }  
73.  
74. //遍历初始化即方案选择  
75. void FS(Graph *G,int choice)                 //从图G的顶点i开始DFS  
76. {  
77.     int i = 0;  
78.     for(i = 0;i < G->v; i++)  
79.         visited[i] = 0;             //初始化所有顶点都没有被访问  
80.             switch(choice)  
81.             {  
82.                 case 0:  
83.                     for(i = 0;i < G->v; i++)  
84.                         dfs(G,i);                 //从第一个顶点开始访问  
85.                     break;  
86.                 case 1:  
87.                     for(i = 0;i < G->v; i++)  
88.                         bfs(G,i);  
89.                     break;  
90.             }  
91. }  
92.  
93. //DFS遍历具体实现算法，递归方案  
94. void dfs(Graph *G,int i)  
95. {  
96.     if(visited[i] == 0)  
97.     {  
98.         cout << "Vertex " << i+1 << " has been visited!" << endl;  
99.         visited[i] = 1;  
100.         for(int j = 0;j < G->v; j++)  
101.         {  
102.             if(G->edges[i][j] != 0 && visited[j] == 0)  
103.                 dfs(G,j);         //递归从与顶点i有连接的且尚未被访问的顶点j开始访问  
104.         }     
105.     }  
106. }  
107.  
108. //BFS遍历具体算法，队列方案  
109. void bfs(Graph *G,int i)  
110. {     
111.     int j,k;  
112.     queue *q=(queue *)malloc(sizeof(queue));   //新建一个队列  
113.     q->front = q->rear = q->count = 0;         //空队列  
114.     //把当前正在访问的顶点进队，以后会从这个顶点出发遍历他的还没有被访问的邻顶点  
115.           
116.     visited[i] = 1;  
117.     cout << "Vertex " << i+1 << " has been visited!" << endl;  
118.     q->p[q->rear] = i;                          //  
119.     q->rear++;  
120.     q->count++;              //进队  rear永远指向对尾，front永远指向对头  
121.  
122.     while(q->count > 0)      //最好不要用q->count != 0。因为可能为负数，循环有问题  
123.     {  
124.         j = q->p[q->front];  
125.         q->front++;  
126.         q->count--;                  //出队  
127.         if(visited[j] == 0)  
128.         {  
129.             for(k = 0; k < G->v; k++)  
130.             {  
131.                 if(G->edges[j][k] != 0 && visited[k] == 0)   //边存在且尚未被访问  
132.                 {  
133.                     cout << "Vertex " << k+1 << " has been visited!" << endl;  
134.                     visited[k] = 1;  
135.  
136.                     q->p[q->rear] = k;  
137.                     q->rear++;  
138.                     q->count++;          //入队  
139.                 }  
140.             }  
141.         }  
142.     }  
143. }