Algoritmul Căutare în adâncime (DFS)

Cuprins

Algoritm de căutare a adâncimii
Exemplu de căutare a adâncimii
Pseudocod DFS (implementare recursivă)
Implementare DFS în Python, Java și C / C ++
Complexitatea căutării în profunzime
Aplicarea algoritmului DFS

În acest tutorial, veți afla despre algoritmul de căutare în profunzime, cu exemple și pseudocod. De asemenea, veți învăța să implementați DFS în C, Java, Python și C ++.

Căutarea în adâncime în primul rând sau traversarea în adâncime în primul rând este un algoritm recursiv pentru căutarea tuturor vârfurilor unui grafic sau a unei structuri de date în arbore. Traversal înseamnă a vizita toate nodurile unui grafic.

Algoritm de căutare a adâncimii

O implementare standard DFS pune fiecare vârf al graficului în una din cele două categorii:

Vizitat
Nu a fost vizitat

Scopul algoritmului este de a marca fiecare vârf ca fiind vizitat evitând ciclurile.

Algoritmul DFS funcționează după cum urmează:

Începeți prin a pune oricare dintre vârfurile grafului deasupra unei stive.
Luați elementul de sus al stivei și adăugați-l la lista vizitată.
Creați o listă a nodurilor adiacente ale vârfului respectiv. Adăugați cele care nu sunt în lista vizitată în partea de sus a stivei.
Repetați pașii 2 și 3 până când stiva este goală.

Exemplu de căutare a adâncimii

Să vedem cum funcționează algoritmul Depth First Search cu un exemplu. Folosim un grafic neorientat cu 5 vârfuri.

Grafic nedirectat cu 5 vârfuri

Începem de la vârful 0, algoritmul DFS începe prin plasarea acestuia în lista Vizitat și punerea tuturor vârfurilor adiacente în stivă.

Accesați elementul și puneți-l în lista vizitată

Apoi, vizităm elementul din partea de sus a stivei, adică 1 și mergem la nodurile sale adiacente. Deoarece 0 a fost deja vizitat, vizităm în schimb 2.

Vizitați elementul din partea de sus a stivei

Vertex 2 are un vârf adiacent nevizitat în 4, așa că îl adăugăm în partea de sus a stivei și îl vizităm.

După ce vizităm ultimul element 3, acesta nu are noduri adiacente nevizitate, așa că am finalizat Traversarea în adâncime a graficului.

Pseudocod DFS (implementare recursivă)

Pseudocodul pentru DFS este prezentat mai jos. În funcția init (), observați că rulăm funcția DFS pe fiecare nod. Acest lucru se datorează faptului că graficul ar putea avea două părți diferite deconectate, astfel încât să ne asigurăm că acoperim fiecare vârf, putem rula și algoritmul DFS pe fiecare nod.

 DFS (G, u) u.visited = adevărat pentru fiecare v ∈ G.Adj (u) dacă v.visited == false DFS (G, v) init () (Pentru fiecare u ∈ G u.visited = false Pentru fiecare u ∈ G DFS (G, u))

Implementare DFS în Python, Java și C / C ++

Codul pentru algoritmul de căutare a adâncimii cu un exemplu este prezentat mai jos. Codul a fost simplificat astfel încât să ne putem concentra asupra algoritmului mai degrabă decât asupra altor detalii.

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; )