c++广度优先遍历计算连通分量

广度优先遍历是一种基于队列的搜索算法，用于遍历图的所有节点。计算连通分量即是通过广度优先遍历找出图中的所有连通分支。

首先，我们从图中随机选取一个节点作为起始节点，将其加入队列中并标记为已访问。然后，从队列中逐个取出节点，并遍历其所有相邻节点。

如果这些相邻节点没有被访问过，则将它们加入队列，并标记为已访问。重复该过程，直到队列为空。

在遍历的过程中，如果发现节点的相邻节点都已被标记为已访问，则说明该节点所在的连通分支已被完全遍历。我们可以将该连通分支的节点计数加一，并继续遍历队列中的其他节点。

最终，当队列中所有节点都被遍历完毕，我们就可以得到图中的所有连通分支的数量。

通过广度优先遍历计算连通分量的过程可以用以下步骤总结：
1. 选择一个起始节点并将其入队，并标记为已访问。
2. 当队列非空时，进行以下循环：
- 取出队首节点，并遍历其所有未被访问的相邻节点。
- 对于每个相邻节点，如果其未被访问过，将其入队并标记为已访问。
3. 如果一个节点的所有相邻节点都被标记为已访问，则该节点所在的连通分支遍历完毕，将连通分量计数增加一。
4. 重复步骤2和3，直到队列为空。
5. 返回连通分量计数作为结果。

通过广度优先遍历计算连通分量的时间复杂度为O(V + E)，其中V为节点数，E为边数。

相关问题

广度优先遍历连通图c++代码

以下是广度优先遍历连通图的C++代码实现：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int MAXN = 100; // 最大顶点数
const int INF = 0x3f3f3f3f; // 无穷大

vector<int> adj[MAXN]; // 邻接表
bool visited[MAXN]; // 标记数组

void BFS(int s) {
    queue<int> q; // 定义队列
    visited[s] = true; // 标记s已访问
    q.push(s); // 将s入队
    while (!q.empty()) { // 队列不为空
        int u = q.front(); // 取出队首元素
        q.pop(); // 将队首元素出队
        cout << u << " "; // 输出u
        for (int v : adj[u]) { // 遍历u的所有邻接点
            if (!visited[v]) { // 如果v未被访问
                visited[v] = true; // 标记v已访问
                q.push(v); // 将v入队
            }
        }
    }
}

int main() {
    int n, m; // n为顶点数，m为边数
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v; // u和v之间有一条边
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // 无向图需要加上这一行
    }
    int s; // 指定起点
    cin >> s;
    BFS(s); // 从s开始遍历
    return 0;
}

该算法的时间复杂度为$O(|V|+|E|)$，其中$|V|$和$|E|$分别为顶点数和边数。因为每个顶点和每条边都只会被访问一次。

实现代码：图的遍历 实现对连通无向图的深度优先和广度优先遍历算法。 要求： （1）输入图的顶点和边的信息； （2）按用户指定的顶点开始遍历，深度优先遍历图中所有顶点，并输出顶点； （3）按用户指定的顶点开始遍历，广度优先遍历、输出各顶点。

以下是C++实现的图的深度优先遍历和广度优先遍历算法，代码中使用邻接表表示图：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 100; // 最大顶点数
const int INF = 0x3f3f3f3f; // 无穷大

// 邻接表存储图
struct Edge {
    int to, weight;
    Edge(int t, int w): to(t), weight(w) {}
};

vector<Edge> adj[MAXN]; // 邻接表
bool visited[MAXN]; // 标记顶点是否访问过

// 深度优先遍历
void dfs(int u) {
    visited[u] = true;
    cout << u << " ";

    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i].to;
        if (!visited[v]) {
            dfs(v);
        }
    }
}

// 广度优先遍历
void bfs(int u) {
    queue<int> q;
    q.push(u);
    visited[u] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";

        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].to;
            if (!visited[v]) {
                q.push(v);
                visited[v] = true;
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入顶点数和边数

    // 输入边的信息
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(Edge(v, w));
        adj[v].push_back(Edge(u, w));
    }

    // 按用户指定的顶点开始遍历
    int u;
    cin >> u;

    // 深度优先遍历
    cout << "DFS: ";
    dfs(u);
    cout << endl;

    // 重置visited数组
    memset(visited, false, sizeof(visited));

    // 广度优先遍历
    cout << "BFS: ";
    bfs(u);
    cout << endl;

    return 0;
}

在输入时，每输入一条边就在邻接表中添加两条边，因为是无向图。例如，输入 `(1, 2, 3)` 时，在邻接表中添加 `(1, 2, 3)` 和 `(2, 1, 3)` 两条边。

输入格式：

5 7
1 2 2
1 3 3
1 5 4
2 3 1
3 4 5
4 5 1
2  // 指定遍历起点为2

输出格式：

DFS: 2 1 5 4 3
BFS: 2 1 3 5 4