Algoritem globine prvega iskanja (DFS)

Kazalo

Algoritem iskanja po globini
Primer globinskega iskanja
DFS Pseudocode (rekurzivna izvedba)
Implementacija DFS v Python, Java in C / C ++
Kompleksnost globinskega prvega iskanja
Uporaba algoritma DFS

V tej vadnici boste izvedeli več o algoritmu za iskanje globine s primeri in psevdokodo. Prav tako se boste naučili izvajati DFS v C, Java, Python in C ++.

Globina najprej iskanje ali Globina prva prehod je rekurzivni algoritem za iskanje vseh točk v grafu ali drevesni strukturi podatkov. Prehod pomeni obisk vseh vozlišč grafa.

Algoritem iskanja po globini

Standardna izvedba DFS uvrsti vsako oglišče grafa v eno od dveh kategorij:

Obiskano
Ni obiskan

Namen algoritma je označiti vsako oglišče kot obiskano, hkrati pa se izogniti ciklom.

Algoritem DFS deluje na naslednji način:

Začnite tako, da na vrh sklada postavite katero koli točko grafa.
Vzemite zgornji element sklada in ga dodajte na obiskani seznam.
Ustvarite seznam sosednjih vozlišč te točke. Tiste, ki niso na seznamu obiskanih, dodajte na vrh sklada.
Ponavljajte koraka 2 in 3, dokler se sklad ne izprazni.

Primer globinskega iskanja

Poglejmo, kako algoritem za globino prvega iskanja deluje na primeru. Uporabljamo neusmerjeni graf s 5 oglišči.

Neusmerjeni graf s 5 oglišči

Začnemo od točke 0, algoritem DFS se začne tako, da ga uvrstimo na seznam obiskanih in v sosednjo skladbo vstavimo vse njegove sosednje točke.

Obiščite element in ga dodajte na obiskani seznam

Nato obiščemo element na vrhu sklada, tj. 1, in pojdimo na sosednja vozlišča. Ker je 0 že obiskano, namesto tega obiščemo 2.

Obiščite element na vrhu sklada

Vertex 2 ima v 4 sosednjo točko, ki ni bila obiskana, zato jo dodamo na vrh sklada in jo obiščemo.

Po obisku zadnjega elementa 3 v njem ni nobenega neobiskanega sosednjega vozlišča, zato smo zaključili prehod globine prvega grafa.

DFS Pseudocode (rekurzivna izvedba)

Psevkodo za DFS prikazuje spodaj. V funkciji init () opazite, da zaženemo funkcijo DFS na vsakem vozlišču. To je zato, ker ima graf lahko dva različna dela, ki sta med seboj nepovezana, zato lahko zagotovimo, da pokrijemo vsako oglišče, lahko tudi algoritem DFS zaženemo na vsakem vozlišču.

 DFS (G, u) u.visited = true za vsak v ∈ G.Adj (u), če je v.visited == false DFS (G, v) init () (Za vsak u ∈ G u.visited = false u ∈ G DFS (G, u))

Implementacija DFS v Python, Java in C / C ++

Koda algoritma za globino prvega iskanja s primerom je prikazana spodaj. Koda je poenostavljena, tako da se lahko osredotočimo na algoritem in ne na druge 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; )