Đồ thị không liên thông là đồ thị mà một hoặc nhiều nút không phải là điểm cuối của đồ thị, tức là chúng không được kết nối.
Một đồ thị không liên thông...
Bây giờ, BFS đơn giản chỉ áp dụng khi đồ thị liên thông, tức là tất cả đỉnh của đồ thị đều truy cập được từ một nút. Trong đồ thị không liên thông trên, kỹ thuật đó không thể thực hiện vì một số định luật không truy cập được, nên chương trình thay đổi sau sẽ tốt hơn để thực hiện tìm kiếm theo chiều rộng trong đồ thị không liên thông.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
void insertnode(vector<int> adj[], int u, int v) {
adj[u].push_back(v);
}
void breathFirstSearch(int u, vector<int> adj[], vector<bool> &visited) {
list<int> q;
visited[u] = true;
q.push_back(u);
while(!q.empty()) {
u = q.front();
cout << u << " ";
q.pop_front();
for (int i = 0; i != adj[u].size(); ++i) {
if (!visited[adj[u][i]]) {
visited[adj[u][i]] = true;
q.push_back(adj[u][i]);
}
}
}
}
void BFSdisc(vector<int> adj[], int V) {
vector<bool> visited(V, false);
for (int u = 0; u < V; u++)
if (visited[u] == false)
breathFirstSearch(u, adj, visited);
}
int main() {
int V = 5;
vector<int> adj[V];
insertnode(adj, 0, 23);
insertnode(adj, 0, 4);
insertnode(adj, 1, 2);
insertnode(adj, 1, 3);
insertnode(adj, 1, 4);
insertnode(adj, 2, 3);
insertnode(adj, 3, 4);
BFSdisc(adj, V);
return 0;
}
Kết quả
0 4 1 2 3