9.6 Zusammenhangskomponente

Gegeben: Ungerichteter, ungewichteter Graph G = (V,E)

Gesucht: Zusammenhangskomponenten, d.h. zhk[i] = j, falls Knoten i sich in der j -ten Zusammenhangskomponente befindet.

1. Möglichkeit: Berechne transitive Hülle.

huell[i,j]= 1 $\Leftrightarrow$ es gibt Weg von i nach j .
Sei A die (boole'sche) Adjazenzmatrix.
Dann bilde A ^j = A ^{j - 1} $\oplus$ A $\cong$ Wege der Länge j .
Läßt sich abkürzen durch A,A ²,A ⁴,A ⁸,....
$\Rightarrow$ log n boole'sche Matrixmultiplikationen
$\Rightarrow$ log n Schritte für eine CRCW-PRAM mit n ³ Prozessoren.

Graph und seine transitive Hülle

Liegt der erste Eintrag von Zeile i in Spalte j , so gilt zhk[i] = j.
Kosten: O(n ³ · log n) .

2. Möglichkeit: Tiefensuche

Partitioniere die Adjazenzmatrix in p Streifen.
Jeder Prozessor berechnet einen Spannwald durch Tiefensuche. Anschließend werden die Spannwälder mit UNION-FIND ineinandergemischt. Dazu wird jede Kante (x,y) vom sendenden Prozessor beim empfangenden Prozessor daraufhin getestet, ob x und y in derselben ZHK liegen. Falls ja, wird (x,y) ignoriert, falls nein, werden ZHK(x) und ZHK(y) verbunden. Da jeder Wald höchstens n Kanten enthält, benötigt das Mischen O(n) . Im Hypercube mit p Prozessoren entstehen nach der initialen Tiefensuche mit Zeit O(${\frac{n^2}{p}}$) anschließend log p Mischphasen der Zeit O(n) . Also beträgt die Gesamtzeit O(n ²/p) + O(n · log p) , die Kosten betragen O(n ²) + O(p · logp · n) . Für p < n/log n ist der Algorithmus kostenoptimal.

Graph (a) Partitionierung der Adjazenzmatrix (b)

Teilgraph für P₁ (c) Spannwald berechnet von P₁ (d)

Teilgraph für P₂ (e) Spannwald berechnet von P₂ (f)

3. Möglichkeit: Verschmelzen von Superknoten

Während des Ablaufs existiert eine Partition der Knoten in vorläufige Zusammenhangskomponenten. Jede vorläufige Zusammenhangskomponente wird repräsentiert durch den an ihr beteiligten Knoten mit der kleinsten Nummer, genannt Superknoten. Dieser Knoten ist Vater für alle Knoten der Zusammenhangskomponente, einschließlich für sich selbst. In jeder Iteration sucht sich jede unfertige Zusammenhangskomponente einen Partner und vereinigt sich mit diesem. Zu Beginn ist jeder Knoten sein eigener Vater und somit Superknoten. Jede Iteration hat drei Phasen:

Phase 1: Jeder Knoten sucht sich als Freund den kleinsten benachbarten Superknoten, d.h. von den Vätern seiner Nachbarn den kleinsten. (Dabei wird nach Möglichkeit ein anderer Superknoten gewählt.)

Phase 2: Jeder Superknoten sucht sich als neuen Vater den kleinsten Freund seiner Söhne. (Dabei wird nach Möglichkeit ein anderer Superknoten gewählt.)

Phase 3: Jeder Knoten sucht sich als neuen Vater das Minimum seiner Vorfahren.

Es wird eine CREW-PRAM mit n ² Prozessoren verwendet. Da sich in jeder Iteration die Anzahl der Zusammenhangskomponenten mindestens halbiert, entstehen höchstens log (n) Iterationen. Jede Iteration benötigt:

Aufwand für Phase 1:

Je n Prozessoren bearbeiten Knoten x .

Für alle Knoten, die x zum Nachbarn haben, wird über ihren Vater minimiert.

$\Rightarrow$ O(log n)

Aufwand für Phase 2:

Je n Prozessoren bearbeiten Superknoten x .

Für alle Knoten, die x zum Vater haben, wird über ihren Freund minimiert.

$\Rightarrow$ O(log n)

Aufwand für Phase 3:

n Prozessoren ersetzen log n mal bei jedem Knoten den Vater durch den Großvater.

$\Rightarrow$ O(log n)

Die Gesamtlaufzeit beträgt daher O($\log^{2}_{}$n) , die Kosten O(n ² · $\log^{2}_{}$n) .