判断图是否连通 c语言代码实现
时间: 2023-10-07 15:05:05 浏览: 43
以下是使用深度优先搜索(DFS)实现的判断图是否连通的C语言代码:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
bool visited[MAX_VERTICES]; // 标记节点是否被访问过
// 邻接矩阵存储图
int graph[MAX_VERTICES][MAX_VERTICES];
// 深度优先搜索函数
void dfs(int v, int n) {
visited[v] = true;
for (int i = 0; i < n; i++) {
if (graph[v][i] == 1 && !visited[i]) {
dfs(i, n);
}
}
}
// 判断图是否连通
bool is_connected(int n) {
// 初始化visited数组
for (int i = 0; i < n; i++) {
visited[i] = false;
}
// 从第一个节点开始遍历
dfs(0, n);
// 如果所有节点都被访问过,则图是连通的
for (int i = 0; i < n; i++) {
if (!visited[i]) {
return false;
}
}
return true;
}
int main() {
int n; // 节点数
scanf("%d", &n);
// 输入邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
// 判断图是否连通
if (is_connected(n)) {
printf("The graph is connected.\n");
} else {
printf("The graph is not connected.\n");
}
return 0;
}
```
该代码先定义了一个visited数组,用于标记节点是否被访问过。然后定义了一个dfs函数,用于进行深度优先搜索。最后使用is_connected函数判断图是否连通。