c语言如何判断图是否连通
时间: 2023-08-10 13:02:09 浏览: 46
在C语言中,判断图是否连通可以使用深度优先搜索(DFS)或广度优先搜索(BFS)算法来实现。下面是DFS算法的示例代码:
```c
#include <stdio.h>
#include <stdbool.h>
#define N 100 // 图的最大顶点数
bool visited[N]; // 记录顶点是否被访问过
int graph[N][N]; // 存储图的邻接矩阵
int n; // 图的顶点数
void dfs(int u)
{
visited[u] = true; // 标记当前顶点已访问
for (int v = 0; v < n; v++)
{
if (graph[u][v] && !visited[v]) // 如果v与u相邻且未被访问过
{
dfs(v); // 继续访问v的邻接顶点
}
}
}
bool is_connected()
{
for (int i = 0; i < n; i++)
{
visited[i] = false; // 初始化visited数组
for (int j = 0; j < n; j++)
{
scanf("%d", &graph[i][j]); // 输入邻接矩阵
}
}
dfs(0); // 从第一个顶点开始进行深度优先搜索
for (int i = 0; i < n; i++)
{
if (!visited[i]) // 如果有顶点未被访问到,则图不连通
{
return false;
}
}
return true;
}
int main()
{
printf("请输入图的顶点数:");
scanf("%d", &n);
printf("请输入邻接矩阵(0表示不连通,1表示连通):\n");
if (is_connected())
{
printf("该图是连通图。\n");
}
else
{
printf("该图不是连通图。\n");
}
return 0;
}
```
这里使用了邻接矩阵来表示图,如果图是连通的话,那么从任意一个顶点开始进行DFS遍历,最终所有的顶点都会被访问到。如果存在未被访问到的顶点,那么说明图不连通。