Tiefensuche - Zusammenhangskomponente

[Ekimus]

Hallo,

haett mal eine kleine Frage zur Tiefensuche, und zwar dafuer ob beim DFS2 (117-118)Algorithmus nicht irgenwo die Teilmenge N schon bekannt sein muss. In den Algorithmen selbst wird die ja nirgends wirklich festgestellt/definiert oder aehnliches.

Ausgesprochen laeuft der Pseudocode fuer mich so ab:

Zuerst mal nehme ich alle Knoten v aus der Grundmenge V und sobald ein Knoten mit "0" (als nicht) markiert ist, nehme ich die naechste Komponentennummer und gehe zum DFS2 Algo.
Und in DFS2 schreib ich in jeden Unmarkierten Knoten die entsprechende Komponentennummer rein. Wenn wir fertig sind wieder in die Schleife vom aufrufenden Algorithmus rein und nachsehen ob noch was uebrig ist. Wenn ja dann einfach wieder DFS2 ablaufen lassen.
Das was mich stoert ist das nun im DFS2 ploetzlich w und N(v) vorkommen laut Definition muesste N ja eine Teilmenge von V sein. Darf ich einfach annehmen das ich diese Teilmengen schon richtig festgestellt hab oder muss ich irgendwie sagen koennen woher die kommen oder bin ich voellig am Holzweg.

[wolti]

Hallo,
Zuerst mal nehme ich alle Knoten v aus der Grundmenge V und sobald ein Knoten mit "0" (als nicht) markiert ist, nehme ich die naechste Komponentennummer und gehe zum DFS2 Algo.

Ja. Das funktioniert so. Und der DFS2 markiert alle Knoten wo in einer Zusammenhangskomponente liegen, da er ja solange in den Graphen reintaucht und markiert wie er nur kann. Ich nach diesem Durchlauf noch ein Knoten nicht markiert, so liegt er in einer anderen Komponente.
Das was mich stoert ist das nun im DFS2 ploetzlich w und N(v) vorkommen laut Definition muesste N ja eine Teilmenge von V sein. Darf ich einfach annehmen das ich diese Teilmengen schon richtig festgestellt hab oder muss ich irgendwie sagen koennen woher die kommen oder bin ich voellig am Holzweg.
Die Menge N-(v) ermittelst du natürlich aus E, weil du das über die Kanten bekommst. Und das erste bedeutet nicht, dass du das Element rausnimmst. Das wäre dann v e V und V=V \ {v} (Um das Element zu entfernen).

Grüße,
Wolti

[Ekimus]

Die Menge N-(v) ermittelst du natürlich aus E, weil du das über die Kanten bekommst. Und das erste bedeutet nicht, dass du das Element rausnimmst. Das wäre dann v e V und V=V \ {v} (Um das Element zu entfernen).


Das ich nichts rausnehme ist mir klar der Algo markiert ja nur bereits gegangene Wege (oder besser die Knoten die zu einer Komponente gehoeren). Aber wie komme ich zu meiner Teilmenge? Ich blick da nicht ganz durch. Haettest du irgendwo einen guten Link das Skriptum hilft mir nicht so wirklich weiter bei der Sache

thx
Ekimus

[yrucrem]

Ich glaube Du siehst das einfach komplizierter als es sein muss. Man verwendet den Ausdruck N(v) -- also die Nachbarn vom Knoten v -- einfach um den Pseudocode uebersichtlicher zu halten. Wenn man das auschreiben wuerde, wuerde die Stelle unoetig komplex, obwohl sie ja nicht sonderlich wichtig ist (alle Nachbarn eines Knotens zu finden ist ja nicht recht schwer).

Statt also zu schreiben (ich gehe hier von einer Adjazenzliste aus):


curr = edgelist[v]; /* Die Liste der Inzidenten Knoten von v */
while (curr != NULL) {
markiert[curr.nodenumber] = 1;
curr = curr.next;
}


Schreibt man einfacher


fuer alle w aus N(v) {
markiert[w] = 1;
}


Wobei N(v) alle Knoten enthaelt, die ueber eine Kante mit v verbunden sind. Da es ja ersichtlich ist, dass diese Knoten nicht schwer herauszufinden sind, gibt man auch keinen Pseudocode an um N(v) zu berechnen.

[Ekimus]

Auf gut deutsch heisst das also: ich hab einen (beliebigen) Knoten und all Knoten die ueber genau eine Kante erreichen kann gehoeren zur selben Komponente?