Chương trình sử dụng thuật toán tìm kiếm theo chiều rộng (BFS) để xác định xem có đường đi từ đỉnh nguồn đến đỉnh đích trong đồ thị có hướng hay không.
Thuật toán
Hàm isReach(s, d):
Nếu s == d: trả về true.
Khởi tạo mảng visited[] = false.
Hàng đợi queue, thêm s, đánh dấu visited[s] = true.
Khi queue không rỗng:
Lấy đỉnh u = queue.front(), queue.pop().
Với mỗi đỉnh kề v của u:
Nếu v == d: trả về true.
Nếu chưa thăm v: đánh dấu visited[v] = true, push v vào queue.
Trả về false.
Ví dụ mã nguồn
#include <iostream>
#include <list>
using namespace std;
class Graph {
int V;
list<int> *adj;
public:
Graph(int V) { this->V = V; adj = new list<int>[V]; }
void addEdge(int u, int v) { adj[u].push_back(v); }
bool isReachable(int s, int d);
};
bool Graph::isReachable(int s, int d) {
if (s == d) return true;
vector<bool> visited(V, false);
list<int> queue;
visited[s] = true;
queue.push_back(s);
while (!queue.empty()) {
int u = queue.front(); queue.pop_front();
for (int v : adj[u]) {
if (v == d) return true;
if (!visited[v]) {
visited[v] = true;
queue.push_back(v);
}
}
}
return false;
}
int main() {
Graph g(4);
g.addEdge(1, 3);
g.addEdge(0, 1);
g.addEdge(2, 3);
g.addEdge(1, 0);
g.addEdge(2, 1);
g.addEdge(3, 1);
int a, b;
cout << "Nhap dinh nguon va dich (0-3): ";
cin >> a >> b;
if (g.isReachable(a, b))
cout << "Co duong di tu " << a << " den " << b;
else
cout << "Khong co duong di tu " << a << " den " << b;
swap(a, b);
if (g.isReachable(a, b))
cout << "\nCo duong di tu " << a << " den " << b;
else
cout << "\nKhong co duong di tu " << a << " den " << b;
return 0;
}
Đầu ra mẫu
Nhap dinh nguon va dich (0-3): 3 1 Co duong di tu 3 den 1 Co duong di tu 1 den 3