В этом туториале описан алгоритм поиска в глубину (depth first search, DFS) с псевдокодом и примерами. Кроме того, расписаны способы реализации поиска в глубину в C, Java, Python и C++.

“Поиск в глубину” или “обход в глубину” — это рекурсивный алгоритм по поиску всех вершин графа или дерева. Обход подразумевает под собой посещение всех вершин графа.

Алгоритм поиска в глубину

Стандартная реализация поиска в глубину помещает каждую вершину (узел, node) графа в одну из двух категорий:

1. Пройденные (Visited).

2. Не пройденные (Not Visited).

Цель алгоритма состоит в том, чтобы пометить каждую вершину как “Пройденная”, избегая при этом циклов.

Алгоритм поиска в глубину работает следующим образом:

1. Начните с того, что поместите любую вершину графа на вершину стека.

2. Возьмите верхний элемент стека и добавьте его в список “Пройденных”.

3. Создайте список смежных вершин для этой вершины. Добавьте те вершины, которых нет в списке “Пройденных”, в верх стека.

4. Необходимо повторять шаги 2 и 3, пока стек не станет пустым.

Пример реализации поиска в глубину

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

Начнем мы с вершины “0”. В первую очередь алгоритм поиска в глубину поместит ее саму в список “Пройденные” (на изображении “Visited”), а ее смежные вершины — в стек.

Затем мы берем следующий элемент сверху стека, т.е. к вершину “1”, и переходим к ее соседним вершинам. Поскольку вершина “0” уже пройдена, следующая вершина “2”.

Вершина “2” смежна непройденной вершине “4”, следовательно мы добавляем ее наверх стека и проходим ее.

После того, как мы пройдем последний элемент (вершину “3”), в стеке не останется непройденных смежных вершин, и таким образом мы завершили обход графа в глубину.

Псевдокод поиска в глубину (рекурсивная реализация)

Ниже представлен псевдокод для алгоритма поиска в глубину. Обратите внимание, что в функции init() необходимо запускать функцию DFS на каждой вершине. Это связано с тем, что граф может иметь две разные несвязанные части, поэтому для того, чтобы убедиться, что мы покрываем каждую вершину, мы должны запускать алгоритм поиска в глубину на каждой вершине.

DFS(G, u)
    u.visited = true
    for each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)
     
init() {
    For each u ∈ G
        u.visited = false
     For each u ∈ G
       DFS(G, u)
}

Реализация поиска в глубину на Python, Java и C/C++

Ниже приведены примеры реально кода алгоритма поиска в глубину. Код был упрощен, чтобы мы могли сфокусироваться на самом алгоритме, а не на других деталях.

# Алгоритм поиска в глубину на Python


# Алгоритм
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    print(start)

    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited


graph = {'0': set(['1', '2']),
         '1': set(['0', '3', '4']),
         '2': set(['0']),
         '3': set(['1']),
         '4': set(['2', '3'])}

dfs(graph, '0')

// Алгоритм поиска в глубину на Java
import java.util.*;
 
class Graph {
  private LinkedList<Integer> adjLists[];
  private boolean visited[];
 
  // Создание графа
  Graph(int vertices) {
    adjLists = new LinkedList[vertices];
    visited = new boolean[vertices];
 
    for (int i = 0; i < vertices; i++)
      adjLists[i] = new LinkedList<Integer>();
  }
 
  // Добавление ребер
  void addEdge(int src, int dest) {
    adjLists[src].add(dest);
  }
 
  // Алгоритм 
  void DFS(int vertex) {
    visited[vertex] = true;
    System.out.print(vertex + " ");
 
    Iterator<Integer> ite = adjLists[vertex].listIterator();
    while (ite.hasNext()) {
      int adj = ite.next();
      if (!visited[adj])
        DFS(adj);
    }
  }
 
  public static void main(String args[]) {
    Graph g = new Graph(4);
 
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
 
    System.out.println("Following is Depth First Traversal");
 
    g.DFS(2);
  }
}

// Алгоритм поиска в глубину на C
 
#include <stdio.h>
#include <stdlib.h>
 
