Демо: обходы графа в глубину и в ширину

Управление

Алгоритм обхода

Начальная вершина

Скорость, мс: 600

Посещено

Шагов

В структуре

Граф

Структура данных

Стек пуст

Порядок посещения

—

Нажмите «Запустить» или «Шаг», чтобы начать обход.

Матрица смежности

Граф неориентированный, поэтому матрица симметрична: a[i][j] = a[j][i]. Единица означает наличие ребра между вершинами i и j.

Ключевой код

Обход в глубину (итеративный, со стеком)

void DFS(int a[][N], int v) {
  int st[N], r[N] = {0};   // st — стек, r — пометки
  int k = 0;                // указатель вершины стека
  st[k] = v;
  r[v] = 1;
  cout << "Посетили " << v+1 << endl;
  while (k != -1) {
    int found = -1;
    for (int j = 0; j < N; j++)
      if (a[st[k]][j] && !r[j]) { found = j; break; }
    if (found != -1) {
      r[found] = 1;
      st[++k] = found;
      cout << "Посетили " << found+1 << endl;
    } else {
      k--;                   // откат: из этой вершины пути нет
    }
  }
}

Обход в ширину (очередь)

void BFS(int a[][N], int v) {
  int q[N], head = 0, tail = 0, r[N] = {0};
  q[tail++] = v;
  r[v] = 1;
  while (head < tail) {
    int u = q[head++];
    cout << "Посетили " << u+1 << endl;
    for (int j = 0; j < N; j++)
      if (a[u][j] && !r[j]) {
        r[j] = 1;
        q[tail++] = j;
      }
  }
}

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

Задание

Запустите DFS и BFS из одной и той же вершины. Сравните порядок посещения.
Запустите обход из разных вершин. Всегда ли посещаются все вершины графа?
Добавьте в граф «мост» — ребро, удаление которого разъединяет граф. Как это повлияет на обход из вершины 0?
Модифицируйте алгоритм так, чтобы он запоминал предшественника каждой вершины и умел восстанавливать путь от корня.
Реализуйте рекурсивный DFS и сравните его с итеративным.