[已解决]非连通无向图深度优先遍历

sususususu

算法设计题：假设一个无向图是非连通的，采用邻接表作为存储结构。设计一个算法，利用深度优先遍历方法求出该图连通分量个数。（用C语言解决）

最佳答案

月排行榜 / 总排行榜

isdkz

2023-11-12 00:24:39

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define MAX_VERTEX_NUM 100
   
5. 
   
6. typedef struct ArcNode {
   
7.     int adjvex;
   
8.     struct ArcNode *next;
   
9. } ArcNode;
   
10. 
    
11. typedef struct VNode {
    
12.     int data;
    
13.     ArcNode *first;
    
14. } VNode, AdjList[MAX_VERTEX_NUM];
    
15. 
    
16. typedef struct {
    
17.     AdjList vertices;
    
18.     int vexnum, arcnum;
    
19. } ALGraph;
    
20. 
    
21. int visited[MAX_VERTEX_NUM];
    
22. 
    
23. void DFS(ALGraph G, int v) {
    
24.     visited[v] = 1;
    
25.     ArcNode *p = G.vertices[v].first;
    
26.     while (p != NULL) {
    
27.         if (!visited[p->adjvex]) {
    
28.             DFS(G, p->adjvex);
    
29.         }
    
30.         p = p->next;
    
31.     }
    
32. }
    
33. 
    
34. int CountConnectedComponents(ALGraph G) {
    
35.     int count = 0;
    
36.     for (int i = 0; i < G.vexnum; i++) {
    
37.         if (!visited[ i]) {
    
38.             count++;
    
39.             DFS(G, i);
    
40.         }
    
41.     }
    
42.     return count;
    
43. }
    
44. 
    
45. int main() {
    
46.     // 初始化图 G
    
47.     ALGraph G;
    
48.     // 调用CountConnectedComponents函数求出连通分量个数
    
49.     int result = CountConnectedComponents(G);
    
50.     printf("连通分量个数为：%d\n", result);
    
51.     return 0;
    
52. }
    

复制代码

解释：这段代码实现了利用深度优先搜索（DFS）方法求解无向图的连通分量个数。首先定义了邻接表的数据结构，然后使用DFS函数进行图的遍历，标记已访问的节点，并递归访问未访问的相邻节点。最后通过CountConnectedComponents函数统计连通分量个数并返回。在main函数中初始化图 G 并调用CountConnectedComponents函数求解连通分量个数，最终输出结果。

跳转到最佳答案楼层

isdkz

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define MAX_VERTEX_NUM 100
   
5. 
   
6. typedef struct ArcNode {
   
7.     int adjvex;
   
8.     struct ArcNode *next;
   
9. } ArcNode;
   
10. 
    
11. typedef struct VNode {
    
12.     int data;
    
13.     ArcNode *first;
    
14. } VNode, AdjList[MAX_VERTEX_NUM];
    
15. 
    
16. typedef struct {
    
17.     AdjList vertices;
    
18.     int vexnum, arcnum;
    
19. } ALGraph;
    
20. 
    
21. int visited[MAX_VERTEX_NUM];
    
22. 
    
23. void DFS(ALGraph G, int v) {
    
24.     visited[v] = 1;
    
25.     ArcNode *p = G.vertices[v].first;
    
26.     while (p != NULL) {
    
27.         if (!visited[p->adjvex]) {
    
28.             DFS(G, p->adjvex);
    
29.         }
    
30.         p = p->next;
    
31.     }
    
32. }
    
33. 
    
34. int CountConnectedComponents(ALGraph G) {
    
35.     int count = 0;
    
36.     for (int i = 0; i < G.vexnum; i++) {
    
37.         if (!visited[ i]) {
    
38.             count++;
    
39.             DFS(G, i);
    
40.         }
    
41.     }
    
42.     return count;
    
43. }
    
44. 
    
45. int main() {
    
46.     // 初始化图 G
    
47.     ALGraph G;
    
48.     // 调用CountConnectedComponents函数求出连通分量个数
    
49.     int result = CountConnectedComponents(G);
    
50.     printf("连通分量个数为：%d\n", result);
    
51.     return 0;
    
52. }
    

复制代码

解释：这段代码实现了利用深度优先搜索（DFS）方法求解无向图的连通分量个数。首先定义了邻接表的数据结构，然后使用DFS函数进行图的遍历，标记已访问的节点，并递归访问未访问的相邻节点。最后通过CountConnectedComponents函数统计连通分量个数并返回。在main函数中初始化图 G 并调用CountConnectedComponents函数求解连通分量个数，最终输出结果。