Djup första sökning (DFS) algoritm

Innehållsförteckning

Djup första sökalgoritmen
Exempel på djup första sökning
DFS Pseudokod (rekursivt implementering)
DFS-implementering i Python, Java och C / C ++
Komplexitet av djup Första sökningen
Tillämpning av DFS-algoritm

I den här handledningen lär du dig om algoritmen för första sökning efter djup med exempel och pseudokod. Du lär dig också att implementera DFS i C, Java, Python och C ++.

Djup först sökning eller Djup första traversal är en rekursiv algoritm för att söka i alla hörn i en graf eller träddatastruktur. Traversal betyder att besöka alla noder i ett diagram.

Djup första sökalgoritmen

En standard DFS-implementering placerar varje toppunkt i diagrammet i en av två kategorier:

Besökta
Inte besökt

Syftet med algoritmen är att markera varje toppunkt som besökt medan man undviker cykler.

DFS-algoritmen fungerar enligt följande:

Börja med att placera någon av grafens hörn ovanpå en stack.
Ta stapelns överdel och lägg till den i den besökta listan.
Skapa en lista med toppunktens intilliggande noder. Lägg till de som inte finns i den besökta listan högst upp i stacken.
Fortsätt upprepa steg 2 och 3 tills stacken är tom.

Exempel på djup första sökning

Låt oss se hur Depth First Search-algoritmen fungerar med ett exempel. Vi använder en oriktad graf med 5 hörn.

Oriktad graf med 5 hörn

Vi börjar från vertex 0, DFS-algoritmen börjar med att placera den i listan Besökta och placera alla dess intilliggande hörn i stacken.

Besök elementet och lägg det i den besökta listan

Därefter besöker vi elementet högst upp på stapeln, dvs. 1 och går till dess intilliggande noder. Eftersom 0 redan har besökts besöker vi 2 istället.

Besök elementet högst upp på stacken

Vertex 2 har ett obesökt intilliggande toppunkt i 4, så vi lägger till det på toppen av stacken och besöker det.

Efter att vi har besökt det sista elementet 3 har det inga obesökta angränsande noder, så vi har slutfört djupets första genomgång i diagrammet.

DFS Pseudokod (rekursivt implementering)

Pseudokoden för DFS visas nedan. I init () -funktionen märker vi att vi kör DFS-funktionen på varje nod. Detta beror på att grafen kan ha två olika frånkopplade delar så att vi kan köra DFS-algoritmen på varje nod för att se till att vi täcker varje toppunkt.

 DFS (G, u) u.visited = true för varje v ∈ G.Adj (u) om v.visited == falsk DFS (G, v) init () (För varje u ∈ G u.visited = false för varje u ∈ G DFS (G, u))

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

Koden för Depth First Search Algorithm med ett exempel visas nedan. Koden har förenklats så att vi kan fokusera på algoritmen snarare än andra 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; )