编写C语言算法求无向图的连通分量的个数
时间: 2024-01-27 11:05:54 浏览: 35
您可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来解决这个问题。具体而言,您需要遍历整个图,对图中每个尚未被遍历的顶点执行 DFS 或 BFS。遍历操作中,您需要标记每个已经访问过的节点,并将它们放入不同的连通分量中。最后,该算法返回连通分量的个数。
以下是使用 DFS 算法求解无向图连通分量个数的 C 语言示例代码:
```c
//定义最大节点数量
#define MAX_VERTICES 100
//定义图的数据结构
typedef struct {
int count; //节点总数
int matrix[MAX_VERTICES][MAX_VERTICES]; //邻接矩阵
int visited[MAX_VERTICES]; //标记数组,用于记录已访问的顶点
} Graph;
//DFS遍历算法实现
void DFS(Graph *g, int v, int visited[]) {
visited[v] = 1; //标记该节点已被访问
int i;
for (i = 0; i < g->count; i++) {
if (g->matrix[v][i] && !visited[i]) { //如果两节点有连边,且该节点未被访问
DFS(g, i, visited); //递归遍历其相邻节点
}
}
}
//求无向图连通分量个数
int FindConnectedComponents(Graph *g) {
int i, count = 0;
int visited[MAX_VERTICES] = {0}; //初始化标记数组
for (i = 0; i < g->count; i++) { //遍历整个图
if (!visited[i]) { //如果该节点未被访问
DFS(g, i, visited); //以该节点作为起点进行 DFS 遍历
count++; //累加连通分量个数
}
}
return count;
}
```
希望这个回答可以帮助你!