Поиск в ширину обход графа по алгоритму, приведенному в Книге CLRS.
BFS - один из способов перемещения по графику. Он назван так потому, что он равномерно расширяет границу между обнаруженными и неоткрытыми вершинами по всей ширине границы. Это означает, что алгоритм сначала обнаруживает все вершины, связанные с «u» на расстоянии k, а затем обнаруживает вершины на расстоянии k + 1. от u. Алгоритм, приведенный в CLRS, использует концепцию «цвета», чтобы проверить, обнаружена ли вершина полностью, частично или неоткрыта. Он также отслеживает расстояние, на котором вершина u находится от источников.
BFS(G,s) 1 for each vertex u in G.V - {s} 2 u.color = white 3 u.d = INF 4 u.p = NIL 5 s.color = green 6 s.d = 0 7 s.p = NIL 8 Q = NULL 9 ENQUEUE(Q,s) 10 while Q != NULL 11 u = DEQUEUE(Q) 12 for each v in G.Adj[u] 13 if v.color == white 14 v.color = green 15 v.d = u.d + 1 16 v.p = u 17 ENQUEUE(Q,v) 18 u.color = dark_green
Он создает «дерево в ширину» с корнем s, которое содержит все достижимые вершины. Давайте возьмем простой ориентированный граф и посмотрим, как BFS проходит по нему.
График
Начало обхода
1-й обход
1-й обход завершен
// CPP program to implement BFS as per CLRS // algorithm.
#include <bits/stdc++.h> using
namespace
std;
// Declaring the vectors to store color, distance // and parent
vector<string> colour; vector<int> d; vector<int> p;
/* This function adds an edge to the graph. It is an undirected graph. So edges are added for both the nodes. */
void
addEdge(vector <int> g[], int
u, int
v) { g[u].push_back(v); g[v].push_back(u); }
/* This function does the Breadth First Search*/ void
BFSSingleSource(vector <int> g[], int
s) { // The Queue used for the BFS operation queue<int> q;
// Pushing the root node inside the queue q.push(s);
/* Distance of root node is 0 & colour is gray as it is visited partially now */ d[s] = 0; colour[s] = "green";
/* Loop to traverse the graph. Traversal will happen traverse until the queue is not empty.*/
while
(!q.empty()) { /* Extracting the front element(node) and poping it out of queue. */ int
u = q.front(); q.pop(); cout << u << " "; /* This loop traverses all the child nodes of u */ for
(auto
i = g[u].begin(); i != g[u].end(); i++) { /* If the colour is white then the said node is not traversed. */ if
(colour[*i] == "white") { colour[*i] = "green"; d[*i] = d[u] + 1; p[*i] = u;
/* Pushing the node inside queue to traverse its children. */ q.push(*i); } }
/* Now the node u is completely traversed and colour is changed to black. */ colour[u] = "dark_green"; } }
void
BFSFull(vector <int> g[], int
n) { /* Initially all nodes are not traversed. Therefore, the colour is white. */ colour.assign(n, "white"); d.assign(n, 0); p.assign(n, -1); // Calling BFSSingleSource() for all white // vertices. for
(int
i = 0; i < n; i++) if
(colour[i] == "white") BFSSingleSource(g, i); }
// Driver Function int
main() { // Graph with 7 nodes and 6 edges. int
n = 7;
// The Graph vector vector <int> g[n]; addEdge(g, 0, 1); addEdge(g, 0, 2); addEdge(g, 1, 3); addEdge(g, 1, 4); addEdge(g, 2, 5); addEdge(g, 2, 6);
BFSFull(g, n); return
0;
}
Выход:
0 1 2 3 4 5 6
Первоначально опубликовано на www.geeksforgeeks.org 26 января 2018 г.