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

Содержание

Алгоритм поиска в глубину
Пример поиска в глубину
Псевдокод DFS (рекурсивная реализация)
Реализация DFS на Python, Java и C / C ++
Сложность поиска в глубину
Применение алгоритма DFS

В этом руководстве вы узнаете об алгоритме поиска в глубину с примерами и псевдокодом. Кроме того, вы научитесь реализовывать DFS на языках C, Java, Python и C ++.

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

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

Стандартная реализация DFS помещает каждую вершину графа в одну из двух категорий:

Посетил
Не посещал

Цель алгоритма - пометить каждую вершину как посещенную, избегая циклов.

Алгоритм DFS работает следующим образом:

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

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

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

Неориентированный граф с 5 вершинами

Мы начинаем с вершины 0, алгоритм DFS запускается с помещения ее в список посещенных и помещения всех соседних вершин в стек.

Посетите элемент и поместите его в список посещенных

Затем мы посещаем элемент наверху стека, т.е. 1, и переходим к его соседним узлам. Поскольку 0 уже был посещен, мы посещаем 2.

Посетите элемент наверху стека

В вершине 2 есть непосещенная смежная вершина в 4, поэтому мы добавляем ее к вершине стека и посещаем ее.

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

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

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

 DFS (G, u) u.visited = true для каждого v ∈ G.Adj (u), если v.visited == false DFS (G, v) init () (Для каждого u ∈ G u.visited = false Для каждого u ∈ G DFS (G, u))

Реализация DFS на Python, Java и C / C ++

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

Python Java C C +

 # DFS algorithm in Python # DFS algorithm 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')

 // DFS algorithm in Java import java.util.*; class Graph ( private LinkedList adjLists(); private boolean visited(); // Graph creation Graph(int vertices) ( adjLists = new LinkedList(vertices); visited = new boolean(vertices); for (int i = 0; i < vertices; i++) adjLists(i) = new LinkedList(); ) // Add edges void addEdge(int src, int dest) ( adjLists(src).add(dest); ) // DFS algorithm void DFS(int vertex) ( visited(vertex) = true; System.out.print(vertex + " "); Iterator 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); ) )

 // DFS algorithm in C #include #include struct node ( int vertex; struct node* next; ); struct node* createNode(int v); struct Graph ( int numVertices; int* visited; // We need int** to store a two dimensional array. // Similary, we need struct node** to store an array of Linked lists struct node** adjLists; ); // DFS algo void DFS(struct Graph* graph, int vertex) ( struct node* adjList = graph->adjLists(vertex); struct node* temp = adjList; graph->visited(vertex) = 1; printf("Visited %d ", vertex); while (temp != NULL) ( int connectedVertex = temp->vertex; if (graph->visited(connectedVertex) == 0) ( DFS(graph, connectedVertex); ) temp = temp->next; ) ) // Create a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Create graph 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 adjLists(i) = NULL; graph->visited(i) = 0; ) return graph; ) // Add edge void addEdge(struct Graph* graph, int src, int dest) ( // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists(src); graph->adjLists(src) = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists(dest); graph->adjLists(dest) = newNode; ) // Print the graph void printGraph(struct Graph* graph) ( int v; for (v = 0; v numVertices; v++) ( struct node* temp = graph->adjLists(v); printf(" Adjacency list of vertex %d ", v); while (temp) ( printf("%d -> ", temp->vertex); temp = temp->next; ) printf(""); ) ) 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; )

 // DFS algorithm in C++ #include #include using namespace std; class Graph ( int numVertices; list *adjLists; bool *visited; public: Graph(int V); void addEdge(int src, int dest); void DFS(int vertex); ); // Initialize graph Graph::Graph(int vertices) ( numVertices = vertices; adjLists = new list(vertices); visited = new bool(vertices); ) // Add edges void Graph::addEdge(int src, int dest) ( adjLists(src).push_front(dest); ) // DFS algorithm void Graph::DFS(int vertex) ( visited(vertex) = true; list adjList = adjLists(vertex); cout << vertex << " "; list::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; )