数据结构【图】—022邻接矩阵的深度和广度遍历

  1 #include "000库函数.h"
  2 //无向图
  3 
  4 typedef char VertexType; /* 顶点类型应由用户定义 */
  5 typedef int EdgeType; /* 边上的权值类型应由用户定义 */
  6 
  7 #define MAXSIZE 9 /* 存储空间初始分配量 */
  8 #define MAXEDGE 15
  9 #define MAXVEX 9
 10 #define INFINITY 65535
 11 
 12 struct MGraph {//临接矩阵参数
 13     VertexType vexs[MAXVEX];
 14     EdgeType arc[MAXVEX][MAXVEX];
 15     int numVertexes, numEdges;
 16 };
 17 
 18 struct Queue {//遍历表
 19     char data;//标号
 20     Queue *front;//头
 21     Queue *rear;//尾
 22 };
 23 //queue链表的初始化
 24 void InitQueue(Queue **q) {
 25     (*q) = new Queue;
 26     (*q)->data = 0;
 27     (*q)->front = NULL;
 28     (*q)->rear = NULL;
 29 }
 30 
 31 void CreateMGraph(MGraph **G) {
 32     (*G) = new MGraph;
 33     (*G)->numEdges = 15;
 34     (*G)->numVertexes = 9;
 35     /* 读入顶点信息，建立顶点表 */
 36     (*G)->vexs[0] = 'A';
 37     (*G)->vexs[1] = 'B';
 38     (*G)->vexs[2] = 'C';
 39     (*G)->vexs[3] = 'D';
 40     (*G)->vexs[4] = 'E';
 41     (*G)->vexs[5] = 'F';
 42     (*G)->vexs[6] = 'G';
 43     (*G)->vexs[7] = 'H';
 44     (*G)->vexs[8] = 'I';
 45 
 46 
 47     for (int i = 0; i < (*G)->numVertexes; ++i)/* 初始化图 */
 48     {
 49         for (int j = 0; j < (*G)->numVertexes; ++j)
 50         {
 51             (*G)->arc[i][j] = 0;
 52         }
 53     }
 54 
 55     (*G)->arc[0][1] = 1;
 56     (*G)->arc[0][5] = 1;
 57  
 58     (*G)->arc[1][2] = 1;
 59     (*G)->arc[1][8] = 1;
 60     (*G)->arc[1][6] = 1;
 61  
 62     (*G)->arc[2][3] = 1;
 63     (*G)->arc[2][8] = 1;
 64  
 65     (*G)->arc[3][4] = 1;
 66     (*G)->arc[3][7] = 1;
 67     (*G)->arc[3][6] = 1;
 68     (*G)->arc[3][8] = 1;
 69  
 70     (*G)->arc[4][5] = 1;
 71     (*G)->arc[4][7] = 1;
 72  
 73     (*G)->arc[5][6] = 1;
 74  
 75     (*G)->arc[6][7] = 1;
 76 
 77 
 78     for (int i = 0; i < (*G)->numVertexes; ++i)/* 初始化图 */
 79     {
 80         for (int j = 0; j < (*G)->numVertexes; ++j)
 81         {
 82             (*G)->arc[j][i] = (*G)->arc[i][j];
 83         }
 84     }
 85 
 86 }
 87 
 88 Queue *q;//用来存储路径
 89 vector<bool>a(MAXVEX, true);//访问标志
 90 void DFS(MGraph *G, int pot) {
 91     a[pot] = false;//已经访问过
 92     Queue *p;
 93     InitQueue(&p);
 94     p->data = G->vexs[pot];
 95     q->rear = p;
 96     p->front = q;
 97     q = p;
 98     for (int i = 0; i < G->numVertexes; ++i) {
 99         if (G->arc[pot][i] && a[i]) {//有路
100             DFS(G, i);//递归遍历,编历到B,就到B中找可行路径，A中其他的可行路径以后再遍历
101         }
102     }
103 }
104 
105 void DFSTraverse(MGraph *G) {//深度遍历
106     InitQueue(&q);
107     Queue *head = q;
108     for (int i = 0; i < G->numVertexes; ++i) {
109         if (a[i])//未访问过
110             DFS(G, i);//进入回溯
111     }
112     Queue *p = head->rear;
113     while (p) {
114         cout << p->data << "  ";
115         p = p->rear;
116     }
117     cout << endl;
118     
119     
120 }
121 
122 
123 vector<char> bf;
124 vector<bool>b(MAXVEX, true);//访问标志
125 deque<int>s;
126 void BFS(MGraph *G, int pot) {
127     s.pop_front();//出栈
128     bf.push_back(G->vexs[pot]);
129     if (bf.size() >= G->numVertexes)return;
130     for (int j = 0; j < G->numVertexes; ++j) {
131         if (G->arc[pot][j] && b[j]) {
132             b[j] = false;//遍历过
133             s.push_back(j);
134         }            
135     }
136     BFS(G, s.front());    
137 }
138 
139 void BFSTraverse(MGraph *G) {
140     for (int i = 0; i < G->numVertexes; ++i) {
141         if (b[i]) {
142             s.push_back(i);
143             b[i] = false;//遍历过
144             BFS(G, s.front());
145         }
146     }
147     for (auto f : bf)
148         cout << f << "  ";
149     cout << endl;
150 }
151 int T022(void)
152 {
153     MGraph *G;
154     CreateMGraph(&G);
155     //printf("
深度遍历：");
156     //DFSTraverse(G);
157     printf("
广度遍历：");
158     BFSTraverse(G);
159     return 0;
160 }