Chương trình C++ tìm đường đi giữa hai nút trong đồ thị

Chương trình này xác định xem có đường đi giữa hai nút hay không bằng cách dùng DFS trên đồ thị cho trước.

Thuật toán

Bắt đầu
  hàm isReach() đệ quy kiểm tra d có đạt được từ s:
    A) Đánh dấu tất cả đỉnh chưa thăm.
    B) Đánh dấu nút hiện tại đã thăm và đưa vào hàng đợi, dùng để lấy tất cả đỉnh kề.
    C) Lấy đỉnh từ hàng đợi và in ra.
    D) Lấy tất cả đỉnh kề của đỉnh s vừa lấy.
    E) Nếu đỉnh kề chưa thăm, đánh dấu đã thăm và đưa vào hàng đợi.
    F) Nếu đỉnh kề là đích, trả về true, ngược lại tiếp tục BFS.
Kết thúc

Ví dụ mã nguồn

#include <iostream>
#include <list>
using namespace std;

class G {
    int n;
    list<int> *adj;
public:
    G(int n);
    void addEd(int v, int u);
    bool isReach(int s, int d);
};

G::G(int n) {
    this->n = n;
    adj = new list<int>[n];
}

void G::addEd(int v, int u) {
    adj[v].push_back(u);
}

bool G::isReach(int s, int d) {
    if (s == d) return true;
    bool *visited = new bool[n];
    for (int i = 0; i < n; i++) visited[i] = false;
    list<int> queue;
    visited[s] = true;
    queue.push_back(s);
    list<int>::iterator i;
    while (!queue.empty()) {
        s = queue.front();
        queue.pop_front();
        for (i = adj[s].begin(); i != adj[s].end(); ++i) {
            if (*i == d) return true;
            if (!visited[*i]) {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }
    return false;
}

int main() {
    G g(4);
    g.addEd(1, 3);
    g.addEd(0, 1);
    g.addEd(2, 3);
    g.addEd(1, 0);
    g.addEd(2, 1);
    g.addEd(3, 1);
    cout << "Nhập đỉnh nguồn và đích: (0-3)";
    int a, b;
    cin >> a >> b;
    if (g.isReach(a, b))
        cout << "\nCó đường đi từ " << a << " đến " << b;
    else
        cout << "\nKHÔNG có đường đi từ " << a << " đến " << b;
    int t = a; a = b; b = t;
    if (g.isReach(a, b))
        cout << "\nCó đường đi từ " << a << " đến " << b;
    else
        cout << "\nKHÔNG có đường đi từ " << a << " đến " << b;
    return 0;
}

Kết quả

Nhập đỉnh nguồn và đích: (0-3)
Có đường đi từ 3 đến 1
Có đường đi từ 1 đến 3