dfs algorithmen

[clemensp]

hm findet sonst noch jemand das die DFS algorithmen im skript etwas komisch sind ?

ich mein ich versteh sie zwar aber noch mehr PSEUDO geht wirklich nichtmehr oda ?


für alle Knoten w aus N(v){
blabla
}

also N(v) sind alle benachtbarten Knoten von v denk ich mal...

können wir das beim test auch so einfach hinschreibn ??

N(v) wenn wir alle benachtbarten knoten brauchn von einem knoten?



sehr pseudo wie gesagt
gefällt mir überhaupt nicht ^^

[maitscha]

für alle Knoten w aus N(v){
blabla
}


Also dieser Aufruf ist meiner Meinung nicht schwierig zu programmieren und daher ok. Man müsste dazu zB in einer Adjazenzmatrix nur in der Zeile v alle Spalten mit einer "1" rausfinden um die Nachbarknoten von v zu erhalten.

In Java könnte das aussehen:


for [int i = 0; i<M[v].length(); i++) {

if (M[v,i] == 1)
{
...
}
}

[clemensp]

voraussetzung is das man schon eine adjazenzmatrix hat

[Merlin]

DFS1(v) {

markiert[v] = 1;

für alle Knoten w aus N(v) {

falls markiert[w] == 0 dann {

DFS1(w);
}
}
Versteht das jemand genauer?

Im ersten Schritt kommt das s, der Startknoten in die Funktion hinein.
Er wird auf 1 gesetzt.

Anschliessend gehe ich folgendes für alle Nachbarknoten von v durch:

wenn markiert[w] == 0 dann DFS1(w) also für alle Knoten, für die es keinen Pfad von s nach v gibt (sprich makiert[w] == 0 )

mache dasselbe nochmal.

2.Schritt:

Nun ist ein Nachbarknoten nicht verbunden mit einem Pfad nach s und kommt in DFS1 wieder hinein.
Jetzt wird er gleicheinmal auf 1 gesetzt ???

Dann werden also alle Nachbarknoten einfach mit markiert[v] = 1 versehen?
Hab ich das richtig verstanden?


achso, kann dass dann so gemeint sein, dass ich alle Nachbarknoten immer auf 1 setzte, und übrig bleiben dann diejenigen, welche keine Nachbarknoten von irgendeinem anderem Nachbarknoten von einem Nachbarknoten von ........ s sind?
Ok, dann ist mir das ganze jetzt verständlich geworden ;)

[clemensp]

genau

leider ist das ganze so blöd geschriebn ...


man startet bei einem knoten v markiert ihn

und ruft dann für alle nachbarknoten (die man w tauft) nochmal die funktion dfs1 auf (aber nur wenn sie noch nicht markiert worden sind (damit das ganze nicht unendlich durchläuft den jeder nachbarknoten hat ja den knoten vondem er aufgerufn wurde auch zum nachbarknoten))


am ende hat man dann alle knoten markiert die mit dem startknoten zusammenhängen
bzw anders formuliert
zu denen (zumindest bei ungerichteten graphen) ein weg vom startknoten existiert




aber wie gsagt ich find das is zimlich blöd gelöst

vor allm auch dieses
markiert[v]=1

gfallt ma ned wirklich


da wär ma sowas lieber
v.markiert = true;

^^

[Merlin]

Ich hab das die Tiefensuche als Stack angeschrieben, ähnlich der Lösung auf yukcrems Homepage:

DFS_Stack(s) {

S.push(s); // Füge Startknoten in den Stack

while (S.pop() != NULL) {

für alle w € S { // für alle Knoten-Elemente, die im Stack sind

falls (markiert[w] == 0) && (w € N(w) ) {

markiert[w] = 1;
push(w); //Gib w in den Stack

} sonst pop();

}

}

Zuerst ist nur s im Stack

alle Knoten werden auf Null markiert

Dann wird für alle Knoten im Stack geschaut, ob ihre Nachbarnmarkiert sind.
Wenn nicht, werden sie es und werden zusätzlich in den Stack gepusht.

Dadurch weiss ich im nächsten Durchlauf der Schleife (da Stack ja nicht leer ist, wiederholt sich diese), von welchen Knoten ich jetzt wieder die Nachbarknoten markieren soll.
usw...
Ist alles markiert was markiert gehört, gib die Elemente aus dem Stack wieder einzeln aus mittels pop().
voila

hoffentlich funzt das auch wirklich...
vielleicht schauts sich mal wer an....

lg
Merlinhttp://hades.gothic.at/iforum/images/smilies/thumb.gif

[johnDoe]

Hier ist so was ähnliches auch schon mal gemacht worden:
http://hades.gothic.at/iforum/showthread.php?t=1672

mfg johnDoe

[Cheez]

Funktioniert die Tiefensuche bei einem gerichteten Graphen eigentlich gleich?? Den was passiert bei einem gerichteten Graphen, wenn man zu einem Knoten kommt der keine Nachbarn mehr hat....dann springt man ja beim ungerichteten zurück zum vorgänger....aber dieses zurückspringen ist ja bei einem gerichteten graphen nicht mehr möglich.