Unterschied Tiefensuche/ Breitensuche

[grassi3000]

Also, wo genau liegt eigentlich der Unterschied.

Zu Tiefensuche steht im Skriptum:
[...]Verlasse jeden Knoten so schnell wie möglich, um "tiefer" in den Graphen zu laufen[...]
Bezüglich Breitensuche steht am Übungsblatt
[...]werden hier zunächst alle Nachbarn des aktuellen Knotens besucht, und dann rekursiv die Nachbarn [...]
Wo liegt hier der Unterschied? Man überprüft hier bei beiden Methoden immer die Knoten, die ich von einem Knoten aus mit einer Kante erreichen kann, usw.
Ebenso überprüft man nur Knoten, die noch nicht erreicht wurden.

Ebenso wird das ganze nicht auf spezielle Graphen, wie Bäume beschränkt.

Also ist meiner Meinung nach hier gar kein Unterschied, sei es von der Betrachtung im Graphen, als auch auf algorithmischer Ebene, oder liege ich hier Falsch?

[eva_d]

wo um himmels willen kommt denn breitensuche vor?! :confused:

schon gefunden

[grassi3000]

Nach dem Letzten Test, wo im Übungsblatt vorher auch der Minimum Heap vorgekommen ist, glaube ich, dass das eventuell auch beim Test kommen könnte.

[clemensp]

naja


beispiel

also du hast folgnde knoten (in den klammern steht zu welchen knoten sie kanten haben )

1 ( 2,3,4)
2 ( 1,3)
3 (2,4,5)
4 (1,3)
5 (3)

wennst jetz tiefensuche machst dann rufst amal knoten 1 auf

der algorithmus würd jetz in den knoten 2 gehn
hier gleich wieder den nächstn nachbarn aufrufn der noch nicht markiert ist also 3 hier wieder
--> 4

jetz gibts keinen knoten mehr der noch nicht markiert is
also die schleife der nachbarknoten vom vorherign fertig machn (knoten 3)
in dem fall is der nächste nachbarknoten der behandelt wird 5
der hat auch keine unmarkierten nachbarn

also wieder ein schritt zurück
jetz hat knoten 3 auch keine unmarkierten nachbarknoten mehr

usw...


bei da breitensuche würd vermutlich zuerst knoten 2 dann gleich 3 dann 4 markiert werden bevor man sich die nachbarn der markierten knoten weiter anschaut



das is zumindest das einzige was mir logisch erscheint ^^

ned schlagn wenns ned stimmt :)

[Lord Binary]

oder liege ich hier Falsch?
Ja.

Etwas anders formuliert wirds vielleicht klarer ???

Tiefensuche:
Einer der Nachfolger eines Knotens wird ausgewählt
, danach einer von dessen Nachfolgern, danach, ...
Gibts keine Nachfolger mehr, zurück zum letzten Knoten,
dessen Nachfolger noch nicht alle untersucht wurden (=Backtracking).

Breitensuche:
ALLE Nachfolger eines Knotens werden untersucht, dann wird einer ausgewählt und dessen Nachfolger untersucht.
Danach kommen erst die Nachfolger des zweiten, dritten, ... dran.
Mit der Verarbeitung der nächsten Ebene wird erst begonnen, wenn alle Knoten auf einer Ebene besucht worden sind.

Man beachte bzw überlege die Unterschiede bezüglich Speicherbedarf.

Mfg, LB

[grassi3000]

sprich: beim algorithmus für die Tiefensuche hab ich immer nur einen aufruf DFS (x)

bei einem Breitensuche algorithmus hätte ich den Aufruf so oft, so oft ich nachbarn habe?

[clemensp]

nix wervechselt

[grassi3000]

ALLE Nachfolger eines Knotens werden untersucht, dann wird einer ausgewählt und dessen Nachfolger untersucht.
Danach kommen erst die Nachfolger des zweiten, dritten, ... dran.
Mit der Verarbeitung der nächsten Ebene wird erst begonnen, wenn alle Knoten auf einer Ebene besucht worden sind.


Aber ich betrachte immer noch alle Nachbarn von allen Nachbarn, oder?

