DAG - Algorithmus, um sicherzustellen, dass es eine einzige Quelle und eine einzige Senke gibt

Question

Ich muss sicherstellen, dass ein Diagramm in unserer Anwendung eine DAG mit einer eindeutigen Quelle und einer eindeutigen Senke ist.

Insbesondere muss ich sicherstellen, dass für einen Startknoten und einen Endknoten (beide sind von Anfang an bekannt) jeder Knoten im Graphen auf einem Pfad vom Startknoten zum Endknoten liegt.

Ich habe bereits eine Implementierung von Tarjans Algorithmus, mit dem ich Zyklen identifiziere, und einen topologischen Sortieralgorithmus, den ich ausführen kann, sobald Tarjans Algorithmus den Graphen als DAG meldet.

Was ist der effizienteste Weg, um sicherzustellen, dass der Graph dieses Kriterium erfüllt?

Answer 1

Wenn Ihr Graph durch eine Adjazenzmatrix repräsentiert wird, dann ist Knoten x ein Quellknoten, wenn die xte Spalte der Matrix 0 ist und ein Senkenknoten, wenn Zeile x der Matrix 0 ist. Sie könnten zwei schnelle Durchgänge ausführen über die Matrix, um die Anzahl der Zeilen und Spalten zu zählen, die 0 sind, um zu bestimmen, wie viele Quellen und Senken existieren und was sie sind. Dies benötigt Zeit O (n) und ist wahrscheinlich der schnellste Weg, dies zu überprüfen.

Wenn Ihr Graph durch eine Adjazenzliste dargestellt wird, können Sie alle Senkenknoten in der Zeit O (n) finden, indem Sie prüfen, ob ein Knoten keine ausgehenden Kanten hat. Sie können alle Senken finden, indem Sie für jeden Knoten einen booleschen Wert beibehalten, der angibt, ob er ankommende Kanten hat, was zunächst falsch ist. Sie können dann über alle Kanten in der Liste in der Zeit I (n + m) iterieren, indem Sie alle Knoten mit eingehenden Kanten markieren. Die Knoten, die nicht als eingehende Kanten markiert waren, sind dann Quellen. Dieser Prozess benötigt Zeit O (m + n) und hat so wenig Overhead, dass es wahrscheinlich einer der schnellsten Ansätze ist.

Hoffe, das hilft!

Answer 2

Eine einfache Breiten- oder Tiefensuche sollte dies erfüllen. Erstens können Sie eine Gruppe von Knoten beibehalten, die Senkenknoten enthalten, die Sie gesehen haben. Zweitens können Sie eine Gruppe von Knoten behalten, die Sie mithilfe von BFS/DFS entdeckt haben. Dann wird das Diagramm verbunden, wenn es eine einzige verbundene Komponente gibt. Vorausgesetzt, dass Sie irgendeine Art von Adjazenzliste Stil Darstellung für Ihr Diagramm verwenden, würde der Algorithmus wie folgt aussehen:

create an empty queue 
create an empty set to store seen vertices 
create an empty set for sink nodes 

add source node to queue 

while queue is not empty 
    get next vertex from queue, add vertex to seen vertices 
    if num of adjacent nodes == 0 
     add sink nodes to sink node set 
    else 
     for each node in adjacent nodes 
     if node is not in seen vertices 
      add node to queue 

return size of sink nodes == 1 && size of seen vertices == total number in graph 

Dies wird linear in der Anzahl der Ecken und Kanten im Graph.

Beachten Sie, dass auch dann, wenn Sie einen Quellknoten kennen, der die Eigenschaft einer einzelnen Quelle sichert: jeder andere Vertex, der eine Quelle ist, wird vom BFS/DFS nicht erkannt Die Größe der sichtbaren Scheitelpunkte entspricht nicht der Gesamtzahl im Diagramm.

Answer 3

Wenn Ihr Algorithmus eine DAG verwendet, die schwach verbunden ist, nehmen Sie an, dass es nur einen Knoten s gibt, dessen In-Grad Null ist und nur ein Knoten t, dessen Out-Grad Null ist, während alle anderen Knoten positiv sind In-Grad und Out-Grad, dann kann s alle anderen Knoten erreichen, und alle anderen Knoten können t erreichen. Nehmen Sie im Widerspruch an, dass es einen Knoten v gibt, den s nicht erreichen kann. Da keine Knoten s erreichen können, kann v auch s nicht erreichen. Damit sind v und s getrennt, was der Annahme widerspricht. Auf der anderen Seite, wenn die DAG nicht schwach verbunden ist, erfüllt es definitiv nicht die Anforderungen, die Sie wollen. Zusammenfassend kann man die schwach verbundene Komponente der DAG zuerst einfach mit BFS/DFS berechnen und dabei die Anzahl der Knoten berücksichtigen, deren In-Grad oder Out-Grad Null ist. Die Komplexität dieses Algorithmus ist O (| E |).

Answer 4

Zuerst machen Sie ein DFS auf dem Graph, beginnend mit dem Quellknoten, der, wie Sie sagen, im Voraus bekannt ist. Wenn Sie auf eine Back Edge [1] stoßen, haben Sie einen Zyklus und Sie können mit einem Fehler beenden.Während dieser Durchquerung können Sie feststellen, ob Knoten vorhanden sind, die nicht von der Quelle [2] aus erreichbar sind, und die entsprechenden Maßnahmen ergreifen.

Sobald Sie die grafische Darstellung festgestellt haben, ein DAG ist, kann sichergestellt werden, dass jeder Knoten auf einem Pfad durch einen anderen DFS von der Quelle zur Senke liegt, von der Quelle ausgehend, wie folgt:

bool have_path(source, sink) { 
    if source == sink { 
     source.flag = true 
     return true 
    } 

    // traverse all successor nodes of `source` 
    for dst in succ(source) { 
     if not dst.flag and not have_path(dst, sink) 
      return false // exit as soon as we find a node with no path to `sink` 
    } 
    source.flag = true; 
    return true 
} 

The Prozedur have_path legt einen booleschen flag in jedem Knoten fest, für den ein Pfad von diesem Knoten zu der Senke existiert. Zur gleichen Zeit durchläuft die Prozedur nur Knoten, die von der Quelle erreichbar sind, und sie durchquert alle Knoten, die von der Quelle erreichbar sind. Wenn die Prozedur wahr zurückgibt, dann liegen alle Knoten, die von der Quelle erreichbar sind, auf einem Pfad zu der Senke. Nicht erreichbare Knoten wurden bereits in der ersten Phase behandelt.

---

[1] eine Kante, einen Knoten mit einer größeren DFS-Nummer zu einem Knoten mit einer geringeren DFS Nummer verknüpft, dass nicht bereits vollständig abgearbeitet, also noch immer auf der DFS-Stack

[2 ] z.B sie hätten keine zugewiesene DFS-Nummer