用C语言写一个函数,输入一个无向图的二维数组和数组的行列数,判断这个图是否是全连通
时间: 2024-02-18 21:04:32 浏览: 67
好的,我来回答你的问题。以下是用C语言实现判断无向图是否全连通的函数:
```c
#include <stdio.h>
#include <stdbool.h>
void dfs(int graph[][10], int n, bool visited[], int vertex) {
visited[vertex] = true;
for(int i = 0; i < n; i++) {
if(graph[vertex][i] == 1 && !visited[i]) {
dfs(graph, n, visited, i);
}
}
}
bool isFullyConnected(int graph[][10], int n) {
bool visited[n];
for(int i = 0; i < n; i++) {
visited[i] = false;
}
dfs(graph, n, visited, 0);
for(int i = 0; i < n; i++) {
if(!visited[i]) {
return false;
}
}
return true;
}
int main() {
int graph[10][10] = {{0, 1, 1, 0, 0},
{1, 0, 1, 1, 0},
{1, 1, 0, 1, 0},
{0, 1, 1, 0, 1},
{0, 0, 0, 1, 0}};
if(isFullyConnected(graph, 5)) {
printf("The graph is fully connected.\n");
} else {
printf("The graph is not fully connected.\n");
}
return 0;
}
```
这里假设输入的二维数组的最大行列数为10。函数isFullyConnected的实现是通过深度优先搜索算法来判断图是否是全连通的。首先,我们初始化一个bool类型的visited数组,表示每个顶点是否被访问过。然后,我们从第一个顶点开始,对于每个未被访问过的邻接顶点,递归地进行深度优先搜索,将visited数组中对应的顶点标记为已访问。最后,我们检查visited数组中是否所有顶点都被访问过,如果是,则图是全连通的,否则不是。在这个例子中,我们假设输入的图是一个5个顶点的无向图,用一个10x10的二维数组表示,其中1表示两个顶点有边相连,0表示没有边相连。
阅读全文