Tìm chu trình trong đồ thị vô hướng và tìm một chu trình trong đồ thị được hướng dẫn

Question

Vì vậy, tôi đang đọc Thuật toán của Robert Sedgewick lần thứ 4 ed. sách và các phương pháp để tìm một chu trình trong đồ thị được chỉ dẫn khác với một phương pháp để tìm một chu trình trong một đồ thị vô hướng.

Dưới đây là ví dụ mã để tìm thấy một chu kỳ trong một đồ thị vô hướng

public class Cycle { 
    public boolean[] marked; 
    public boolean hasCycle; 

    public Cycle(Graph G) { 
     marked = new boolean[G.V()]; // G.V() is the number of vertices in the graph G 
     for (int s = 0; s < G.V(); ++s) { 
     if (!marked[s]) 
      dfs(G, s, s); 
     } 
    } 

    private void dfs(Graph G, int v, int u) { 
     marked[v] = true; 
     for (int w : G.adj(v)) //iterate through vertices adjacent to v 
     if (!marked[w]) 
      dfs(G, w, v) 
     else if (w != u) hasCycle= true; 
    } 

    public boolean hasCycle() { 
     return hasCycle; 
    } 
} 

Tuy nhiên, khi cố gắng tìm một chu kỳ trong một đồ thị có hướng, Sedgewick sử dụng một mảng boolean nơi các yếu tố thứ i của mảng đó là sự thật nếu đỉnh thứ i đã được kiểm tra trong ngăn xếp cuộc gọi hiện tại. Đối với mỗi đỉnh K được kiểm tra, chúng ta kiểm tra xem phần tử K của mảng boolean có đúng không. Nếu có, thì chúng ta có một chu kỳ. Câu hỏi của tôi là, tại sao nó là cần thiết để sử dụng mảng boolean đó cho một đồ thị được chỉ dẫn. Phương pháp tiếp cận mà tôi vừa liệt kê có hiệu quả về bộ nhớ hơn không? Và cách tiếp cận này chỉ làm việc cho các đồ thị không bị chiếu xạ? tại sao?

Answer 1

Bạn không thể sử dụng cùng một thuật toán: Thuật toán ở trên chỉ khám phá tất cả các thành phần được kết nối của biểu đồ. Nếu bạn gặp phải một đỉnh đã được đánh dấu, phải có hai đường dẫn khác nhau để tiếp cận nó và trong một biểu đồ không giới hạn phải có một chu kỳ. Nếu không, bạn có thể tiếp tục với thành phần được kết nối tiếp theo - không cần dọn dẹp thành phần bạn vừa hoàn thành.

Mặt khác, nếu bạn có biểu đồ hướng dẫn , hai đường dẫn khác nhau đến cùng một đỉnh không tạo chu kỳ. Vì vậy, bạn cần một thuật toán khác (ví dụ, bạn có thể cần phải dọn sạch bất kỳ bước nào bạn theo dõi.)