Tiefensuche

[Hagbard]

kann mir da vielleicht jemand weiterhelfen? :confused:

hier die Angabe:

Geg. sei ein zusammenhängender, ungerichteter, ungewichteter Graph G mit n Knoten un m Kanten.
Schreiben sie einen Alg. in Pseudocode , der ausgehend vom Knoten mit der Nummer 1 mittels Tiefensuche den Graphen durchläuft und seine Adjazenzliste ausgibt. Dabei soll für jeden Knoten genau eine Zeile ausgegeben werden, in der zuerst die Knotennummer und anschließend eine Liste der Nummern seiner Nachbarknoten steht. Sie können im Pseudocode die Anweisungen ausgeben und neue Zeile verwenden. Und dann noch die O - Notation angeben.

mfg hagbard :thumb:

[Sensei]

Naja... Tiefensuche steht ja im Skript;
ich würd das ganz normal angehen mit Tiefensuche und dann immer für alle w € N-(w) die Knoten speichern in einer Liste...
und am Schluss ausgeben!

[the_unclean]

Naja... Tiefensuche steht ja im Skript;
ich würd das ganz normal angehen mit Tiefensuche und dann immer für alle w € N-(w) die Knoten speichern in einer Liste...
und am Schluss ausgeben!

sensei ich glaub du hast übersehen daß er ungerichtet sein soll..
also wäre das doch für alle w € N(v) oder?
mfg maz

[the_unclean]

also ich hab mich mal rübergewagt und hab versucht das mit Edgelist,bzw indexlist von s.114 zu machen...
habe auf die 2 methoden nächste zeile, und ausgeben vezichtet, da sie mir nicht sonderlich brauchbar schienen..
Und warum man hier mit DFS vorghen soll check ich a ned so ganz
einfgacher wäre sicher gewesen:
"Für alle knoten € V"
und dann die arrays auffüllen
hoffe das versteht irgendwer, is leider schirch gworden mit den ganzen variablen, wusst aber ned wie ich sie sonst übergeben soll
wenn jemand einen Tipp diesbezüglich hat, bitte sagen!
Gleich dazu:
Hätte ich sowas beim Test dann würd ichs lieber nach Woltis Angaben von letzter Woche vom Bsp 4.2 mit Liste.add(x) zusammenbasteln :thumb:

edgelist[]= array mit 2xKantenzahl-feldern
index[]= array mit AnzahlDerKnoten-feldern
s=Knoten
m=Laufvariable des Indexarrays
z= Laufvariable des edgelistarrays



blah(s)
{
p=1
DFS(s,z,p,m)
returniere index + edgelist
}


dfs(s,z,p,m)
{
s.markiert=1
Index[m]=p
m++
p=Anzahl der Knoten in N(v) +1 // +1 damit er auf das erste elment in edgelist verweist, daß zu dem neuen Punkt an index[m] gehört
(weil p mit 1 initilialisiert wird)

f.alle knoten w Element von N(v)
{
edgelist[z]=w
z++
}
f.alle Knoten w Element von N(v)
{
if(w.markiert=0)
DFS(w,z,p,m)
}
}


Is der algorithmus zu irgenwas zu gebrauchen?
Programmier noch nicht so lange, daher gleich noch eine frage kann ich
die 2 "f.alle knoten € N(v)" in eine einzige schleife tun, ohne daß es kollisionen bei den arrayfelden gibt?
Thx, maz

[Tiniiiii]

Ich denke, dass das zu ausführlich ist. Habe das Ganze versucht minimal zu lösen und auch habe dabei keine Arrays (bis auf markiert[]) initialisiert, weil ich glaube wenn nur ausgegeben (und nicht gespeichert) werden soll, Arrys nicht notwendig sind.

Hier mein Versuch (hoffe er stimmt):

Adjazenzliste_ausgeben(V,E)
---------------------------
markiert[1,...,v] = 0;
DFS(1);

DFS(v)
------
markiert[v] = 1;
neue zeile();
ausgeben(v);

für alle w Element N(v) {
ausgeben(w);
falls markiert[w] == 0;
DFS(w);
}

Freu' mich immer über Feedback!

lg Martina

[the_unclean]

