Обход означает посещение всех узлов графа. «Обход в глубину» или «Поиск в глубину» - это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных. В этой статье, с помощью приведенных ниже примеров, вы узнаете: алгоритм DFS, псевдокод DFS и код алгоритма «поиска в глубину» с реализацией в программах на C ++, C, Java и Python.
Алгоритм DFS
Стандартная реализация DFS помещает каждую вершину графа в одну из двух категорий:
- Посещенные.
- Не посещенные.
Цель алгоритма - пометить каждую вершину, как посещенную, избегая циклов.
Алгоритм DFS работает следующим образом:
- Начните с размещения любой вершины графа на вершине стека.
- Возьмите верхний элемент стека и добавьте его в список посещенных.
- Создайте список смежных узлов этой вершины. Добавьте те, которых нет в списке посещенных, в начало стека.
- Продолжайте повторять шаги 2 и 3, пока стек не станет пустым.
Пример DFS
Давайте посмотрим, как алгоритм «поиска в глубину» работает на примере. Мы используем неориентированный граф с 5 вершинами.
Мы начинаем с вершины 0, алгоритм DFS начинается с помещения его в список посещенных и размещения всех смежных вершин в стеке.
Затем мы посещаем элемент в верхней части стека, то есть 1, и переходим к смежным узлам. Так как 0 мы уже посетили, вместо этого посещаем 2.
У вершины 2 есть не посещенная смежная вершина 4, поэтому мы добавляем ее в верхнюю часть стека и посещаем.
После того, как мы посетим последний элемент 3, у него нет не посещенных смежных узлов. На этом мы завершим первый «обход в глубину» графа.
Псевдокод DFS (рекурсивная реализация)
Псевдокод для DFS показан ниже. Обратите внимание, что в функции init() мы запускаем функцию DFS на каждом узле. Это связано с тем, что граф может иметь две разные несвязанные части, поэтому, чтобы убедиться, что мы покрываем каждую вершину, мы также можем запустить алгоритм 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) }
Код DFS
Код для алгоритма «поиска в глубину» с примером показан ниже. Код был упрощен, поэтому мы можем сосредоточиться на алгоритме, а не на других деталях.
DFS в 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; struct node** adjLists; // we need int** to store a two dimensional array. Similary, we need struct node** to store an array of Linked lists }; struct Graph* createGraph(int); void addEdge(struct Graph*, int, int); void printGraph(struct Graph*); void DFS(struct Graph*, int); 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; } 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) { // 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; } 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"); } }
Depth First Search (DFS) в C++
#include <iostream> #include <list> 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); }; Graph::Graph(int vertices) { numVertices = vertices; adjLists = new list[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 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; }
DFS Java код (Java code)
import java.io.*; import java.util.*; class Graph { private int numVertices; private LinkedList<Integer> adjLists[]; private boolean visited[]; Graph(int vertices) { numVertices = 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 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 в 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')