Algoritmus hĺbkového prvého vyhľadávania (DFS)

Obsah

Algoritmus vyhľadávania prvého hĺbky
Príklad hĺbkového prvého vyhľadávania
PFS pseudokód (rekurzívna implementácia)
Implementácia DFS v jazykoch Python, Java a C / C ++
Zložitosť hĺbkového prvého vyhľadávania
Aplikácia DFS algoritmu

V tomto výučbe sa dozviete o algoritme hĺbkového prvého vyhľadávania s príkladmi a pseudokódom. Naučíte sa tiež implementovať DFS v jazykoch C, Java, Python a C ++.

Hĺbka ako prvá alebo trasa Hĺbka ako prvá je rekurzívny algoritmus na prehľadávanie všetkých vrcholov grafu alebo stromovej dátovej štruktúry. Traverz znamená návštevu všetkých uzlov grafu.

Algoritmus vyhľadávania prvého hĺbky

Štandardná implementácia DFS stavia každý vrchol grafu do jednej z dvoch kategórií:

Navštívené
Nenavštívené

Účelom algoritmu je označiť každý vrchol ako navštívený, pričom sa treba vyhnúť cyklom.

Algoritmus DFS funguje nasledovne:

Začnite umiestnením ktoréhokoľvek z vrcholov grafu na hromadu.
Vezmite hornú položku zásobníka a pridajte ju do zoznamu navštívených.
Vytvorte zoznam susedných uzlov tohto vrcholu. Do hornej časti zásobníka pridajte tie, ktoré nie sú v zozname navštívených.
Opakujte kroky 2 a 3, kým nie je zásobník prázdny.

Príklad hĺbkového prvého vyhľadávania

Pozrime sa, ako algoritmus hĺbkového prvého vyhľadávania funguje na príklade. Používame neorientovaný graf s 5 vrcholmi.

Neusmernený graf s 5 vrcholmi

Vychádzame z vrcholu 0, algoritmus DFS sa začína vložením do zoznamu Navštívené a vložením všetkých jeho susedných vrcholov do zásobníka.

Navštívte prvok a vložte ho do zoznamu navštívených

Ďalej navštívime prvok v hornej časti stohu, tj. 1, a prejdeme k jeho susedným uzlom. Pretože 0 už bola navštívená, navštívime radšej 2.

Navštívte prvok v hornej časti stohu

Vertex 2 má nenavštívený susedný vrchol v 4, takže ho pridáme do hornej časti stohu a navštívime ho.

Keď navštívime posledný prvok 3, nemá žiadne nenavštívené susedné uzly, takže sme dokončili priechod hĺbky prvého grafu.

PFS pseudokód (rekurzívna implementácia)

Pseudokód pre DFS je uvedený nižšie. Vo funkcii init () si všimnite, že na každom uzle spúšťame funkciu DFS. Je to tak preto, lebo graf môže mať dve rôzne odpojené časti, aby sme zaistili, že pokryjeme každý vrchol, môžeme tiež spustiť algoritmus DFS na každom uzle.

 DFS (G, u) u.visited = true pre každé v ∈ G.Adj (u) if v.visited == false DFS (G, v) init () (Pre každé u ∈ G u.visited = false pre každú u ∈ G DFS (G, u))

Implementácia DFS v jazykoch Python, Java a C / C ++

Kód algoritmu hĺbkového prvého vyhľadávania s príkladom je uvedený nižšie. Kód bol zjednodušený, aby sme sa mohli sústrediť na algoritmus a nie na ďalšie podrobnosti.

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