Làm cách nào để kiểm tra xem biểu đồ có đạo diễn có tuần hoàn không?

Question

Làm cách nào để kiểm tra xem biểu đồ được chỉ định có theo chu kỳ không? Và thuật toán được gọi là gì? Tôi sẽ đánh giá cao một tham chiếu.

Answer 1

Tôi sẽ cố gắng sort the graph topologically và nếu bạn không thể, thì nó có chu kỳ.

Answer 2

Giải pháp được đưa ra bởi ShuggyCoUk là không đầy đủ vì nó có thể không kiểm tra tất cả các nút.

def isDAG(nodes V): 
    while there is an unvisited node v in V: 
     bool cycleFound = dfs(v) 
     if cyclefound: 
      return false 
    return true 

này có timecomplexity O (n + m) hoặc O (n^2)

Answer 3

Làm một đơn giản sâu-đầu-tìm kiếm được không đủ tốt để tìm một chu kỳ. Có thể truy cập một nút nhiều lần trong một DFS mà không có chu kỳ tồn tại. Tùy thuộc vào nơi bạn bắt đầu, bạn cũng có thể không truy cập toàn bộ biểu đồ.

Bạn có thể kiểm tra chu kỳ trong thành phần được kết nối của biểu đồ như sau. Tìm một nút chỉ có các cạnh đi. Nếu không có nút như vậy, thì có một chu kỳ. Bắt đầu một DFS tại nút đó. Khi di chuyển qua từng cạnh, kiểm tra xem cạnh có trỏ trở lại một nút đã có trên ngăn xếp của bạn hay không. Điều này cho thấy sự tồn tại của một chu kỳ. Nếu bạn không tìm thấy cạnh như vậy, không có chu kỳ trong thành phần được kết nối đó.

Khi Rutger Prins chỉ ra, nếu đồ thị của bạn không được kết nối, bạn cần lặp lại tìm kiếm trên từng thành phần được kết nối.

Để tham khảo, Tarjan's strongly connected component algorithm có liên quan chặt chẽ. Nó cũng sẽ giúp bạn tìm thấy các chu kỳ, không chỉ báo cáo cho dù chúng tồn tại.

Answer 4

Bổ đề 22.11 trên Sách Introduction to Algorithms (Second Edition) cho rằng:

Một đạo diễn đồ thị G là acyclic khi và chỉ khi một tìm kiếm theo chiều sâu của G mang lại không trở lại cạnh

Answer 5

Tôi biết đây là một chủ đề cũ nhưng đối với những người tìm kiếm trong tương lai, đây là một triển khai C# mà tôi đã tạo (không có tuyên bố rằng nó hiệu quả nhất!). Điều này được thiết kế để sử dụng một số nguyên đơn giản để xác định mỗi nút. Bạn có thể trang trí mà tuy nhiên bạn muốn cung cấp băm đối tượng nút của bạn và bằng đúng cách.

Đối với đồ thị rất sâu, điều này có thể có chi phí cao, vì nó tạo ra một hashset ở mỗi nút sâu (chúng bị phá hủy trên bề rộng).

Bạn nhập nút mà bạn muốn tìm kiếm và đường dẫn đến nút đó.

• Đối với một đồ thị với một nút gốc duy nhất bạn gửi mà nút và một HashSet trống
• Đối với một đồ thị có nhiều nút gốc bạn quấn này trong foreach qua những nút và vượt qua một HashSet trống mới cho mỗi lần lặp

• Khi kiểm tra cho chu kỳ dưới bất kỳ nút nào đó, chỉ cần vượt qua nút đó cùng với một HashSet trống

  private bool FindCycle(int node, HashSet<int> path) 
  { 
  
      if (path.Contains(node)) 
       return true; 
  
      var extendedPath = new HashSet<int>(path) {node}; 
  
      foreach (var child in GetChildren(node)) 
      { 
       if (FindCycle(child, extendedPath)) 
        return true; 
      } 
  
      return false; 
  } 
  

Answer 6

đây là implemen ruby ​​của tôi tation của peel off leaf node algorithm.

def detect_cycles(initial_graph, number_of_iterations=-1) 
    # If we keep peeling off leaf nodes, one of two things will happen 
    # A) We will eventually peel off all nodes: The graph is acyclic. 
    # B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic. 
    graph = initial_graph 
    iteration = 0 
    loop do 
     iteration += 1 
     if number_of_iterations > 0 && iteration > number_of_iterations 
      raise "prevented infinite loop" 
     end 

     if graph.nodes.empty? 
      #puts "the graph is without cycles" 
      return false 
     end 

     leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? } 

     if leaf_nodes.empty? 
      #puts "the graph contain cycles" 
      return true 
     end 

     nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) } 
     edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) } 
     graph = Graph.new(nodes2, edges2) 
    end 
    raise "should not happen" 
end 

Answer 7

Solution1: thuật toán Kahn để kiểm tra chu kỳ. Ý tưởng chính: Duy trì một hàng đợi trong đó nút có số không ở mức độ sẽ được thêm vào hàng đợi. Sau đó bóc từng nút một cho đến khi hàng đợi trống. Kiểm tra xem có bất kỳ nút nào trong các cạnh không.

Solution2: Thuật toán Tarjan để kiểm tra Linh kiện kết nối mạnh.

Solution3: DFS. Sử dụng mảng số nguyên để gắn thẻ trạng thái hiện tại của nút: tức là 0 - có nghĩa là nút này chưa được truy cập trước đây. -1 - có nghĩa là nút này đã được truy cập và các nút con của nó đang được truy cập. 1 - có nghĩa là nút này đã được truy cập và đã hoàn tất. Vì vậy, nếu trạng thái của nút là -1 trong khi thực hiện DFS, điều đó có nghĩa là phải có một chu kỳ tồn tại.

Answer 8

Không có bất kỳ cạnh sau nào khi thực hiện DFS.Kiểm tra các nút đã truy cập trong khi thực hiện DFS, nếu bạn gặp phải một cạnh giữa nút hiện tại và nút hiện có, thì biểu đồ có chu kỳ.

Answer 9

đây là một mã nhanh chóng để tìm thấy nếu một đồ thị có chu kỳ:

func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool 
{ 

    if(breadCrumb[root] == true) 
    { 
     return true; 
    } 

    if(visited[root] == true) 
    { 
     return false; 
    } 

    visited[root] = true; 

    breadCrumb[root] = true; 

    if(G[root] != nil) 
    { 
     for child : Int in G[root]! 
     { 
      if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb)) 
      { 
       return true; 
      } 
     } 
    } 

    breadCrumb[root] = false; 
    return false; 
} 


let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]]; 

var visited = [false,false,false,false,false,false,false,false,false]; 
var breadCrumb = [false,false,false,false,false,false,false,false,false]; 




var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb) 

Ý tưởng là như thế này: một dfs thuật toán bình thường với một mảng để theo dõi các nút truy cập, và một mảng bổ sung mà phục vụ như là điểm đánh dấu cho các nút dẫn đến nút hiện tại, để khi chúng ta thực thi dfs cho nút, chúng tôi đặt mục tương ứng trong mảng đánh dấu là true, để khi có nút đã truy cập, chúng tôi kiểm tra xem nó có tương ứng hay không mục trong mảng đánh dấu là true, nếu đúng thì đó là một trong các nút cho chính nó (do đó một chu kỳ), và thủ thuật là bất cứ khi nào một dfs của một nút trả về, chúng ta đặt dấu tương ứng của nó trở lại để sai, để nếu chúng ta ghé thăm nó một lần nữa từ một con đường khác chúng ta không bị lừa.