W tym samouczku dowiesz się o algorytmie wyszukiwania głębi z przykładami i pseudokodem. Nauczysz się również implementować DFS w językach C, Java, Python i C ++.
Najpierw głębokość Przeszukiwanie lub Głębokość pierwsze przejście to rekurencyjny algorytm przeszukiwania wszystkich wierzchołków wykresu lub struktury danych drzewa. Przechodzenie oznacza odwiedzanie wszystkich węzłów wykresu.
Algorytm wyszukiwania w głębi
Standardowa implementacja DFS umieszcza każdy wierzchołek wykresu w jednej z dwóch kategorii:
- Odwiedziłem
- Nie odwiedzono
Celem algorytmu jest oznaczenie każdego wierzchołka jako odwiedzonego z jednoczesnym unikaniem cykli.
Algorytm DFS działa w następujący sposób:
- Zacznij od umieszczenia dowolnego wierzchołka wykresu na szczycie stosu.
- Weź górny przedmiot ze stosu i dodaj go do listy odwiedzonych.
- Utwórz listę sąsiednich węzłów tego wierzchołka. Dodaj te, których nie ma na liście odwiedzonych, na górę stosu.
- Powtarzaj kroki 2 i 3, aż stos będzie pusty.
Przykład pierwszego wyszukiwania w głębi
Zobaczmy, jak działa algorytm wyszukiwania głębokości w pierwszej kolejności na przykładzie. Używamy nie skierowanego grafu z 5 wierzchołkami.
Nie skierowany graf z 5 wierzchołkami
Zaczynamy od wierzchołka 0, algorytm DFS zaczyna od umieszczenia go na liście Odwiedzonych i umieszczenia wszystkich sąsiednich wierzchołków na stosie.
Odwiedź element i umieść go na liście odwiedzonych
Następnie odwiedzamy element na szczycie stosu, czyli 1 i przechodzimy do jego sąsiednich węzłów. Ponieważ 0 zostało już odwiedzone, zamiast tego odwiedzamy 2.
Odwiedź element na szczycie stosu
Wierzchołek 2 ma nieodwiedzony sąsiedni wierzchołek w 4, więc dodajemy go na szczyt stosu i odwiedzamy.
Wierzchołek 2 ma nieodwiedzony sąsiedni wierzchołek w 4, więc dodajemy go na szczyt stosu i odwiedzamy go. 
Wierzchołek 2 ma nieodwiedzony sąsiedni wierzchołek w 4, więc dodajemy go na szczyt stosu i odwiedzamy.
Po odwiedzeniu ostatniego elementu 3 nie ma on żadnych nieodwiedzonych sąsiednich węzłów, więc zakończyliśmy przejście wykresu przez pierwszą głębokość.
Po odwiedzeniu ostatniego elementu 3 nie ma on żadnych nieodwiedzonych sąsiednich węzłów, więc zakończyliśmy przejście wykresu przez pierwszą głębokość.
Pseudokod DFS (rekurencyjna implementacja)
Pseudokod dla DFS jest pokazany poniżej. W funkcji init () zwróć uwagę, że uruchamiamy funkcję DFS na każdym węźle. Dzieje się tak, ponieważ graf może mieć dwie różne odłączone części, więc aby upewnić się, że pokryjemy każdy wierzchołek, możemy również uruchomić algorytm DFS na każdym węźle.
DFS (G, u) u.visited = true for each v ∈ G.Adj (u) if v.visited == false DFS (G, v) init () (For each u ∈ G u.visited = false For each u ∈ G DFS (G, u))
Implementacja DFS w Pythonie, Javie i C / C ++
Kod algorytmu wyszukiwania według głębokości wraz z przykładem pokazano poniżej. Kod został uproszczony, abyśmy mogli skupić się na algorytmie, a nie na innych szczegółach.
Python Java 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; )
Złożoność pierwszego wyszukiwania wgłębnego
Złożoność czasowa algorytmu DFS jest reprezentowana w postaci O(V + E), gdzie Vjest liczbą węzłów i Ejest liczbą krawędzi.
Złożoność przestrzenna algorytmu wynosi O(V).
Zastosowanie algorytmu DFS
- Za znalezienie ścieżki
- Aby sprawdzić, czy wykres jest dwudzielny
- Do znajdowania silnie powiązanych elementów grafu
- Do wykrywania cykli na wykresie
