使用DFS算法判断图的连通性

使用深度优先搜索（DFS）算法可以判断图的连通性。DFS是一种遍历图的方法，从一个起始节点开始，沿着一条路径尽可能深入地访问图中的节点，直到无法继续深入为止，然后回溯到前一个节点，继续探索其他路径。

下面是使用DFS算法判断图的连通性的示例代码：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
    visited[node] = true; // 将当前节点标记为已访问

    // 遍历当前节点的邻居节点
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, visited, neighbor); // 递归地访问邻居节点
        }
    }
}

bool isGraphConnected(vector<vector<int>>& graph) {
    int n = graph.size(); // 图中节点的数量

    vector<bool> visited(n, false); // 标记节点是否已访问

    // 从第一个节点开始进行DFS
    dfs(graph, visited, 0);

    // 检查是否所有节点都被访问到
    for (bool nodeVisited : visited) {
        if (!nodeVisited) {
            return false; // 存在未被访问到的节点，图不连通
        }
    }

    return true; // 所有节点都被访问到，图连通
}

int main() {
    int n = 5; // 图中节点的数量

    vector<vector<int>> graph(n); // 用邻接表表示图

    // 添加图中的边
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[2].push_back(3);
    graph[3].push_back(2);
    graph[3].push_back(4);
    graph[4].push_back(3);

    bool isConnected = isGraphConnected(graph);

    if (isConnected) {
        cout << "The graph is connected." << endl;
    } else {
        cout << "The graph is not connected." << endl;
    }

    return 0;
}

在上面的示例代码中，我们使用邻接表来表示图，其中每个节点的邻居节点存储在一个vector中。使用一个bool类型的数组visited来标记节点是否已被访问。

首先，我们从第一个节点开始调用dfs函数进行深度优先搜索。在dfs函数中，我们首先将当前节点标记为已访问，然后遍历当前节点的邻居节点。如果邻居节点尚未访问过，则递归调用dfs函数继续访问邻居节点。这样，通过DFS算法，我们可以遍历整个图。

最后，我们检查visited数组中是否所有节点都被访问到。如果存在未被访问到的节点，则图不连通；否则，图连通。

以上是使用DFS算法判断图的连通性的示例代码。请根据自己的需求和图的表示方式进行相应的修改。