Algoritmus hloubkového prvního vyhledávání (DFS)

Obsah

Algoritmus vyhledávání prvního hloubky
Příklad vyhledávání hloubky
PFS pseudokód (rekurzivní implementace)
Implementace DFS v Pythonu, Javě a C / C ++
Složitost vyhledávání do hloubky
Aplikace DFS algoritmu

V tomto tutoriálu se dozvíte o algoritmu hloubkového vyhledávání s příklady a pseudokódem. Naučíte se také implementovat DFS v jazycích C, Java, Python a C ++.

Hledání hloubky první nebo Traverze hloubky první je rekurzivní algoritmus pro vyhledávání všech vrcholů datové struktury grafu nebo stromu. Traverz znamená navštívit všechny uzly grafu.

Algoritmus vyhledávání prvního hloubky

Standardní implementace DFS staví každý vrchol grafu do jedné ze dvou kategorií:

Navštíveno
Není navštěvováno

Účelem algoritmu je označit každý vrchol jako navštívený a vyhnout se cyklům.

Algoritmus DFS funguje následovně:

Začněte tím, že umístíte kterýkoli z vrcholů grafu na hromádku.
Vezměte horní položku zásobníku a přidejte ji do navštíveného seznamu.
Vytvořte seznam sousedních uzlů tohoto vrcholu. Přidejte ty, které nejsou v navštíveném seznamu, do horní části zásobníku.
Opakujte kroky 2 a 3, dokud není zásobník prázdný.

Příklad vyhledávání hloubky

Podívejme se, jak algoritmus hloubkového prvního vyhledávání funguje na příkladu. Používáme neorientovaný graf s 5 vrcholy.

Neusměrněný graf s 5 vrcholy

Začínáme od vrcholu 0, algoritmus DFS začíná vložením do seznamu Navštíveno a vložením všech jeho sousedních vrcholů do zásobníku.

Navštivte prvek a vložte jej do seznamu navštívených

Dále navštívíme prvek v horní části zásobníku, tj. 1 a přejdeme do jeho sousedních uzlů. Protože 0 již byla navštívena, navštěvujeme místo toho 2.

Navštivte prvek v horní části zásobníku

Vertex 2 má nenavštívený sousední vrchol v 4, takže ho přidáme do horní části zásobníku a navštívíme jej.

Poté, co jsme navštívili poslední prvek 3, nemá žádné nenavštívené sousední uzly, takže jsme dokončili procházení hloubky prvního grafu.

PFS pseudokód (rekurzivní implementace)

Pseudokód pro DFS je uveden níže. Ve funkci init () si všimněte, že na každém uzlu spustíme funkci DFS. Důvodem je, že graf může mít dvě různé odpojené části, abychom se ujistili, že pokryjeme každý vrchol, můžeme také spustit algoritmus DFS na každém uzlu.

 DFS (G, u) u.visited = true pro každý v ∈ G.Adj (u) if v.visited == false DFS (G, v) init () (Pro každý u ∈ G u.visited = false pro každý u ∈ G DFS (G, u))

Implementace DFS v Pythonu, Javě a C / C ++

Níže je uveden kód algoritmu hloubkového prvního vyhledávání s příkladem. Kód byl zjednodušen, takže se můžeme soustředit spíše na algoritmus než na další 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; )