Pertanyaan Bagaimana cara memeriksa apakah grafik yang diarahkan bersifat asiklik?


Bagaimana cara memeriksa apakah grafik yang diarahkan bersifat asiklik? Dan bagaimana algoritme disebut? Saya akan menghargai referensi.


75
2018-02-24 22:19


asal


Jawaban:


Saya akan mencoba urutkan grafik secara topologi, dan jika Anda tidak bisa, maka itu memiliki siklus.


83
2018-02-25 02:16



Melakukan pencarian kedalaman-pertama yang sederhana adalah tidak cukup baik untuk menemukan siklus. Dimungkinkan untuk mengunjungi node beberapa kali dalam DFS tanpa siklus yang ada. Bergantung pada tempat Anda memulai, Anda juga mungkin tidak mengunjungi seluruh grafik.

Anda dapat memeriksa siklus dalam komponen grafik yang terhubung sebagai berikut. Temukan node yang hanya memiliki ujung yang keluar. Jika tidak ada simpul seperti itu, maka ada siklus. Mulai DFS di simpul itu. Saat melintasi setiap sisi, periksa apakah ujung mengarah kembali ke simpul yang sudah ada di tumpukan Anda. Ini menunjukkan adanya siklus. Jika Anda tidak menemukan keunggulan seperti itu, tidak ada siklus dalam komponen yang terhubung itu.

Seperti yang ditunjukkan Rutger Prins, jika grafik Anda tidak terhubung, Anda perlu mengulang pencarian pada setiap komponen yang terhubung.

Sebagai acuan, Algoritma komponen yang sangat terhubung Tarjan terkait erat. Ini juga akan membantu Anda menemukan siklus, tidak hanya melaporkan apakah mereka ada.


32
2018-02-25 02:08



Lemma 22.11 di Buku Introduction to Algorithms (Edisi Kedua) menyatakan bahwa:

Sebuah graf berarah G adalah asiklik jika dan hanya jika pencarian kedalaman-kedalaman G menghasilkan tidak ada tepi belakang


12
2018-05-30 10:45



Solusi1Algoritma Kahn untuk memeriksa siklus. Gagasan utama: Mempertahankan antrian di mana node dengan nol dalam derajat akan ditambahkan ke dalam antrian. Kemudian kupas simpul satu per satu hingga antrian kosong. Periksa apakah ada ujung-ujung node yang ada.

Solusi2: Algoritma Tarjan untuk memeriksa komponen yang terhubung kuat.

Solution3: DFS. Gunakan integer array untuk menandai status node saat ini: yaitu 0 - artinya simpul ini belum pernah dikunjungi sebelumnya.      -1 - berarti node ini telah dikunjungi, dan node anak-anaknya sedang dikunjungi.      1 - berarti node ini telah dikunjungi, dan selesai. Jadi jika status node adalah -1 ketika melakukan DFS, itu berarti harus ada siklus.


5
2017-09-19 19:49



Solusi yang diberikan oleh ShuggyCoUk tidak lengkap karena mungkin tidak memeriksa semua node.


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

Ini memiliki timecomplexity O (n + m) atau O (n ^ 2)


1
2018-02-25 01:29



Saya tahu ini adalah topik lama tetapi bagi para pencari masa depan di sini adalah implementasi C # yang saya buat (tidak ada klaim yang paling efisien!). Ini dirancang untuk menggunakan bilangan bulat sederhana untuk mengidentifikasi setiap node. Anda dapat menghias bahwa bagaimanapun Anda suka memberikan hash objek simpul Anda dan sama dengan benar.

Untuk grafik yang sangat dalam, ini mungkin memiliki overhead yang tinggi, karena menciptakan hashset pada setiap node secara mendalam (mereka hancur lebarnya).

Anda memasukkan node dari mana Anda ingin mencari dan jalan mengambil ke node itu.

  • Untuk grafik dengan simpul akar tunggal Anda mengirim simpul itu dan hashset kosong
  • Untuk grafik yang memiliki beberapa simpul akar, Anda membungkus ini dalam foreach di atas node tersebut dan meneruskan hashset kosong baru untuk setiap iterasi
  • Saat memeriksa siklus di bawah node yang diberikan, cukup lewati node tersebut bersama dengan hashset kosong

    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;
    }
    

1
2017-10-24 17:47



Seharusnya tidak ada tepi belakang saat melakukan DFS.Jaga jejak node yang sudah dikunjungi saat melakukan DFS, jika Anda menemukan tepi antara node saat ini dan node yang ada, maka grafik memiliki siklus.


1
2017-10-28 05:14



di sini adalah kode cepat untuk menemukan apakah grafik memiliki siklus:

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)

Idenya adalah seperti ini: algoritma dfs normal dengan array untuk melacak node yang dikunjungi, dan array tambahan yang berfungsi sebagai penanda untuk node yang mengarah ke node saat ini, sehingga ketika kita menjalankan dfs untuk node kami mengatur item yang sesuai dalam array marker sebagai true, sehingga ketika node yang pernah dikunjungi ditemui, kami memeriksa apakah item yang sesuai dalam array marker benar, jika itu benar maka salah satu node yang membiarkan dirinya sendiri (maka siklus), dan triknya adalah setiap kali dfs dari node mengembalikan kita mengatur marker terkait kembali ke false, sehingga jika kita mengunjunginya lagi dari rute lain kita tidak tertipu.


1
2018-01-10 14:59



Berikut ini adalah implementasi ruby ​​saya tentang mengupas algoritme simpul daun.

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

0
2018-06-27 19:45