Để giải các bài toán trên đồ thị, chúng ta cần một cơ chế duyệt đồ thị. Giống như thuật toán duyệt cây (Inorder, Preorder, Postorder và Level-Order traverse), các thuật toán tìm kiếm đồ thị bắt đầu từ một số đỉnh nguồn trong đồ thị và tìm kiếm đồ thị bằng cách đi qua các cạnh và đánh dấu các đỉnh. Bây giờ, chúng ta sẽ thảo luận về thuật toán tìm kiếm theo chiều sâu (Depth First Search - DFS),
1. Giới thiệu
Tìm kiếm theo chiều sâu (DFS) là một thuật toán để duyệt qua hoặc tìm kiếm cấu trúc dữ liệu dạng cây hoặc đồ thị. Thuật toán bắt đầu tại nút gốc (chọn một số nút tùy ý làm nút gốc trong trường hợp đồ thị) và kiểm tra từng nhánh càng xa càng tốt trước khi quay lui.
Kết quả của một DFS là một cây bao trùm (spanning tree). Cây bao trùm (spanning tree) là một đồ thị không có vòng lặp. Để thực hiện duyệt theo DFS, chúng ta cần sử dụng cấu trúc dữ liệu ngăn xếp có kích thước tối đa bằng tổng số đỉnh trong biểu đồ.
2. Thuật toán
Để cài đặt DFS, ta cần thực hiện các bước sau:
- Lấy một đỉnh bất kỳ trong đồ thì đưa vào ngăn xếp.
- Lấy top value của ngăn xếp để duyệt và thêm vào visited list.
- Tạo một list bao gồm các đỉnh liền kề của đỉnh đang xét, thêm những đỉnh không có trong visited list vào ngăn xếp.
- Tiếp tục lặp lại bước 2 và bước 3 đến khi ngăn xếp rỗng.
Ví dụ:
Hãy xem thuật toán Tìm kiếm theo chiều sâu hoạt động như thế nào với một ví dụ. Chúng ta dùng đồ thị vô hướng có 5 đỉnh. Chúng ta 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 Visited và đưa tất cả các cạnh liền kề đỉnh đang xét vào ngăn xếp. Tiếp theo, chúng ta truy cập phần tử ở đầu 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, nên 2 là số được xét. Đỉnh 2 có một đỉnh liền kề chưa được thăm là 4, vì vậy chúng ta thêm đỉnh đó vào vị trí đầu của ngăn xếp và duyệt nó. Sau khi chúng ta duyệt 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 duyệt, vì vậy chúng tôi đã hoàn thành tìm kiếm theo chiều sâu trong đồ thị trên.
3. Cài đặt
// DFS algorithm in Java import java.util.*; class Graph { private LinkedList<Integer> 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<Integer>(); } // 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<Integer> 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); }
}
4. Độ phức tạp
Độ phức tạp thời gian của thuật toán DFS được biểu diễn dưới dạng O(V + E), trong đó V là số nút và E là số cạnh. Độ phức tạp không gian của thuật toán là O(V).
5. Ứng dụng
- Giải các câu đố mê cung.
- Tìm đường đi.
- Để kiểm tra xem đồ thi có phải là hai hướng.
- Phát hiện chu trình cho đồ thị