Thuật toán tốt nhất để phát hiện chu kỳ trong đồ thị được hướng dẫn

Question

Thuật toán hiệu quả nhất để phát hiện tất cả các chu kỳ trong biểu đồ được chỉ dẫn là gì?

Tôi có đồ thị được chỉ định biểu thị lịch công việc cần được thực thi, công việc là nút và phụ thuộc là một cạnh. Tôi cần phải phát hiện trường hợp lỗi của một chu kỳ trong biểu đồ này dẫn đến phụ thuộc theo chu kỳ.

Answer 1

Tarjan's strongly connected components algorithm có độ phức tạp thời gian là O(|E| + |V|).

Đối với các thuật toán khác, hãy xem Strongly connected components trên Wikipedia.

Answer 2

Cho rằng đây là lịch biểu công việc, tôi nghi ngờ rằng tại một thời điểm nào đó, bạn sẽ sắp xếp chúng vào một lệnh được thực hiện được đề xuất.

Nếu trường hợp đó xảy ra, thì việc thực hiện topological sort có thể xảy ra trong mọi trường hợp phát hiện chu kỳ. UNIX tsort chắc chắn không. Tôi nghĩ rằng có khả năng là do đó hiệu quả hơn để phát hiện các chu kỳ cùng một lúc như tsorting, chứ không phải trong một bước riêng biệt.

Vì vậy, câu hỏi có thể trở thành, "làm cách nào để hiệu quả nhất tsort", thay vì "cách tôi phát hiện các vòng lặp hiệu quả nhất". Mà câu trả lời có lẽ là "sử dụng một thư viện", nhưng không có bài viết sau Wikipedia:

http://en.wikipedia.org/wiki/Topological_sorting

có giả mã cho một thuật toán, và một mô tả ngắn gọn của người khác từ Tarjan . Cả hai đều có độ phức tạp thời gian O(|V| + |E|).

Answer 3

Nếu bạn không thể thêm thuộc tính "đã truy cập" vào nút, hãy sử dụng tập hợp (hoặc bản đồ) và chỉ cần thêm tất cả các nút đã truy cập vào nhóm trừ khi chúng đã có trong tập hợp. Sử dụng một khóa duy nhất hoặc địa chỉ của các đối tượng là "chìa khóa".

Điều này cũng cung cấp cho bạn thông tin về nút "gốc" của phụ thuộc theo chu kỳ sẽ hữu ích khi người dùng phải khắc phục sự cố.

Một giải pháp khác là cố gắng tìm sự phụ thuộc tiếp theo để thực thi. Đối với điều này, bạn phải có một số ngăn xếp, nơi bạn có thể nhớ bạn đang ở đâu và những gì bạn cần làm tiếp theo. Kiểm tra xem phụ thuộc đã có trên ngăn xếp này chưa trước khi bạn thực hiện nó. Nếu có, bạn đã tìm thấy một chu kỳ.

Trong khi điều này có vẻ phức tạp của O (N * M), bạn phải nhớ rằng ngăn xếp có độ sâu rất hạn chế (vì vậy N nhỏ) và M trở nên nhỏ hơn với mỗi phụ thuộc mà bạn có thể kiểm tra "thực hiện" cộng với bạn có thể ngừng tìm kiếm khi bạn tìm thấy một chiếc lá (vì vậy bạn không bao giờ phải kiểm tra mọi nút -> M cũng sẽ nhỏ).

Trong MetaMake, tôi đã tạo biểu đồ dưới dạng danh sách các danh sách và sau đó xóa mọi nút khi tôi thực hiện chúng, điều này sẽ tự động cắt giảm lượng tìm kiếm. Tôi không bao giờ thực sự phải chạy một kiểm tra độc lập, tất cả đều xảy ra tự động trong quá trình thực hiện bình thường.

Nếu bạn cần chế độ "chỉ thử nghiệm", chỉ cần thêm cờ "chạy khô" để vô hiệu hóa việc thực hiện các công việc thực tế.

Answer 4

Cách tôi làm điều đó là thực hiện Phân loại tôpô, đếm số lượng đỉnh truy cập. Nếu số đó nhỏ hơn tổng số đỉnh trong DAG, bạn có chu kỳ.

Answer 5

Cách đơn giản nhất để thực hiện việc này là thực hiện chuyển tiếp độ sâu đầu tiên (DFT) của biểu đồ.

Nếu biểu đồ có n đỉnh, đây là thuật toán phức tạp thời gian O(n). Vì bạn có thể phải làm một DFT bắt đầu từ mỗi đỉnh, tổng độ phức tạp trở thành O(n^2).

Bạn phải duy trì ngăn xếp chứa tất cả các đỉnh ở độ sâu hiện tại đầu tiên theo chiều ngang, với phần tử đầu tiên là nút gốc. Nếu bạn gặp một phần tử đã có trong ngăn xếp trong DFT, thì bạn có một chu trình.

