Поиск в ширину у графа

В данном алгоритме граф будет представлен в виде матрицы смежности, что очень удобно. Да и к тому же вы можете с легкостью написать свой код для перехода от матрицы к списку смежности.
Поиск в ширину один из самых простейших обходов в графа, как пример алгоритм Дейкстры использует похожую схему обхода.

• Суть данного алгоритма в том, что в процессе обхода мы идем вширь, то есть, перед тем, как приступить к поиску вершин на расстоянии k+1, мы выполняем обход всех вершин на расстоянии k.
• Для отслеживания процесса обхода, мы окрашиваем вершины в белый, серый или черный цвета.
• Сначала мы все вершины у нас белые, начальную вершину мы красим серым цветом, для обозначения окраса у нас есть вектор colors[numOfVertices]:
1. color[i]=0 - белый цвет
2. color[i]=1 - серый цвет
3. color[i]=2 - черный цвет
• Еще у нас есть вектор расстояний d[numOfVertices] - очень удобная штука, чтобы посмотреть, есть ли у нас какие нибудь несвязные вершины.

Алгоритм:

1. Пока очередь не пуста:
1. Взять первый элемент из очереди u
2. Цикл для каждой связной с вершиной u вершиной (v)
1. если у нас вершина v не окрашенная
1. окрасит в серый
2. пометить в векторе, что d[v]=d[u]+1
3. добавить вершину в очередь
3. Окрасить вершину u в черный цвет

Реализация:

void BFS(unsigned int NumOfVertices, double **ConnectionMatrix, unsigned int start, unsigned int target){
  //BFS algorithm
 if (target==start) return;
 const double INFINITY=1E10;
 unsigned int u=start;
 //0-white, grey-1, black-2
 vector  d (NumOfVertices,INFINITY); //вектор расстояний
 d[start]=0;
 vector  color(NumOfVertices,0); //вектор закраски
 color[start]=1;
 vector  predcessors (NumOfVertices);
 predcessors[start]=-1;
 queue  q;
 q.push(start);
 while (!q.empty()) {
  u=q.front();
  q.pop();
  for (int v=0; v< NumOfVertices; v++) {
   if (color[v]==0&&ConnectionMatrix[u][v]) {
    color[v]=1;
    d[v]=d[u]+1;
    predcessors[v]=u;
    q.push(v);
   }
  }
  color[start]=2;
 }
 cout< path;
 for (int cur=target; cur!=-1; cur=predcessors[cur])
  path.push_back (cur);
 reverse (path.begin(), path.end());
 cout << "Path from " << start << " to " << target << ": ";
 for (size_t i=0; i

Posted in: Алгоритмы, Графы, CPP