THUẬT TOÁN DFS DÙNG STACK

     

Cấu trúc Graph (đồ thị) tất cả tập những đỉnh liên kết với nhau qua các cạnh. Depth First Search (DFS) là trong số những thuật toán có thể dùng để thông qua qua đồ vật thị.

Bạn đang xem: Thuật toán dfs dùng stack

Mục lục 2. Hiện thực 4. Đánh giá chỉ 1. Ý tưởng

Ý tưởng chừng như sau:

Từ một đỉnh, ta đi qua sâu vào cụ thể từng nhánh. Khi đã chú tâm hết nhánh của đỉnh, lùi lại để coi ngó đỉnh tiếp theo.Thuật toán dừng khi trải qua hết tất cả các đỉnh có thể đi qua.2. Hiện nay thực

Hai cách hiện thực tiếp sau đây được dùng cho cấu trúc Graph ở nội dung bài viết Tổng quan liêu về Đồ thị.

2.1. Đệ quy

Hiện thực theo phương pháp đệ quy khá dễ dàng và đơn giản và dễ hiểu. Ta yêu cầu dùng một mảng marked để bình chọn xem một đỉnh vẫn được thông qua qua chưa.

Đầu vào đề nghị một Graph với đỉnh nơi bắt đầu v. Quá trình như sau:

Đánh lốt điểm nơi bắt đầu v đã duyệt y qua.Lấy danh sách các đỉnh kề của v. Với từng đỉnh i:Nếu i chưa được duyệt qua thì lựa chọn i làm đỉnh gốc new và lặp lại thủ tục trên.

Code tham khảo:

DepthFirstSearch java

1234567891011121314151617

public class DepthFirstSearch private boolean<> marked; public DepthFirstSearch(Graph g, int v) // init vertex marked with default value false marked = new boolean; dfs(g, v); private void dfs(Graph g, int v) marked = true; for (int i : g.adj(v)) if (!marked) dfs(g, i); public boolean marked(int v) return marked;

2.2. Khử đệ quy

Với cách thức không dùng đệ quy, phương pháp hiện thực hơi phức hợp hơn chút. Hôm nay phải cần sử dụng một Stack để xét các đỉnh chưa duyệt.

Xem thêm: Loại Cây Ưa Nhiệt Thường Phân Bố Ở Vùng ? Loài Cây Ưa Nhiệt Thường Phân Bố Ở Vùng:

Đầu vào là một Graph với đỉnh gốc v. Công việc như sau:

Thêm đỉnh nơi bắt đầu vào stack.Lặp lại với đk stack ko rỗng:Lấy đỉnh ở đầu stack làm cho đỉnh vẫn xét.Nếu đỉnh đã xét đã được chăm sóc thì quăng quật qua. (*)Đánh vệt đỉnh sẽ xét là đỉnh đang duyệt.Lấy danh sách những đỉnh kề của đỉnh đã xét. Với mỗi đỉnh i:Nếu i không được duyệt qua thì đẩy i vào stack.

Code tham khảo:

DepthFirstSearch java

12345678910111213141516

private void dfs(Graph g, int v) Stack stack = new Stack(); stack.push(v); int currentVertex; while (!stack.isEmpty()) currentVertex = stack.pop(); if (marked) continue; marked = true; for (Integer i : g.adj(currentVertex)) if (!marked) stack.push(i);

(*) còn nếu không làm cách này, sẽ xẩy ra trường phù hợp một đỉnh chưa được duyệt được sản xuất stack các lần và hiệu quả là sẽ tiến hành duyệt qua nhiều lần.Kết quả coi sóc của cách thức khử đệ quy hoàn toàn có thể khác với phương pháp đệ quy do cấu trúc Stack hoạt động theo lý lẽ LIFO. Tức là thêm những đỉnh kề vào thì sẽ mang ra theo vật dụng tự ngược lại. Tuy nhiên, nó vẫn tuân theo nguyên tắc của DFS là cẩn thận sâu nhất có thể nên vẫn hòa hợp lệ.


3. Áp dụng

Bài toán: Cho đồ dùng thị g và đỉnh gốc s. Vấn đáp câu hỏi, gồm đường đi nào từ đỉnh cội s tới một đỉnh w nào đó không. Nếu như có, hãy tìm đường đi đó.

Xem thêm: Bản Nhận Xét Chuyển Đảng Chính Thức, Hỏi Về Thủ Tục Chuyển Đảng Chính Thức

Chúng ta sẽ dùng thuật toán DFS để chăm chú qua các đỉnh. Trong quá trình duyệt đó, gìn giữ đỉnh sớm nhất tới đỉnh a như thế nào đó áp dụng edgeTo<>.Nếu những đỉnh được để mắt tới qua vào marked<>, chứng tỏ có đường đi đến đỉnh kia và có thể truy hồi lại đường đi dùng edgeTo<>.

Code tham khảo:

DepthFirstPaths java

1234567891011121314151617181920212223242526272829

public class DepthFirstPaths private boolean<> marked; private int<> edgeTo; private int s; public DepthFirstPaths(Graph g, int s) marked = new boolean; edgeTo = new int; this.s = s; dfs(g, s); private void dfs(Graph g, int v) marked = true; for (Integer i : g.adj(v)) if (!marked) edgeTo = v; dfs(g, i); public boolean hasPathTo(int w) return marked; public Iterable pathTo(int w) if (!hasPathTo(w)) return null; LinkedList path = new LinkedList(); for (int i = w; i != s; i = edgeTo) path.addFirst(i); path.addFirst(s); return path;

Cùng phân tích với đồ vật thị sau đây:


*
Đồ thị 1

Viết hàm main nhằm test:

DepthFirstPaths java

12345678910111213141516

public static void main(String<> args) Graph g = new Graph(6); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(0, 3); g.addEdge(1, 4); g.addEdge(2, 4); g.addEdge(2, 5); DepthFirstPaths path = new DepthFirstPaths(g, 0); for (int i = 0; i rs = path.pathTo(i); System.out.println(rs); }

Kết quả là:

<0><0, 1><0, 1, 4, 2><0, 3><0, 1, 4><0, 1, 4, 2, 5>Và đường đi mà thuật toán cho hiệu quả là:


*
Đường đi mang đến Đồ thị 1

Có gì đấy sai sai đúng không nhỉ