利用dfs判断无向图G是否连通
时间: 2023-07-30 07:09:03 浏览: 54
可以使用深度优先搜索(DFS)来判断无向图G是否连通。具体步骤如下:
1. 任选一个节点v作为起点,将其标记为已访问。
2. 对于节点v的每个未被访问的邻居节点w,以w为新的起点进行递归搜索,并将其标记为已访问。
3. 如果存在未被访问的节点,则返回2;否则,返回1。
4. 如果存在未被访问的节点,选择其中一个未被访问的节点u,重复以上步骤。
如果在步骤2和步骤3中遍历了整个图,即所有节点都被标记为已访问,则说明该图是连通的。如果存在未被访问的节点,则说明该图不是连通的。
以下是一个示例代码,其中用visited数组记录了每个节点是否被访问过。
```c++
#include <iostream>
#include <vector>
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 is_connected(vector<vector<int>>& graph) {
int n = graph.size();
vector<bool> visited(n, false);
dfs(graph, visited, 0);
for (bool v : visited) {
if (!v) {
return false;
}
}
return true;
}
int main() {
vector<vector<int>> graph = {{1, 2}, {0}, {0}, {4, 5}, {3}, {3}};
cout << (is_connected(graph) ? "Connected" : "Not connected") << endl;
return 0;
}
```
输出结果为:Connected