Thuật toán tìm kiếm đầu tiên theo chiều sâu (DFS)

Mục lục

Thuật toán tìm kiếm đầu tiên theo chiều sâu
Ví dụ về tìm kiếm đầu tiên về độ sâu
Mã giả DFS (triển khai đệ quy)
Triển khai DFS bằng Python, Java và C / C ++
Độ phức tạp của Tìm kiếm đầu tiên về Độ sâu
Ứng dụng của thuật toán DFS

Trong hướng dẫn này, bạn sẽ tìm hiểu về thuật toán tìm kiếm theo chiều sâu với các ví dụ và mã giả. Ngoài ra, bạn sẽ học cách triển khai DFS trong C, Java, Python và C ++.

Độ sâu đầu tiên Tìm kiếm hoặc Độ sâu đầu tiên truyền qua là một thuật toán đệ quy để tìm kiếm tất cả các đỉnh của đồ thị hoặc cấu trúc dữ liệu cây. Traversal có nghĩa là truy cập tất cả các nút của biểu đồ.

Thuật toán tìm kiếm đầu tiên theo chiều sâu

Triển khai DFS tiêu chuẩn đặt mỗi đỉnh của biểu đồ thành một trong hai loại:

Đã đến thăm
Không được thăm

Mục đích của thuật toán là đánh dấu mỗi đỉnh là đã thăm trong khi tránh các chu kỳ.

Thuật toán DFS hoạt động như sau:

Bắt đầu bằng cách đặt bất kỳ một trong các đỉnh của biểu đồ lên trên một ngăn xếp.
Lấy mục trên cùng của ngăn xếp và thêm nó vào danh sách đã truy cập.
Tạo danh sách các nút liền kề của đỉnh đó. Thêm những cái không có trong danh sách đã truy cập vào đầu ngăn xếp.
Tiếp tục lặp lại các bước 2 và 3 cho đến khi ngăn xếp trống.

Ví dụ về tìm kiếm đầu tiên về độ sâu

Hãy xem cách hoạt động của thuật toán Tìm kiếm đầu tiên theo chiều sâu với một ví dụ. Chúng tôi sử dụng một đồ thị vô hướng với 5 đỉnh.

Đồ thị vô hướng với 5 đỉnh

Chúng tôi bắt đầu từ đỉnh 0, thuật toán DFS bắt đầu bằng cách đưa nó vào danh sách Đã thăm và đưa tất cả các đỉnh liền kề của nó vào ngăn xếp.

Truy cập phần tử và đưa nó vào danh sách đã truy cập

Tiếp theo, chúng tôi truy cập phần tử ở trên cùng của ngăn xếp tức là 1 và đi đến các nút liền kề của nó. Vì 0 đã được truy cập, chúng tôi truy cập 2 thay thế.

Truy cập phần tử ở đầu ngăn xếp

Đỉnh 2 có một đỉnh liền kề không được chờ đợi trong 4, vì vậy chúng tôi thêm đỉnh đó vào đầu ngăn xếp và truy cập nó.

Sau khi chúng tôi truy cập phần tử 3 cuối cùng, nó không có bất kỳ nút liền kề nào chưa được truy cập, vì vậy chúng tôi đã hoàn thành Giao tuyến đầu tiên theo chiều sâu của biểu đồ.

Mã giả DFS (triển khai đệ quy)

Mã giả cho DFS được hiển thị bên dưới. Trong hàm init (), lưu ý rằng chúng ta chạy hàm DFS trên mọi nút. Điều này là do biểu đồ có thể có hai phần không kết nối khác nhau, vì vậy để đảm bảo rằng chúng ta bao phủ mọi đỉnh, chúng ta cũng có thể chạy thuật toán DFS trên mọi nút.

 DFS (G, u) u.visited = true cho mỗi v ∈ G.Adj (u) if v.visited == false DFS (G, v) init () (Với mỗi u ∈ G u.visited = false Cho mỗi u ∈ G DFS (G, u))

Triển khai DFS bằng Python, Java và C / C ++

Mã cho Thuật toán tìm kiếm đầu tiên theo chiều sâu với một ví dụ được hiển thị bên dưới. Mã đã được đơn giản hóa để chúng ta có thể tập trung vào thuật toán hơn là các chi tiết khá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; )