Алгоритм глибинного першого пошуку (DFS)

Зміст

Алгоритм пошуку глибини
Приклад пошуку глибини
DFS псевдокод (рекурсивна реалізація)
Впровадження DFS в Python, Java та C / C ++
Складність глибинного першого пошуку
Застосування алгоритму DFS

У цьому підручнику ви дізнаєтесь про алгоритм пошуку глибини спочатку із прикладами та псевдокодом. Крім того, ви навчитесь реалізовувати DFS на C, Java, Python та C ++.

Пошук глибини спочатку або обхід глибини - це рекурсивний алгоритм пошуку у всіх вершинах графіка або деревоподібної структури даних. Обхід означає відвідування всіх вузлів графіка.

Алгоритм пошуку глибини

Стандартна реалізація DFS включає кожну вершину графіка в одну з двох категорій:

Відвідав
Не відвідували

Мета алгоритму - позначити кожну вершину як відвідану, уникаючи циклів.

Алгоритм DFS працює наступним чином:

Почніть з того, що покладете будь-яку з вершин графа поверх стека.
Візьміть верхній елемент стека та додайте його до відвіданого списку.
Створіть список сусідніх вузлів цієї вершини. Додайте ті, яких немає в списку відвідуваних, у верх стека.
Продовжуйте повторювати кроки 2 і 3, поки стек не порожній.

Приклад пошуку глибини

Давайте подивимося, як працює алгоритм глибини пошуку на прикладі. Ми використовуємо неорієнтований графік з 5 вершинами.

Непрямий графік з 5 вершинами

Ми починаємо з вершини 0, алгоритм DFS починає з того, що поміщає його в список Відвіданих і поміщає всі сусідні вершини в стек.

Відвідайте елемент і внесіть його до списку відвідуваних

Далі ми відвідуємо елемент у верхній частині стека, тобто 1, і переходимо до сусідніх вузлів. Оскільки 0 вже відвідали, замість цього ми відвідуємо 2.

Відвідайте елемент у верхній частині стека

Вершина 2 має невідвідану сусідню вершину в 4, тому ми додаємо це у верх стека і відвідуємо його.

Після того, як ми відвідаємо останній елемент 3, він не має будь-яких невідвіданих сусідніх вузлів, тому ми завершили обхід глибини першого графіка.

DFS псевдокод (рекурсивна реалізація)

Псевдокод для DFS показаний нижче. У функції init () зауважте, що ми запускаємо функцію DFS на кожному вузлі. Це пояснюється тим, що графік може мати дві різні від’єднані частини, тому, щоб переконатися, що ми охоплюємо кожну вершину, ми також можемо запустити алгоритм DFS на кожному вузлі.

 DFS (G, u) u.visited = true для кожного v ∈ G.Adj (u), якщо v.visited == false DFS (G, v) init () (Для кожного u ∈ G u.visited = false Для кожного u ∈ G DFS (G, u))

Впровадження DFS в Python, Java та C / C ++

Код алгоритму глибинного першого пошуку з прикладом наведено нижче. Код був спрощений, так що ми можемо зосередитись на алгоритмі, а не на інших деталях.

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; )