Dybde første søk (DFS) algoritme

I denne opplæringen lærer du om algoritme for første søk med dybde med eksempler og pseudokode. Du vil også lære å implementere DFS i C, Java, Python og C ++.

Dybde første søk eller Dybde første traversal er en rekursiv algoritme for å søke i alle toppunktene i en graf eller tredatastruktur. Traversal betyr å besøke alle nodene i en graf.

Dybde første søkealgoritme

En standard DFS-implementering setter hvert toppunkt i grafen i en av to kategorier:

  1. Besøkt
  2. Ikke besøkt

Formålet med algoritmen er å merke hvert toppunkt som besøkt mens man unngår sykluser.

DFS-algoritmen fungerer som følger:

  1. Start med å plassere en av grafens hjørner på toppen av en bunke.
  2. Ta toppen av bunken og legg den til den besøkte listen.
  3. Lag en liste over toppunktets tilstøtende noder. Legg til de som ikke er i den besøkte listen øverst i bunken.
  4. Gjenta trinn 2 og 3 til bunken er tom.

Eksempel på dybde første søk

La oss se hvordan Depth First Search-algoritmen fungerer med et eksempel. Vi bruker en ikke-rettet graf med 5 hjørner.

Udirigert graf med 5 hjørner

Vi starter fra toppunkt 0, DFS-algoritmen starter med å sette den i Besøkt-listen og sette alle de tilstøtende toppunktene i bunken.

Besøk elementet og legg det i den besøkte listen

Deretter besøker vi elementet øverst på bunken, dvs. 1 og går til de tilstøtende nodene. Siden 0 allerede er besøkt, besøker vi 2 i stedet.

Besøk elementet øverst på bunken

Vertex 2 har et ubesøkt tilstøtende toppunkt i 4, så vi legger til det på toppen av stabelen og besøker det.

Vertex 2 har et ubesøkt tilstøtende toppunkt i 4, så vi legger til det på toppen av stabelen og besøker det. Vertex 2 har et ubesøkt tilstøtende toppunkt i 4, så vi legger til det på toppen av stabelen og besøker det.

Etter at vi har besøkt det siste elementet 3, har det ingen ubesøkte tilstøtende noder, så vi har fullført dybden første gjennomgang av grafen.

Etter at vi har besøkt det siste elementet 3, har det ingen ubesøkte tilstøtende noder, så vi har fullført dybden første gjennomgang av grafen.

DFS Pseudokode (rekursiv implementering)

Pseudokoden for DFS er vist nedenfor. I init () -funksjonen, legg merke til at vi kjører DFS-funksjonen på hver node. Dette er fordi grafen kan ha to forskjellige frakoblede deler, for å sikre at vi dekker hvert toppunkt, kan vi også kjøre DFS-algoritmen på hver node.

 DFS (G, u) u.visited = true for hver v ∈ G.Adj (u) hvis v.visited == false DFS (G, v) init () (For hver u ∈ G u.visited = false for hver u ∈ G DFS (G, u))

DFS-implementering i Python, Java og C / C ++

Koden for Depth First Search Algorithm med et eksempel er vist nedenfor. Koden er forenklet slik at vi kan fokusere på algoritmen i stedet for andre detaljer.

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

Kompleksitet av dybde første søk

Tidskompleksiteten til DFS-algoritmen er representert i form av O(V + E), hvor Ver antall noder og Eer antall kanter.

Romkompleksiteten til algoritmen er O(V).

Anvendelse av DFS-algoritme

  1. For å finne stien
  2. Å teste om grafen er tosidig
  3. For å finne de sterkt koblede komponentene i en graf
  4. For å oppdage sykluser i en graf

Interessante artikler...