概述
- 从图中某一顶点出发遍历图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历。
深度优先遍历
- 也叫深度优先搜索，简称DFS。
- 对于连通图，从图中某个顶点v出发，访问此顶点，然后从顶点v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。
- 对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// 邻接矩阵的方式 typedef int Boolean; Boolean visited[MAX]; void DFS(MGraph G, int i) { int j; visited[i] = TRUE; printf("%c", G.vexs[i]); for (j = 0; j < G.numVertexes; j++) { if (G.arc[i][j] == 1 && !visited[j]) { DFS(G, j); } } } // 邻接矩阵深度遍历 void DFSTraverse(MGraph G) { int i; for (i = 0; i < G.numVertexes; i++) { visited[i] = FALSE; } for (i = 0; i < G.numVertexes; i++) { if (!visited[i]) { DFS(G, i); } } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// 邻接表结构 void DFS(GraphAdjList GL, int i) { EdgeNode* p; printf("%c", GL->adjList[i].data); p = GL->adjList[i].firstedge; while(p) { if (!visited[p->adjvex]) { DFS(GL, p->adjvex); } p = p->next; } } void DFSTraverse(GraphAdjList GL) { int i; for (i = 0; i < GL->numVertexes; i++) { visited[i] = FALSE; } for (i = 0; i < GL->numVertexes; i++) { if (!visited[i]) { DFS(GL, i); } } } |
广度优先遍历
- 又叫广度优先搜索，简称BFS。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// 邻接矩阵广度遍历算法 void BFSTraverse(MGraph G) { int i, j; Queue Q; for (i = 0; i < G.numVertexes; i++) { visited[i] = FALSE; } InitQueue(&Q); for (i = 0; i < G.numVertexes; i++) { if (!visited[i]) { visited[i] = TRUE; printf("%c ", G.vexs[i]); EnQueue(&Q, i); while(!QueueEmpty(Q)) { DeQueue(&Q, &i); for (j = 0; j < G.numVertexes; j++) { if (G.arc[i][j] == 1 && !visited[j]) { visited[j] = TRUE; printf("%c ", G.vexs[j]); EnQueue(&Q, j); } } } } } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// 邻接表广度遍历算法 void BFSTraverse(GraphAdjList GL) { int i; EdgeNode* p; Queue Q; for (i = 0; i < GL->numVertexes; i++) { visited[i] = FALSE; } InitQueue(&Q); for (i = 0; i < GL->numVertexes; i++) { if (!visited[i]) { visited[i] = TRUE; printf("%c ",GL->adjList[i].data); Enqueue(&Q, i); while(!QueueEmpty(Q)) { DeQueue(&Q, &i); p = GL->adjList[i].firstedge; while(p) { if (!visited[p->adjvex]) { visited[p->adjvex] = TRUE; printf("%c ", GL->adjList[p->adjvex].data); EnQueue(&Q, p->adjvex); } p = p->next; } } } } } |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ 大话数据结构_二叉树_结构&&遍历&&推导11/03
- ♥ Dump分析：空指针访问二，重复释放堆内存二03/30
- ♥ 狄克斯特拉算法06/29
- ♥ 大话数据结构_赫夫曼树与应用01/11
- ♥ Skia总结概述11/15
- ♥ 大话数据结构_二叉树11/03