I denne vejledning lærer du om dybde førstesøgningsalgoritme med eksempler og pseudokode. Du lærer også at implementere DFS i C, Java, Python og C ++.
Dybde første søgning eller Dybde første gennemgang er en rekursiv algoritme til søgning i alle hjørnerne i en graf eller træstatastruktur. Traversal betyder at besøge alle noder i en graf.
Dybde første søgning algoritme
En standard DFS-implementering placerer hvert toppunkt i grafen i en af to kategorier:
- Besøgt
- Ikke besøgt
Formålet med algoritmen er at markere hvert toppunkt som besøgt, mens man undgår cyklusser.
DFS-algoritmen fungerer som følger:
- Start med at placere en af grafens hjørner oven på en stak.
- Tag det øverste element i stakken og føj det til den besøgte liste.
- Opret en liste over toppunktets tilstødende noder. Tilføj dem, der ikke er på den besøgte liste, til toppen af stakken.
- Gentag trin 2 og 3, indtil stakken er tom.
Eksempel på dybde første søgning
Lad os se, hvordan Depth First Search-algoritmen fungerer med et eksempel. Vi bruger en ikke-rettet graf med 5 hjørner.
Ustyret graf med 5 hjørner
Vi starter fra toppunkt 0, DFS-algoritmen starter med at placere den i listen Besøgte og placere alle dens tilstødende hjørner i stakken.
Besøg elementet og placer det på den besøgte liste
Dernæst besøger vi elementet øverst på stakken, dvs. 1 og går til dets tilstødende noder. Da 0 allerede er besøgt, besøger vi 2 i stedet.
Besøg elementet øverst på stakken
Vertex 2 har et ubesøgt tilstødende toppunkt i 4, så vi tilføjer det til toppen af stakken og besøger det.
Vertex 2 har et ubesøgt tilstødende toppunkt i 4, så vi tilføjer det til toppen af stakken og besøger det. 
Vertex 2 har et ubesøgt tilstødende toppunkt i 4, så vi tilføjer det til toppen af stakken og besøger det.
Efter at vi har besøgt det sidste element 3, har det ingen ubesøgte tilstødende noder, så vi har gennemført dybden første gennemgang af grafen.
Efter at vi har besøgt det sidste element 3, har det ingen ubesøgte tilstødende noder, så vi har gennemført dybden første gennemgang af grafen.
DFS Pseudocode (rekursiv implementering)
Pseudokoden til DFS er vist nedenfor. I funktionen init () skal du bemærke, at vi kører DFS-funktionen på hver node. Dette skyldes, at grafen måske har to forskellige frakoblede dele, så for at sikre, at vi dækker hvert toppunkt, kan vi også kø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 til den dybde første søgningsalgoritme med et eksempel er vist nedenfor. Koden er blevet forenklet, så vi kan fokusere på algoritmen snarere end 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 af dybde første søgning
Tidskompleksiteten af DFS-algoritmen er repræsenteret i form af O(V + E), hvor Ver antallet af noder og Eer antallet af kanter.
Rummets kompleksitet af algoritmen er O(V).
Anvendelse af DFS-algoritme
- For at finde stien
- At teste, om grafen er toparts
- Til at finde de stærkt forbundne komponenter i en graf
- Til detektion af cyklusser i en graf