Nicht alle Nachbarn, des besten Nachbarn

[clemensp]

jo es werdn alle nachbarn von allen nachbarn behandelt
nur die reihenfolge also die priorität ist anders ^^

[schurli]

mir hat dieses Seite beim Verständnis geholfen:
http://user.cs.tu-berlin.de/~magus/labyrinth/

mfg
schurli

[Merlin]

hat jemand vielleicht einen verständlicheren Algorithmus (als auf der Homepage) geschrieben?

Wenn wir eine Tiefensuche mittels Stack schreiben könnten, könnte auch kommen, dass wir die Breitensuche mit Hilfe einer Liste realisieren.

Das wäre auch gleich eine interessante Aufgabe zum Lösen...

[schurli]

hat jemand vielleicht einen verständlicheren Algorithmus (als auf der Homepage) geschrieben? ich habe hier (http://hades.gothic.at/iforum/showthread.php?t=19007) einen Algorithmus gepostet (vielleicht hilft dir das, bin mir aber nicht sicher ob er stimmt)
Wenn wir eine Tiefensuche mittels Stack schreiben könnten, könnte auch kommen, dass wir die Breitensuche mit Hilfe einer Liste realisieren. soweit ich das verstanden habe ist der einzige unterschied zw. Tiefen- und Breitensuche dass bei der Tiefensuche ein Stack (Stapel) und bei der Breitensuche eine Queue (Warteschlange) verwendet wird.
Also müsstest du dir im Prinzip nur überlegen wie du eine Queue mit einer Liste simulierst.

[Merlin]

soweit ich das verstanden habe ist der einzige unterschied zw. Tiefen- und Breitensuche dass bei der Tiefensuche ein Stack (Stapel) und bei der Breitensuche eine Queue (Warteschlange) verwendet wird.
Also müsstest du dir im Prinzip nur überlegen wie du eine Queue mit einer Liste simulierst.
Nein, dass ist nicht der Unterschied.
Der Unterschied ist die Reihenfolge der Abarbeitung sprich die Priorität der Knoten...
Ausserdem ist eine Queue eine Liste ;)

Bei der Breitensuche markiere ich Ebene für Ebene während ich bei der Tiefensuche zuerst alle Folgeknoten und deren Folgeknoten in die Tiefe abklappere.
Anschliessend kehre ich wieder in die erste Ebene zurück
Dann schau ich mir vom 2.Knoten alle deren Nachfolgeknoten an usw....
Schlagwort: Back-Tracking.

Bei der Breitensuche suche ich wie gesagt für jede Ebene alle zu markierende Elemente.

Also, Konzept:

setze alle Knoten v markiert[v] == 0

anschliessend markiere alle v die Nachbarknoten sind.

Jetzt müsste ich, so ich das richtig verstanden habe alle Knoten der nächsten Ebene markieren, darf aber nicht deren Nachbarknoten gleich markieren bevor ich nicht alle dieser Ebene zuEnde markiert habe.

Nur wie soll man das in einer Liste veranschaulichen ???

Bzw. wie soll ich das überhaupt veranschaulichen?

Beim Test würden wir sicher alle durchfallen wenn so was kommt http://hades.gothic.at/iforum/images/smilies/disturbed.gif

[schurli]

Ausserdem ist eine Queue eine Liste ;)
das hab ich aber anders verstanden (vielleicht lieg ich aber auch falsch):
bei einer liste kann ich jederzeit auf jedes gespeicherte Element zugreifen. (siehe BS 49ff)

eine Queue arbeitet nach dem FIFO - "First In First Out"-Prinzip das heißt das Element das zuerst eingefügt wird muss auch als erster entnommen werden. (deshalb auch der Name "Warteschlange")

ein Stack arbeitet nach dem LIFO - "Last In First Out"-Prinzip das heißt das Element das als letzter eingefügt wird als erster entnommen wird. (deshalb auch der Name Stapel)

