Tatsächlich gibt es bereits einen Artikel über Habré zu diesem Algorithmus, der jedoch nicht den Beweis der Richtigkeit und einige Schritte des Algorithmus abdeckt. Ich habe beschlossen, eine Referenzversion dieses Artikels mit vollständiger Analyse zu erstellen.
Dieser Beitrag ist nützlich für Studenten der Disziplin "Algorithmen und Graphentheorie" sowie für diejenigen, die ihre Kenntnisse über Algorithmen in Graphen verbessern / auffrischen möchten.
Um den Algorithmus von Kosarayu zu verstehen, müssen Sie einige Konzepte der Graphentheorie kennen
Grundlegendes Konzept
Die Eckpunkte u, v werden als stark verbunden bezeichnet, wenn der Graph G einen Pfad (nicht unbedingt eine gerade Linie) enthält. U → v und v → u (Wir bezeichnen stark verbundene Eckpunkte mit u↔v)
Stark verbundene Komponenten sind stark verbundene Teilgraphen, die in Bezug auf den Einschluss maximal sind.
Invertieren des Diagramms - Ändern der Richtung aller Kanten im Diagramm in die entgegengesetzte Richtung (eine bidirektionale Kante bleibt selbst)
Invertieren eines Graphen - der Vorgang des Drehens von Kanten in die entgegengesetzte Richtung (eine bidirektionale Kante bleibt selbst)
Einige ziemlich offensichtliche Deckspelzen können angeführt werden:
1. Eine stark verbundene Komponente ist die Menge von Eckpunkten, die in der Menge von Zyklen enthalten sind,
die mindestens einen gemeinsamen Eckpunkt haben
2.
3. u ↔ v v ↔ w, u ↔ v ↔ w
4.
:
(DFS), «» . «», DFS ( ).
DFS
DFS .
DFS
, : : , :
DFS
( , , )
,
:
1:
'?'
DFS ( 2 , ; , , )
, - ( ) 1
, () ( ) -- DFS -- .
2:
3:
DFS, ,
DFS
3
, :
u v ⇔ DFS
:
⇒
u v G, ( 2), , .
⇐
u v . , r .
r 3 , 1 , u v. 2 :
r . u r v r ( 2). u v ( 3)
r , v. r v , r — ( , v , r, ). ( , ), , v r 3 ( )
, 1 2 , u v
O(V+E)
, , O(V+E) . ( )
, O(V+E)
, — O(V+E)
, O(V+E) .
, .
Zum Beispiel: Projizieren eines Transportnetzes auf ein Diagramm. Der Algorithmus hilft dabei, das neu erstellte Transportnetz auf die Erreichbarkeit jedes Scheitelpunkts von jedem Scheitelpunkt aus zu überprüfen (um sicherzustellen, dass es einen Pfad vom Stadtrand zur Mitte und zurück gibt).
Sie können das Kanalsystem in Gebäuden mit einem Algorithmus testen. Stromfluss in Halbleiterbauelementen
Sie können breiter denken: Wir projizieren das Kreislaufsystem eines Lebewesens, das Sie im Rahmen eines gentechnischen Projekts irgendwo im Jahr 2077 schaffen sollten. Der Algorithmus hilft Ihnen herauszufinden, ob Blut vom Herzen zu den Organen und zurück gelangt.