Graph - Finde den von allen anderen Knoten erreichbaren Knoten

Question

Wie können wir anhand eines Graphen feststellen, ob es einen Knoten v gibt, von dem alle anderen Knoten erreichbar sind. Der Algorithmus sollte so effizient wie möglich sein.

Ich weiß, wie es geht, wenn wir nach einem gegebenen Eckpunkt suchen; Wir könnten dfs auf dem umgekehrten Graphen machen. Aber für diese Frage scheint es ineffizient, dies für jeden Knoten im Graphen zu tun.

Gibt es einen besseren Weg?

Danke.

Answer 1

Verwenden Sie Kosaraju's algorithm, um die stark verbundenen Komponenten des Graphen in der Zeit O(|V|+|E|) zu finden. Wenn Sie dann jede Komponente auf einen einzelnen Knoten "verkleinern", bleibt Ihnen ein gerichteter azyklischer Graph übrig. Es gibt einen Knoten, von dem aus alle anderen genau dann erreicht werden können, wenn es in der DAG genau einen Knoten mit Grad 0 gibt. Dies ist der gesuchte Knoten - der sogenannte "Mutterknoten".

Hinweis: Diese Antwort wurde ursprünglich mit Tarjans Algorithmus empfohlen. Tarjan ist wahrscheinlich ein bisschen schneller, aber es ist auch ein bisschen komplexer als Kosaraju.

Answer 2

Ich habe gerade den folgenden Algorithmus erfunden.

• Beginnen Sie mit einem beliebigen Eckpunkt und markieren Sie ihn als 'besucht'.
• Gehen Sie in dem Diagramm nach oben, um zu einem beliebigen übergeordneten Vertex zu gelangen, und markieren Sie es als "besucht".
• Behalten Sie die besuchten Scheitelpunkte auf einem Stapel im Auge.
• Wenn Sie einen Eckpunkt ohne übergeordnete Eckpunkte erreichen, prüfen Sie, ob es tatsächlich der Eckpunkt ist, von dem aus alle anderen Eckpunkte erreichbar sind.
• Beim Erreichen eines bereits besuchten Scheitelpunkts:
  1. Fügen Sie den besuchten Scheitelpunkt V dem Stapel nicht hinzu. Markieren Sie den vorherigen Eckpunkt als 'Ende' einer stark verbundenen Komponente.
  2. Gehen Sie den Stapel hinunter, bis Sie den bereits besuchten Vertex V erreichen. Entlang des Weges entfernen Sie alle 'Ende' und 'Start' Markierungen. Wenn die letzte entfernte Markierung eine "Start" -Markierung war, markieren Sie V als "Start", andernfalls markieren Sie nicht.
  3. Beginnen Sie erneut am Anfang des Stapels und gehen Sie nach unten, bis Sie einen Eckpunkt mit einem nicht besuchten Elternteil finden (und mit dem ersten Schritt des Algorithmus fortfahren) oder bis Sie den als 'Start' markierten Eckpunkt erreichen tatsächlich ein Mutterknoten, von dem alle anderen erreichbar sind.

Die Idee ist, dass, da jeder Scheitelpunkt von der Mutter Vertex erreichbar sein sollte, können wir nur nach oben einen beliebigen Weg nehmen, bis wir nicht mehr gehen kann.

So prüfen wir nur die stark verbundenen Komponenten, die den Startknoten erreichen können. In dem Fall, in dem viele stark zusammenhängende Komponenten mit Grad 0 vorliegen, wäre dies ein deutlicher Vorteil gegenüber Andys Algorithmus.

Answer 3

Die Lösung kann gefunden werden, indem das Konzept von Kosarajus Algorithmus für stark verbundene Komponenten verwendet wird.Die Idee basiert auf folgender Tatsache:

Wenn es einen Eckpunkt (oder Scheitelpunkte) gibt, von denen alle anderen Eckpunkte erreichbar sind, dann hätte dieser Eckpunkt die maximale Endzeit in einem DFS-Traversal. So , wäre die Lösung wie folgt aussehen:

// Utility function to find mother vertex 
//(vertex from which all other vertices are reachable) 

public void findMotherVertex() { 
    int motherVertex=0; 

    for (int i=0;i<G.V();i++) { //G.V() would return the no. of vertices in the graph 
     if (!marked[i]) { //marked - boolean array storing visited vertices 
      dfs(i); 
      motherVertex=i; 
     } 
    } 

    //Check for this vertex if all other vertices have been already visited 
    //Otherwise no mother vertex exists 

    for (int i=0;i<G.V();i++) { 
     if (!marked[i]) 
      return false; 
    } 

    System.out.println("Desired vertex is : " + motherVertex); 
} 

Der obige Algorithmus O (V + E) Zeit in Anspruch nimmt, das Problem zu lösen.