hier (http://www.pi.informatik.tu-darmstadt.de/icpcSem/web/datenstrukturen/index.html) ein link zum thema.

[RT83]

http://members.aol.com/mnsjava/referate/graphen/breitensuche.htm

unter diesem link hab ich es verstanden, vielleicht hilft es den anderen auch

[Merlin]

danke, das schaut nach einer guten Erklärung aus.
Nur ganz verstanden hab ichs noch nicht:

Es wird ein Queue verwendet um die Ecken zu speichern. Von der Startecke aus besucht der Algorithmus alle an die Startecke angeschlossenen Ecken, markiert sie als besucht und legt sie auf den Queue. Sind alle angeschlossenen Ecken besucht, entfernt er eine Ecke vom Queue und besucht alle unbesuchten an diese Ecke angeschlossenen Ecken und legt sie ebenfalls auf den Queue. Dies macht er so lange, bis keine Ecke mehr auf dem Queue liegt.
Also nimmt er nicht das erste Element und geht damit in die Tiefe sondern das letzte , so wie ich das verstehe.

Stimmt das oder hab ich das falsch verstanden?

[Lord Binary]

@schurli: ja, richtig.
Trotzdem ist der Unterschied Breitensuche/Tiefensuche NICHT Stack versus Queue.

Man KANN diese DS verwenden, es ist sogar recht "geschickt"/günstig/clever, man muß aber nicht.
Zu verstehen warum z.B Queues oft für BFS verwendet werden, kann auch nicht schaden.

Mfg, LB

[schurli]

ich versuche es mal anhand von bsp 4 vom fünften übungsblatt zu erklären.

(leider habe ich kein proggie zur hand um die graphen zu zeichnen also muss ich sie scannen. ich hoffe man kann trotzdem erkennen was ich meine)

am einfachsten man stellt sich die "aufrufe" als Baum vor.

Bei der Tiefensuche wird zuerst jeder Zweig "gefunden"
Bei der Breitensuche wird immer Ebenenweise vorgegangen.

Ich habe die Graphen so weit gezeichnet bis zum ersten mal der Endknoten (K) gefunden wird (ausgegangen vom Knoten A).

Bei diesem BSP hat die Breitensuche den Vorteil dass beim ersten finden von K der kürzeste Weg gefunden ist.
Bei der Tiefensuche müsste ich jetzt noch alle anderen Zweige suchen und dann den kürzesten Weg bestimmen.

[grassi3000]

Das Prinzip ist mir klar, nur das Ablaufdiagramm in dem link (implementierung mittels Queue, mrferrari) ist mir net klar

[schurli]

Das Prinzip ist mir klar, nur das Ablaufdiagramm in dem link (implementierung mittels Queue, mrferrari) ist mir net klar Ist etwas blöd aufgezeichnet (führt meiner Meinung nach nur zu Verwirrungen)
das heißt:
es werden zuerst alle nachbarn von A gesucht, dann alle Nachbarn von B, dann alle Nachbarn von E und dann alle Nachbarn von F.

also:
wenn alle nachbarn von A gesucht werden, werden die Knoten B, E und F gefunden.
Im zweiten Schritt werden die die Nachbarn der Knoten B, E und F gesucht

Dh.
Wenn die Nachbarn von A gesucht werden, werden die Knoten B, E und F (in dieser Reihenfolge) in die Queue gegeben.
Dann werden nacheinander die Knoten aus der Queue abgearbeitet. das heißt zuerst B, dann E und zuletzt F. Die Knoten die bei dieser "Abarbeitung" gefunden werden, werden wieder in die Queue gegeben und (im nächsten Schritt) abgearbeitet...

[Cheez]

Hat jemand eine idee wie der pseudocode einer Breitesuche mit der datenstruktur queue aussieht...??
...was völlig neues in der vorlesung nie besprochenes...wär doch DAS bsp für den UE test... :)

[schurli]

Hat jemand eine idee wie der pseudocode einer Breitesuche mit der datenstruktur queue aussieht...?? für welches problem brauchst du den Algorithmus?
hier (http://hades.gothic.at/iforum/showthread.php?t=19007) hab ich eine gepostet der den kürzesten Weg zwischen 2 Knoten finden (bin aber nicht sicher ob er stimmt)