Алгоритъм за обхождане в ширина (Breadth First Search)

Характерно за този алгоритъм е, че след като се посети един връх, се обхождат всички негови непосетени съседи и чак след това се преминава към обхождане на техните съседи и т.н. За реализацията на това обхождане се използва опашка, в която се записват върховете на графа. Ето по-подробно описание.


1. Разглежда се върхът i.
2. Добавя се върхът i в опашката от върхове.
3. Докато опашката не е празна се повтаря следното:
3. 1. Изтрива се първият елемент от опашката.
3. 2. Разглеждат се всички негови непосетени съседи и се добавят в опашката.


Ето как може да се реализира този алгоритъм със средствата на езика С++. Графът е представен чрез матрица на съседство. Въвеждат се двойки свързани върхове, като за край на въвеждане служат две нули. Обхождането става чрез  функцията bfs. Като помощен масив се използва масива used, който служи за маркиране на посетените върхове. Тук е необходимо да се използва опашка от цели числа, като за реализацията й е използван типа queue от стандартната библиотека на езика С++.

Възел 6 е с ниво 0. Неговите съседи са с ниво 1: 3, 11, 1, 13 и 4. Непосетените съседи на тези възли са от ниво 2: 12 (съсед на 3) 2 (съсед на 11) 8 (съсед на 1) 5 (съсед на 4) Непосетените съседи на тези възли са от ниво 3: 10 (съсед на 12) 9 и 7 (съседи на 8)  

Ако за начален връх на обхождане се въведе връх с нoмер 6 обхождането се извършва както е показано на анимацията.

6
1
3
4
11
13
8
12
5
2
7
9
10
Презентацията приключи. Натисни бутона за да се рестартира
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int n,v,used[101];
queue<int>q;
vector<int>a[101];

void bfs()
{
  q.push(v);
  used[v]=1;
  while(!q.empty()) // докато опашката не е празна
  {
    int t=q.front();
    q.pop();
    printf("%d ",t);
    for(int i=0; i<a[t].size(); i++)
    {
       if(used[a[t][i]]==0) /* ако не е обходен */
       {
          q.push(a[t][i]);
          used[a[t][i]]=1;
       }
    }
  }
}

int main()
{
  scanf("%d %d",&n,&v); /* дължина на графа и връх,   от който да обхождаме*/
  int b,c;
  while(b!=0 || c!=0)
  {
    scanf("%d %d",&b,&c);
    a[b].push_back(c);
    a[c].push_back(b);
  }
  bfs();
  printf("\n");
  return 0;
}