c++如何验证图的连通性？

使用深度优先搜索（DFS）或广度优先搜索（BFS）算法可以验证图的连通性。以下是使用深度优先搜索的方法：

#include <iostream>
#include <vector>
#include <list>

class Graph {
    int vertices;
    std::vector<std::list<int>> adjList;

public:
    Graph(int v) : vertices(v), adjList(v) {}

    void addEdge(int v, int w) {
        adjList[v].push_back(w);
        adjList[w].push_back(v);
    }

    void DFSUtil(int v, std::vector<bool>& visited) {
        visited[v] = true;

        for (const auto& neighbor : adjList[v]) {
            if (!visited[neighbor]) {
                DFSUtil(neighbor, visited);
            }
        }
    }

    bool isConnected() {
        std::vector<bool> visited(vertices, false);

        // Find the first non-zero degree vertex
        int i;
        for (i = 0; i < vertices; ++i) {
            if (!adjList[i].empty()) {
                break;
            }
        }

        // If there are no edges in the graph, it's connected
        if (i == vertices) {
            return true;
        }

        // Start DFS traversal from the first non-zero degree vertex
        DFSUtil(i, visited);

        // Check if all vertices with non-zero degree are visited
        for (i = 0; i < vertices; ++i) {
            if (!adjList[i].empty() && !visited[i]) {
                return false;
            }
        }

        return true;
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);

    if (g.isConnected()) {
        std::cout << "The graph is connected.\\n";
    } else {
        std::cout << "The graph is not connected.\\n";
    }

    return 0;
}

这个程序创建了一个图类（Graph），其中包含了图的邻接表表示法。通过深度优先搜索（DFS）来检查图是否是连通的。如果图是连通的，isConnected 函数返回 true，否则返回 false。

class Graph {
    int vertices;
    int** adjMatrix;

public:
    Graph(int v) : vertices(v) {
        adjMatrix = new int*[vertices];
        for (int i = 0; i < vertices; ++i) {
            adjMatrix[i] = new int[vertices];
            for (int j = 0; j < vertices; ++j) {
                adjMatrix[i][j] = 0;
            }
        }
    }

    void addEdge(int v, int w) {
        adjMatrix[v][w] = 1;
        adjMatrix[w][v] = 1;
    }

    void DFSUtil(int v, bool* visited) {
        visited[v] = true;

        for (int i = 0; i < vertices; ++i) {
            if (adjMatrix[v][i] && !visited[i]) {
                DFSUtil(i, visited);
            }
        }
    }

    bool isConnected() {
        bool* visited = new bool[vertices];
        for (int i = 0; i < vertices; ++i) {
            visited[i] = false;
        }

        // Find the first non-zero degree vertex
        int i;
        for (i = 0; i < vertices; ++i) {
            bool hasEdge = false;
            for (int j = 0; j < vertices; ++j) {
                if (adjMatrix[i][j] != 0) {
                    hasEdge = true;
                    break;
                }
            }
            if (hasEdge) {
                break;
            }
        }

        // If there are no edges in the graph, it's connected
        if (i == vertices) {
            delete[] visited;
            return true;
        }

        // Start DFS traversal from the first non-zero degree vertex
        DFSUtil(i, visited);

        // Check if all vertices with non-zero degree are visited
        for (i = 0; i < vertices; ++i) {
            bool hasEdge = false;
            for (int j = 0; j < vertices; ++j) {
                if (adjMatrix[i][j] != 0) {
                    hasEdge = true;
                    break;
                }
            }
            if (hasEdge && !visited[i]) {
                delete[] visited;
                return false;
            }
        }

        delete[] visited;
        return true;
    }

    ~Graph() {
        for (int i = 0; i < vertices; ++i) {
            delete[] adjMatrix[i];
        }
        delete[] adjMatrix;
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);

    if (g.isConnected()) {
        // The graph is connected.
    } else {
        // The graph is not connected.
    }

    return 0;
}

#include <iostream>

#define MAX 100

int adjMatrix[MAX][MAX];
int vertices;

void addEdge(int v, int w) {
    adjMatrix[v][w] = 1;
    adjMatrix[w][v] = 1;
}

void DFSUtil(int v, bool* visited) {
    visited[v] = true;

    for (int i = 0; i < vertices; ++i) {
        if (adjMatrix[v][i] && !visited[i]) {
            DFSUtil(i, visited);
        }
    }
}

bool isConnected() {
    bool* visited = new bool[vertices];
    for (int i = 0; i < vertices; ++i) {
        visited[i] = false;
    }

    // Find the first non-zero degree vertex
    int i;
    for (i = 0; i < vertices; ++i) {
        bool hasEdge = false;
        for (int j = 0; j < vertices; ++j) {
            if (adjMatrix[i][j] != 0) {
                hasEdge = true;
                break;
            }
        }
        if (hasEdge) {
            break;
        }
    }

    // If there are no edges in the graph, it's connected
    if (i == vertices) {
        delete[] visited;
        return true;
    }

    // Start DFS traversal from the first non-zero degree vertex
    DFSUtil(i, visited);

    // Check if all vertices with non-zero degree are visited
    for (i = 0; i < vertices; ++i) {
        bool hasEdge = false;
        for (int j = 0; j < vertices; ++j) {
            if (adjMatrix[i][j] != 0) {
                hasEdge = true;
                break;
            }
        }
        if (hasEdge && !visited[i]) {
            delete[] visited;
            return false;
        }
    }

    delete[] visited;
    return true;
}

int main() {
    vertices = 5;
    for (int i = 0; i < MAX; ++i) {
        for (int j = 0; j < MAX; ++j) {
            adjMatrix[i][j] = 0;
        }
    }

    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);

    if (isConnected()) {
        // The graph is connected.
    } else {
        // The graph is not connected.
    }

    return 0;
}