Может кто-нибудь объяснить мне, как работает этот код BFS? - PullRequest
Новая
       6

Может кто-нибудь объяснить мне, как работает этот код BFS?

0 голосов
/ 10 октября 2019

Я новичок в алгоритмах и структурах данных. Этот код взят из класса, который я пропустил, и теперь мне трудно это понять. Я не мог понять, что происходит после того, как он попросил начальную вершину. Ниже приведен код 

#include<iostream>

#include<conio.h>

#include<stdlib.h>

using namespace std;
int i, j, k, e, n, f, r, v, c[10][10], q[10], visit[10], visited[10];
int main() {
  //clrscr();
  cout << "Enter number of nodes: ";
  cin >> n;
  cout << "Enter number of edges: ";
  cin >> e;
  cout << "enter edge details";
  for (k = 1; k <= e; k++) {
    cin >> i >> j;
    c[i][j] = 1;

  }
  cout << "enter initials vertex:";
  cin >> v;
  cout << "\n visited vertices are:" << v << "";
  visited[v] = 1;
  k = 1;
  while (k < n) {
    for (j = 1; j <= n; j++)
      if ((c[v][j] != 0) && (visited[j] != 1) && (visit[j] != 1)) {
        visit[j] = 1;
        q[r++] = j;
      }
    v = q[f++];
    cout << v << "";
    k++;
    visit[v] = 0;
    visited[v] = 1;
  }
}

1 Ответ

0 голосов
/ 10 октября 2019

q - очередь («первым пришел - первым обслужена», FIFO), типичная для BFS. На передний очереди указывается f (отсюда извлекаются значения), а на задний очереди указывается r (где новыйзначения добавляются в очередь).

Сначала очередь пуста, а соседи j текущей вершины v добавляются в очередь (на ее "задней" стороне). Когда вершина j находится в очереди, ее visit[j] устанавливается в 1, в противном случае это 0. Это предотвращает добавление одной и той же вершины дважды в очередь.

С началаочередь, следующая вершина вытягивается. Теперь он считается посещенным, поэтому visited[v] теперь установлен на 1, а visit[v] очищен (это немного излишне, но все в порядке). Опять же, это гарантирует, что вершины посещаются (и выводятся) только один раз.

Используя очередь, мы уверены, что вершины посещаются в порядке их расстояния (с точки зрения количества ребер) от начальной вершины. .

Поскольку существует n вершин, все они будут посещены, когда внешний цикл будет повторяться n раза. Вот что имеет значение k.

...