在C++中,可以使用深度優先搜索(DFS)或廣度優先搜索(BFS)算法來判斷圖的連通性。以下是使用深度優先搜索算法判斷無向圖連通性的示例代碼:
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
void dfs(vector<vector<int>>& graph, vector<bool>& visited, int start) {
visited[start] = true;
for (int i = 0; i < graph[start].size(); i++) {
if (!visited[graph[start][i]]) {
dfs(graph, visited, graph[start][i]);
}
}
}
bool isGraphConnected(vector<vector<int>>& graph) {
int n = graph.size();
vector<bool> visited(n, false);
dfs(graph, visited, 0);
for (int i = 0; i < n; i++) {
if (!visited[i]) {
return false;
}
}
return true;
}
int main() {
vector<vector<int>> graph = {
{1, 2},
{0, 2},
{0, 1, 3},
{2}
};
if (isGraphConnected(graph)) {
cout << "The graph is connected." << endl;
} else {
cout << "The graph is not connected." << endl;
}
return 0;
}
在上面的代碼中,我們定義了一個dfs
函數來進行深度優先搜索,然后通過遍歷整個圖,檢查是否所有節點都被訪問到來判斷圖的連通性。如果所有節點都被訪問到,則圖是連通的,否則圖是不連通的。