struct node {
  int vertex;
  struct node* next;
};
 
struct node* createNode(int v);
 
struct Graph {
  int numVertices;
  int* visited;
 
  // Нам нужен int** для хранения двумерного массива.
  // Аналогично, нам нужна структура node** для хранения массива связанных списков.
  struct node** adjLists;
};
 
// Алгоритм
void DFS(struct Graph* graph, int vertex) {
  struct node* adjList = graph->adjLists[vertex];
  struct node* temp = adjList;
 
  graph->visited[vertex] = 1;
  printf("Visited %d \n", vertex);
 
  while (temp != NULL) {
    int connectedVertex = temp->vertex;
 
    if (graph->visited[connectedVertex] == 0) {
      DFS(graph, connectedVertex);
    }
    temp = temp->next;
  }
}
 
// Создание вершины
struct node* createNode(int v) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->vertex = v;
  newNode->next = NULL;
  return newNode;
}
 
// Создание графа
struct Graph* createGraph(int vertices) {
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;
 
  graph->adjLists = malloc(vertices * sizeof(struct node*));
 
  graph->visited = malloc(vertices * sizeof(int));
 
  int i;
  for (i = 0; i < vertices; i++) {
    graph->adjLists[i] = NULL;
    graph->visited[i] = 0;
  }
  return graph;
}
 
// Добавление ребра
void addEdge(struct Graph* graph, int src, int dest) {
  // Проводим ребро от начальной вершины ребра графа к конечной вершине ребра графа
  struct node* newNode = createNode(dest);
  newNode->next = graph->adjLists[src];
  graph->adjLists[src] = newNode;
 
  // Проводим ребро из конечной вершины ребра графа в начальную вершину ребра графа
  newNode = createNode(src);
  newNode->next = graph->adjLists[dest];
  graph->adjLists[dest] = newNode;
}
 
// Выводим граф
void printGraph(struct Graph* graph) {
  int v;
  for (v = 0; v < graph->numVertices; v++) {
    struct node* temp = graph->adjLists[v];
    printf("\n Adjacency list of vertex %d\n ", v);
    while (temp) {
      printf("%d -> ", temp->vertex);
      temp = temp->next;
    }
    printf("\n");
  }
}
 
int main() {
  struct Graph* graph = createGraph(4);
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 2);
  addEdge(graph, 1, 2);
  addEdge(graph, 2, 3);
 
  printGraph(graph);
 
  DFS(graph, 2);
 
  return 0;
}

// Алгоритм прохода в глубину в C++
 
#include <iostream>
#include <list>
using namespace std;
 
class Graph {
  int numVertices;
  list<int> *adjLists;
  bool *visited;
 
   public:
  Graph(int V);
  void addEdge(int src, int dest);
  void DFS(int vertex);
};
 
// Инициализация графа
Graph::Graph(int vertices) {
  numVertices = vertices;
  adjLists = new list<int>[vertices];
  visited = new bool[vertices];
}
 
// Добавление ребер
void Graph::addEdge(int src, int dest) {
  adjLists[src].push_front(dest);
}
 
// Алгоритм 
void Graph::DFS(int vertex) {
  visited[vertex] = true;
  list<int> adjList = adjLists[vertex];
 
  cout << vertex << " ";
 
  list<int>::iterator i;
  for (i = adjList.begin(); i != adjList.end(); ++i)
    if (!visited[*i])
      DFS(*i);
}
 
int main() {
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 3);
 
  g.DFS(2);
 
  return 0;
}

Сложность алгоритма поиска в глубину

Временная сложность алгоритма поиска в глубину представлена ​​в виде O(V + E), где V — количество вершин, а E — количество ребер.

Пространственная сложность алгоритма равна O(V).

Применения алгоритма

1. Для поиска пути.

2. Для проверки двудольности графа.

3. Для поиска сильно связанных компонентов графа.

4. Для обнаружения циклов в графе.

Приглашаем всех желающих на открытый урок в OTUS «Теория графов. Термины и определения. Основные алгоритмы», регистрация доступна по ссылке.