图的遍历及连通性 用c语言怎么做啊

5.图的遍历及连通性A
【问题描述】
根据输入的图的邻接矩阵A，判断此图的连通性。
【输入形式】
第一行为图的结点个数n，之后的n行为邻接矩阵的内容，每行n个数表示。其中A[i][j]=1表示两个结点邻接，而A[i][j]=0表示两个结点无邻接关系。
【输出形式】
输出此图连通性，若是连通图输出YES，否则输出NO。
【样例输入】
5
0 1 1 00
1 0100
1 1 000
00001
0001 0
【样例输出】
NO

这是一个图的遍历及连通性问题。我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历整个图，查看是否存在未访问到的结点。如果存在未访问到的结点，则说明该图不连通。

下面是基于DFS实现的代码示例：

#include <stdio.h>
#define MAXN 100

int A[MAXN][MAXN]; // 存储邻接矩阵
int visited[MAXN]; // 记录结点是否已经被访问

// 参数n为结点总数，u为当前遍历到的结点
void dfs(int n, int u) {
    visited[u] = 1; // 标记结点u已经被访问过了
    for (int v = 0; v < n; v++) {
        if (A[u][v] == 1 && visited[v] == 0) { // 如果u和v有边相连并且v未被访问过
            dfs(n, v); // 递归访问结点v
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);

    // 读入邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &A[i][j]);
        }
    }

    // 访问结点0，查看整个图的连通性
    dfs(n, 0);

    // 判断是否存在未被访问的结点
    int flag = 1;
    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) {
            flag = 0;
            break;
        }
    }

    if (flag) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }

    return 0;
}

该程序从结点0开始遍历整个图，标记已经被访问到的结点。遍历结束后，判断是否存在未被标记的结点即可得出结论。

时间复杂度：该算法的时间复杂度为 $O(n^2)$，其中n为结点总数，因为需要遍历整个邻接矩阵。