DFS stark verbunden Komponenten Dilemma

Frage: Teilen Sie die Menge der Ecken des Graphen in Problem 1 in stark verbundenen Komponenten (SCC). Spezifizieren Sie, welche Scheitelpunkte in der ersten stark verbundenen Komponente sind, welche in der zweiten, und so weiter.DFS stark verbunden Komponenten Dilemma

kann jemand bestätigen, dass dies korrekt gemacht wurde? wenn ich nämlich Punkt 4 erreiche, habe ich die Möglichkeit, den ersten SCC entweder 1,7,2,4,3 (wie gezeigt) oder 1,7,2,4,6,5 zu machen, je nachdem, auf welche Weise ich reise. Gibt es dafür eine Methode, oder kann ich einfach nur wählen?

Reihenfolge:

1,2,7,3,4,5,8,6

SCC:

1,7,2, 4,3

Quelle

2016-11-03 101ldaniels

Wrong noch weiß ist. Wie kommst du zu 4 von 7 ohne 3 zu passieren? {1,7,2,4,6,5} ist einfach kein SCC. Ich denke, der einzige SCC ist {1,2,3,4,5,6,7} – shole

@shole ja Entschuldigung, dass ich dfs auf umgekehrten Graphen zuerst nicht vorformte. so sind die stark verbundenen Komponenten 8 und 1,2,3,4,5,6,7 – 101ldaniels

Die stark verbundene Komponente ist {1,2,3,4,5,6,7}. Wenn Sie das nicht bekommen, hat Ihr Algorithmus (oder Ihre Implementierung) einen Fehler. Es gibt eine Definition der stark verbundenen Komponente und mehrere bekannte Algorithmen; beide können leicht in Wikipedia (und vielen anderen Internetquellen) gefunden werden und höchstwahrscheinlich in Ihren Lehrbuch- und/oder Kursnotizen. (Wenn Sie keine Kursnotizen haben, finden Sie leicht Kurse für ähnliche Kurse.)

Quelle

2016-11-03 03:05:57 rici

ahhh ja ich sehe. Ich habe dfs nicht zuerst auf umgekehrten Graphen vorgeformt. Prost! – 101ldaniels

Sie können 5 und 6 zu 1,7,2,4,3 hinzufügen, da beide von anderen über 4

erreichbar sind

In DFS Sie müssen visting Knoten weiter und Baum zu schaffen, während der Stapel wenn ja nicht leer ist, dann mit der niedrigsten ID restsrt die

Quelle

2016-11-03 03:09:38

DFS stark verbunden Komponenten Dilemma

Antwort

Verwandte Themen