Algoritme voor Depth First Search (DFS)

Inhoudsopgave

Diepte eerste zoekalgoritme
Voorbeeld diepte eerste zoekopdracht
DFS Pseudocode (recursieve implementatie)
DFS-implementatie in Python, Java en C / C ++
Complexiteit van Depth First Search
Toepassing van DFS-algoritme

In deze zelfstudie leert u over het algoritme voor het eerst op de diepte zoeken met voorbeelden en pseudocode. Ook leer je DFS implementeren in C, Java, Python en C ++.

Diepte eerst zoeken of Diepte eerst traversal is een recursief algoritme voor het doorzoeken van alle hoekpunten van een grafiek of boomgegevensstructuur. Traversal betekent het bezoeken van alle knooppunten van een grafiek.

Diepte eerste zoekalgoritme

Een standaard DFS-implementatie plaatst elk hoekpunt van de grafiek in een van de twee categorieën:

Bezocht
Niet bezocht

Het doel van het algoritme is om elk hoekpunt te markeren als bezocht terwijl cycli worden vermeden.

Het DFS-algoritme werkt als volgt:

Begin door een van de hoekpunten van de grafiek op een stapel te plaatsen.
Neem het bovenste item van de stapel en voeg het toe aan de bezochte lijst.
Maak een lijst met de aangrenzende knooppunten van dat hoekpunt. Voeg degenen die niet in de bezochte lijst staan toe aan de bovenkant van de stapel.
Blijf stap 2 en 3 herhalen totdat de stapel leeg is.

Voorbeeld diepte eerste zoekopdracht

Laten we eens kijken hoe het Depth First Search-algoritme werkt met een voorbeeld. We gebruiken een ongerichte graaf met 5 hoekpunten.

Ongerichte graaf met 5 hoekpunten

We beginnen bij hoekpunt 0, het DFS-algoritme begint door het in de lijst Bezocht te plaatsen en alle aangrenzende hoekpunten in de stapel te plaatsen.

Bezoek het element en zet het in de bezochte lijst

Vervolgens bezoeken we het element bovenaan de stapel, dwz 1, en gaan naar de aangrenzende knooppunten. Aangezien 0 al is bezocht, bezoeken we er 2.

Bezoek het element bovenaan de stapel

Vertex 2 heeft een niet-bezocht aangrenzend hoekpunt in 4, dus we voegen dat toe aan de bovenkant van de stapel en bezoeken het.

Nadat we het laatste element 3 hebben bezocht, heeft het geen onbezochte aangrenzende knooppunten, dus hebben we de diepte eerste doorloop van de grafiek voltooid.

DFS Pseudocode (recursieve implementatie)

De pseudocode voor DFS wordt hieronder weergegeven. Merk in de functie init () op dat we de DFS-functie op elk knooppunt uitvoeren. Dit komt omdat de grafiek twee verschillende losgekoppelde delen kan hebben, dus om ervoor te zorgen dat we elk hoekpunt bedekken, kunnen we ook het DFS-algoritme op elk knooppunt uitvoeren.

 DFS (G, u) u.visited = true voor elke 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-implementatie in Python, Java en C / C ++

De code voor het Depth First Search-algoritme met een voorbeeld wordt hieronder weergegeven. De code is vereenvoudigd, zodat we ons op het algoritme kunnen concentreren in plaats van op andere details.

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