Поиск в ширину обход графа по алгоритму, приведенному в Книге 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 г.