非连通无向图深度优先遍历
算法设计题：假设一个无向图是非连通的，采用邻接表作为存储结构。设计一个算法，利用深度优先遍历方法求出该图连通分量个数。（用C语言解决） #include <stdio.h>#include <stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct ArcNode {
int adjvex;
struct ArcNode *next;
} ArcNode;
typedef struct VNode {
int data;
ArcNode *first;
} VNode, AdjList;
typedef struct {
AdjList vertices;
int vexnum, arcnum;
} ALGraph;
int visited;
void DFS(ALGraph G, int v) {
visited = 1;
ArcNode *p = G.vertices.first;
while (p != NULL) {
if (!visited) {
DFS(G, p->adjvex);
}
p = p->next;
}
}
int CountConnectedComponents(ALGraph G) {
int count = 0;
for (int i = 0; i < G.vexnum; i++) {
if (!visited[ i]) {
count++;
DFS(G, i);
}
}
return count;
}
int main() {
// 初始化图 G
ALGraph G;
// 调用CountConnectedComponents函数求出连通分量个数
int result = CountConnectedComponents(G);
printf("连通分量个数为：%d\n", result);
return 0;
}
解释：这段代码实现了利用深度优先搜索（DFS）方法求解无向图的连通分量个数。首先定义了邻接表的数据结构，然后使用DFS函数进行图的遍历，标记已访问的节点，并递归访问未访问的相邻节点。最后通过CountConnectedComponents函数统计连通分量个数并返回。在main函数中初始化图 G 并调用CountConnectedComponents函数求解连通分量个数，最终输出结果。
页:
[1]