DFS(v)
------
markiert[v] = 1;
neue zeile();
ausgeben(v);

für alle w Element N(v) {
ausgeben(w);
falls markiert[w] == 0;
DFS(w);
}[/CODE]


mhmm ich denke es stimmt soweit, hab nicht bedacht daß du die knoten einfach nur ausgeben musst

meiner meinung jedoch solltest du
ausgeben(v); vor neue zeile();
stellen
denn zuerst gibst du den Knoten aus, und eine zeile darunter alle nachbarknoten

also sähe das so aus
1
2,3
2
1,3
3
2,1

mfg, maz

[Tiniiiii]

also sähe das so aus
1
2,3
2
1,3
3
2,1

Ich in davon ausgegangen dass es so aussehen sollte:

1,2,3
2,1,3
3,2,1

" ... zuerst die Knotennummern & anschließend eine Liste der Nummern seiner Nachbarknoten ..." habe ich so interpretiert. In der Angabe ist hier nicht wirklich eindeutig ob mit "anschließend" in der selben oder in einer neuen Zeile gemeint war. Ich glaube beides sollte durchgehen ...

Außerdem fällt mir gerade auf, dass wenn ich ausgeben(v) vor neueZeile() stelle das Ganze so aussehen würde:

1
2,3,4
1,3,3
2,1

Da müsste man damit es richtig wird nochmal irgendwo ein "neueZeile()" einfügen ...

lg Martina

[Hagbard]

:p danke leute jetzt check ich das, so schwer war das ja gar nicht
hab mich wohl wiedermal von der fragestellung einschüchtern lassen

dank an Tinii & the unclean :)

mfg hagbard

[ricotool]

@Tiniiiii: ich glaube nicht, dass dein Code das gewünschte Ergebnis liefert.
Zuerst wird Knoten 1 markiert und ausgegeben. Jetzt müssten seine Nachbarknoten und danach eine neue Zeile ausgegeben werden. Laut deinem Code wird zunächst zwar der erste Nachbarknoten (von Knoten 1) ausgegeben, dann wird aber DFS für diesen Knoten aufgerufen, da er noch nicht markiert ist.
Somit kommt als nächste Ausgabe eine neue Zeile und die Knotennummer.

ich habe zwar auch keine bessere lösung, aber ich glaube es muss irgendwie gehen ohne die Adjazenzlisten zuerst in einem Array zu speichern und sie erst dann auszugeben.

lg, ricotool

[Tiniiiii]

Oh nein! Hab mich schon soooo gefreut! :traurig:
Neuer Versuch:

Adjazenzliste_ausgeben(V,E)
---------------------------
markiert[1,...,v] = 0;
DFS(1);

DFS(v)
------
markiert[v] = 1;
neue zeile();
ausgeben(v);

für alle w Element N(v)
ausgeben(w);
für alle w Element N(v) {
falls markiert[w] == 0;
DFS(w);
}

So sollten vorab mal alle Nachbarknoten von v ausgegeben werden bevor DFS(w) aufgerufen wird ...
Könnte das so klappen? Vernichte ich hier bei der Laufzeit viel Zeit?

Thanx & lg

[Sensei]

Zeit vernichtest du kaum was... du rufst jetzt 2 mal "für alle w aus..." auf. und 2*x is in Theta-Notation bekannterweise x... klar was ich meine?

denke der Algo passt

[ricotool]

der einfachste algo um dieses problem zu lösen schaut meiner meinung nach so aus:
Adjazenzliste_ausgeben(V,E)
---------------------------
markiert[1,...,v] = 0;
für alle Knoten v aus V {
neue Zeile();
für alle Knoten w aus N(v)
ausgeben(w);
}

leider hat das nix mit Tiefensuche zu tun, wie es in der Angabe verlangt ist.

@Tiniiiii: dein neuer algo ist glaub ich die beste lösung. er benutzt die Tiefensuche ja wenigstens um zu jedem Knoten zu kommen.

lg, ricotool

[Tiniiiii]

Fühl mich schwer geehrt ... :bounce:
Jetzt muss ich nur noch die anderen Beispiele so schön hinkriegen und sie mir bis Mittwoch merken ...