Answer 6

Nếu một đồ thị đáp ứng sở hữu

|e| > |v| - 1 

này sau đó đồ thị chứa ít nhất là trên chu kỳ.

Answer 7

Bắt đầu với DFS: chu kỳ tồn tại nếu và chỉ khi một cạnh sau được phát hiện trong DFS. Điều này được chứng minh là kết quả của lý thuyết đường trắng.

Answer 8

Tôi đã triển khai vấn đề này trong sml (chương trình bắt buộc). Đây là phác thảo. Tìm tất cả các nút có hoặc không rõ ràng hoặc vượt quá 0. Các nút như vậy không thể là một phần của chu trình (vì vậy hãy loại bỏ chúng). Tiếp theo loại bỏ tất cả các cạnh đến hoặc đi từ các nút như vậy. đệ quy áp dụng quy trình này cho biểu đồ kết quả. Nếu ở cuối bạn không bị bỏ lại với bất kỳ nút hoặc cạnh nào, biểu đồ không có bất kỳ chu kỳ nào, nếu không nó sẽ có.

Answer 9

https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length Tôi thích giải pháp này là tốt nhất đặc biệt cho 4 chiều dài :)

thuật sĩ cũng Phys nói u phải làm O (V^2). Tôi tin rằng chúng ta chỉ cần O (V)/O (V + E). Nếu đồ thị được kết nối thì DFS sẽ truy cập tất cả các nút. Nếu đồ thị đã kết nối đồ thị phụ sau đó mỗi khi chúng ta chạy một DFS trên một đỉnh của đồ thị phụ này, chúng ta sẽ tìm thấy các đỉnh được kết nối và sẽ không phải xem xét chúng cho lần chạy tiếp theo của DFS. Do đó khả năng chạy cho mỗi đỉnh là không chính xác.

Answer 10

Không có thuật toán nào có thể tìm thấy tất cả các chu kỳ trong đồ thị được chỉ dẫn trong thời gian đa thức. Giả sử, đồ thị được chỉ dẫn có n nút và mỗi cặp của các nút có các kết nối với nhau có nghĩa là bạn có một biểu đồ hoàn chỉnh. Vì vậy, bất kỳ tập con không trống nào của các nút n này chỉ ra một chu kỳ và có 2^n-1 số tập hợp con như vậy. Vì vậy, không tồn tại thuật toán thời gian đa thức. Giả sử bạn có thuật toán hiệu quả (không ngu ngốc) có thể cho bạn biết số chu kỳ được chỉ dẫn trong biểu đồ, trước tiên bạn có thể tìm thấy các thành phần được kết nối mạnh, sau đó áp dụng thuật toán của bạn trên các thành phần được kết nối này. Vì chu trình chỉ tồn tại trong các thành phần chứ không tồn tại giữa chúng.

Answer 11

Nếu DFS tìm thấy một cạnh trỏ đến đỉnh đã truy cập, bạn có chu kỳ tại đó.

Answer 12

Theo tôi, thuật toán dễ hiểu nhất để phát hiện chu trình trong đồ thị được chỉ dẫn là đồ thị-màu-thuật toán. Về cơ bản, thuật toán tô màu đồ thị chuyển đồ thị theo cách DFS (Độ sâu Tìm kiếm Thứ nhất, có nghĩa là nó khám phá một đường dẫn hoàn toàn trước khi khám phá một đường dẫn khác). Khi nó tìm thấy một cạnh sau, nó đánh dấu đồ thị có chứa một vòng lặp.

Đối với một chiều sâu giải thích về các thuật toán đồ thị màu, hãy đọc bài viết này: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Ngoài ra, tôi cung cấp một thực hiện tô màu đồ thị trong JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Answer 13

Như bạn nói, bạn đã thiết lập công việc , nó cần phải được thực hiện theo thứ tự nhất định. Topological sort cho bạn thứ tự yêu cầu để lên lịch công việc (hoặc cho các vấn đề phụ thuộc nếu nó là direct acyclic graph). Chạy dfs và duy trì một danh sách và bắt đầu thêm nút vào đầu danh sách và nếu bạn gặp phải một nút đã được truy cập. Sau đó, bạn tìm thấy một chu kỳ trong đồ thị nhất định.

Answer 14

//this is better solution in java- 

` 

class Package{ 
    private List<Package> dep; 
    private String name; 
    boolean visited; 
    List<Package> getDependencies(){ 
     return this.dep; 
    } 
    String getName(){} 


    public void getBuildOrder(Package p){ 
     p.visited=true; 
     if(p.getDependencies.size()==0) syso(p.getName()); 
     for(Package p1 : p.getDependencies){ 
      if(p1.visited) { 
       syso("cyclic dependency"); 
       return; 
      } 
      getBuildOrder(p1); 

     } 

    } 
    main(){ 
     Package p = new Package(); 
     // this p i having all infor 
     getBuildOrder(p); 
    } 
} 


`