Tìm đường đi từ một đỉnh đến các đỉnh còn lại bằng BFS C++

Mô tả bài toán

Cho đồ thị có hướng (danh sách kề). In đường đi từ đỉnh nguồn đến mọi đỉnh khác bằng BFS.

Ví dụ

Đồ thị 5 đỉnh: 0→1,3; 1→0,2; 2→1; 3→4; 4→0. Từ đỉnh 0:\n0\n1 ≤ 0\n2 ≤ 1 ≤ 0\n3 ≤ 0\n4 ≤ 3 ≤ 0

Giải thuật BFS

1. Hàng đợi lưu đỉnh, mảng visited, mảng parent.
2. BFS từ nguồn, cập nhật parent.
3. Với mỗi đỉnh, truy ngược parent để in đường đi.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

void printPath(vector parent, int src, int v) {
    while (src != v) { cout << v << " <= "; v = parent[v]; }
    cout << v << '\n';
}

void findPathBFS(vector> adj, int src, int n) {
    vector parent(n), vis(n), q(n);
    int front=-1, rear=-1;
    vis[src]=1; parent[src]=src; q[++rear]=src;
    while (front != rear) {
        int u = q[++front];
        for (int v : adj[u]) if (!vis[v]) {
            vis[v]=1; parent[v]=u; q[++rear]=v;
        }
    }
    for (int i=0; i> adj = {{1,3},{0,2},{1},{4},{0}};
    int n=adj.size(), src=0;
    cout << "Paths from vertex 0:\n";
    findPathBFS(adj, src, n);
    return 0;
}

Đầu ra

The Path from vertex '0' to all other vertex in the graph is :
0
1 <= 0
2 <= 1 <= 0
3 <= 0
4 <= 3 <= 0