Grafikalgorithmus Finden, ob Grafik verbunden ist, bipartite, hat Zyklus und ist ein Baum

  

überprüfe, ob es ist:

     

1. verbunden
  

Bei diesem Versuch versuchst du, den gesamten Graph von einem Punkt aus zu durchlaufen und zu sehen, ob du erfolgreich bist. Sowohl die Tiefen-zuerst-Traversierung als auch die Breiten-zuerst-Traversierung sind hier akzeptabel. Dieser Algorithmus teilt den Knoten in Komponenten auf:

• markiert alle Knoten als nicht besucht
• für jeden Knoten c , wenn dieser Knoten nicht besucht wurde
  • Erstellen Sie eine neue leere Gruppe von Knoten, die aktuelle Komponente
  • stellt den Knoten für traversal
  in die Warteschlange
  • , während ein Knoten t in der Warteschlange steht
    • Entferne diesen Knoten aus der Warteschlange
    • Markieren Sie jeden noch nicht besuchten Nachbarn als offen und fügen Sie ihn für traversal in die Warteschlange ein
    • markieren Sie diesen Knoten als durchlaufen
    • Fügen Sie diesen Knoten zur aktuellen Komponente
    hinzu
  • Schließen Sie die aktuelle Komponente und fügen Sie sie der Komponentengruppe
  hinzu

Wenn es nur eine Komponente gibt, ist das Diagramm verbunden.

Wenn eine Warteschlange verwendet wird, ist der Algorithmus eine Suche nach der Breite. Wenn ein Stapel verwendet wird, ist der Algorithmus eine Tiefensuche. Jede andere Sammlung mit den Push-und Pop-Any-Operationen tun. Von besonderem Interesse ist der Call-Stack: Ersetze "Enqueue for Traversal" durch "traverse rekursiv"

Für gerichtete Graphen gibt es zwei verwandte Konzepte: Ein gerichteter Graph ist schwach verbunden, wenn er unter Vernachlässigung aller Kantenrichtungen verbunden ist. Ein gerichteter Graph ist stark verbunden, wenn jeder Knoten von jedem Knoten aus erreichbar ist. Um auf starke Verbundenheit zu prüfen, genügt es zu überprüfen, dass jeder Knoten vom ersten Knoten aus nur mit Vorwärtsflanken erreichbar ist und jeder Knoten vom ersten Knoten aus nur mit Rückwärtsflanken erreichbar ist (der erste Knoten ist von jedem Knoten erreichbar).

  

1. zweigliedrig
  

Ein Graph ist zweigeteilt, wenn er zweifarbig ist. Versuchen Sie, eine Zweifarbigkeit zuzuweisen, und wenn Sie scheitern, ist die Grafik nicht zweigeteilt. Dies kann in den vorherigen Algorithmus integriert werden: Wenn Sie einen Knoten als offen markieren, weisen Sie ihm eine Farbe zu, die der Farbe des Nachbars t entspricht. Wenn ein Nachbar von t bereits geöffnet ist, überprüfen Sie seine Farbe. Wenn die Farbe dieselbe ist wie die von t , gibt es keine Zweifarbigkeit.

  

1. hat einen Zyklus
  

Dies ist einfach: Wenn Sie any Knoten beobachten, der bereits geöffnet ist, gibt es einen Zyklus. Beachten Sie, dass jeder Graph, der keinen Zyklus hat, zweigeteilt ist.

In gerichteten Graphen wird dies das Vorhandensein eines ungerichteten Zyklus erkennen. Verwenden Sie den folgenden (topologischen Sortier) Algorithmus, um das Vorhandensein von gerichteten Zyklen zu erkennen:

• während es einen Knoten mit dem Wert null gibt
  • fügt den Knoten zur topologischen Sortierung hinzu (irrelevant für die Erkennung von Zyklen)
  • Entferne den Knoten aus dem Graph
• wenn im Diagramm noch ein Knoten vorhanden ist
  • Der Graph enthält einen gerichteten Zyklus. In diesem Diagramm ist keine topologische Sortierung vorhanden.
• sonst
  • das Diagramm enthält keinen gerichteten Zyklus (ist azyklisch). Die generierte topologische Sortierung ist gültig.

  

1. Baum
  

Ein ungerichtetes Diagramm ist ein Baum, wenn es verbunden ist und keinen Zyklus enthält.

Ein gerichteter Graph ist ein gerooteter Baum, wenn er keine ungerichteten Zyklen hat und es nur einen Knoten mit einem Nullwert (nur eine Wurzel) gibt. Ein gerichteter Graph ist auch ein gerooteter Baum, wenn er verbunden ist, hat keine ungerichteten Zyklen und jeder Knoten mit einem Nullgrad von Null hat einen Wert von höchstens eins (jede Senke ist ein Blatt).