В этом туториале описан алгоритм поиска в глубину (depth first search, DFS) с псевдокодом и примерами. Кроме того, расписаны способы реализации поиска в глубину в C, Java, Python и C++.
“Поиск в глубину” или “обход в глубину” — это рекурсивный алгоритм по поиску всех вершин графа или дерева. Обход подразумевает под собой посещение всех вершин графа.
Алгоритм поиска в глубину
Стандартная реализация поиска в глубину помещает каждую вершину (узел, node) графа в одну из двух категорий:
Пройденные (Visited).
Не пройденные (Not Visited).
Цель алгоритма состоит в том, чтобы пометить каждую вершину как “Пройденная”, избегая при этом циклов.
Алгоритм поиска в глубину работает следующим образом:
Начните с того, что поместите любую вершину графа на вершину стека.
Возьмите верхний элемент стека и добавьте его в список “Пройденных”.
Создайте список смежных вершин для этой вершины. Добавьте те вершины, которых нет в списке “Пройденных”, в верх стека.
Необходимо повторять шаги 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).
Применения алгоритма
Для поиска пути.
Для проверки двудольности графа.
Для поиска сильно связанных компонентов графа.
Для обнаружения циклов в графе.
Приглашаем всех желающих на открытый урок в OTUS «Теория графов. Термины и определения. Основные алгоритмы», регистрация доступна по ссылке.