Tiefensuche: Unterschied zwischen den Versionen

Aus KGS-Wiki
(Breitensuche geladen)
 
K (Link hinzugefügt)
 
(2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
{{Thumbnailbox|INHALT={{Beispielgraph}}|CAPTION=Ein Beispielgraph}}
{{Thumbnailbox|INHALT={{Beispielgraph}}|CAPTION=Ein Beispielgraph}}
Die [[Breitensuche]] ist ein [[Algorithmus]], um ein Element in einem [[Graph]]en zu suchen, ohne irgendwelche Informationen über dessen Verbindungen zu anderen Knoten zu haben.
Die [[Tiefensuche]] ist ein [[Algorithmus]], um ein Element in einem [[Graph]]en zu suchen, ohne irgendwelche Informationen über dessen Verbindungen zu anderen Knoten zu haben.


Der Algorithmus beginnt bei einem Startknoten, besucht zunächst alle deren Nachbarn, dann deren noch nicht besuchte Nachbarn, dann deren noch nicht besuchte Nachbarn, bis entweder das gesuchte Objekt gefunden worden ist oder der gesamte Graph durchsucht wurde.
Der Algorithmus beginnt bei einem Startknoten, besucht zunächst einen seiner noch nicht besuchten Nachbarn, dann einen von dessen noch nicht besuchten Nachbarn, dann einen von ''dessen'' noch nicht besuchten Nachbarn usw., bis er an einen Knoten gerät, dessen Nachbarn alle schon besucht worden sind. Falls dies geschieht, wird die Kette von besuchten Knoten rückwärts abgearbeitet, bis ein Knoten mit noch unbesuchten Nachbarn gefunden wird. Über diesen wird wieder eine Tiefensuche durchgeführt, bis der ganze Graph abgearbeitet ist.


Die Liste der noch zu besuchenden Knoten kann bei der Breitensuche als [[Vorrangwarteschlange]] modelliert werden.
Die Liste der noch zu besuchenden Knoten kann bei der Breitensuche als [[Stack]] modelliert werden.


Wenn alle [[Graph#(Un-)Gewichtete_Graphen|Kantengewichte]] des Graphen identisch sind, findet die Breitensuche immer einen [[Wegfindung|kürzesten Weg]] zwischen dem Startknoten und dem gesuchten Knoten.
Die betrachteten Knoten und Kanten bilden nach dem Ende einer Tiefensuche einen [[Baum (Datenstruktur)|Spannbaum]] mit dem Startknoten als Wurzel, allerdings nicht zwingend einen minimalen.
 
Die betrachteten Knoten und Kanten zwischen diesen bilden nach dem Ende einer Breitensuche einen [[Baum (Datenstruktur)|Spannbaum]] mit dem Startknoten als Wurzel, allerdings nicht zwingend einen minimalen.


== Beispiel ==
== Beispiel ==
Zeile 17: Zeile 15:
|INHALT=
|INHALT=
{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{Beispielgraph|link=lightgray|A=#00B169|AB=#00B169|AC=#00B169}}
INHALT={{Beispielgraph|link=lightgray|A=#00B169|AB=lightgreen|AC=lightgreen}}
|CAPTION=Noch nicht besuchte bekannte Nachbarn: B, C.
|CAPTION=Stack mit den noch nicht besuchten bekannten Nachbarn: B, C.
|ALIGN=left
|ALIGN=left
|CLASS=noclear}}
|CLASS=noclear}}


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{Beispielgraph|link=lightgray|A=#00B169|AB=#00B169|AC=#00B169|B=#00B169|BD=#00B169|BE=#00B169}}
INHALT={{Beispielgraph|link=lightgray|A=#00B169|AB=#00B169|AC=lightgreen|B=#00B169|BC=lightgreen|BD=lightgreen|BE=lightgreen}}
|CAPTION=Noch nicht besuchte bekannte Nachbarn: C, D, E.
|CAPTION=Stack mit den noch nicht besuchten bekannten Nachbarn: C, D, E, C.
|ALIGN=left
|ALIGN=left
|CLASS=noclear}}
|CLASS=noclear}}


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{Beispielgraph|link=lightgray|A=#00B169|AB=#00B169|AC=#00B169|B=#00B169|BD=#00B169|BE=#00B169|C=#00B169}}
INHALT={{Beispielgraph|link=lightgray|A=#00B169|AB=#00B169|AC=lightgreen|B=#00B169|BC=#00B169|BD=lightgreen|BE=lightgreen|C=#00B169|CD=lightgreen}}
|CAPTION=Noch nicht besuchte bekannte Nachbarn: D, E.<br/>C hat keine weiteren Nachbarn, die noch nicht auf der To-do-Liste stehen.
|CAPTION=Stack mit den noch nicht besuchten bekannten Nachbarn: D, D, E, C.
|ALIGN=left
|ALIGN=left
|CLASS=noclear}}
|CLASS=noclear}}


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{Beispielgraph|link=lightgray|A=#00B169|AB=#00B169|AC=#00B169|B=#00B169|BD=#00B169|BE=#00B169|C=#00B169|D=#00B169}}
INHALT={{Beispielgraph|link=lightgray|A=#00B169|AB=#00B169|AC=lightgreen|B=#00B169|BC=#00B169|BD=lightgreen|BE=lightgreen|C=#00B169|CD=#00B169|D=#00B169|DE=lightgreen}}
|CAPTION=Noch nicht besuchte bekannte Nachbarn: E.<br/>D hat keine weiteren Nachbarn, die noch nicht auf der To-do-Liste stehen.
|CAPTION=Stack mit den noch nicht besuchten bekannten Nachbarn: E, D, E, C.
|ALIGN=left
|ALIGN=left
|CLASS=noclear}}
|CLASS=noclear}}


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{Beispielgraph|link=lightgray|A=#00B169|AB=#00B169|AC=#00B169|B=#00B169|BD=#00B169|BE=#00B169|C=#00B169|D=#00B169|E=#00B169}}
INHALT={{Beispielgraph|link=lightgray|A=#00B169|AB=#00B169|AC=lightgreen|B=#00B169|BC=#00B169|BD=lightgreen|BE=lightgreen|C=#00B169|CD=#00B169|D=#00B169|DE=#00B169|E=#00B169}}
|CAPTION=E wurde gefunden.
|CAPTION=E wurde gefunden.
|ALIGN=left
|ALIGN=left
Zeile 47: Zeile 45:
}}
}}


== Anwendungen ==
== Weblinks ==
 
Eine Anwendung von Breitensuche ist die Füllung von Farbflächen in einem Zeichenprogramm: zunächst wird der angeklickte Pixel gefärbt, dann alle von seinen Nachbarn, die dieselbe Farbe wie er hatten, dann deren Nachbarn mit derselben Farbe usw.


Auch der Weg aus einem Labyrinth kann mit einer Breitensuche gelöst werden. Dies wird u.a. in Computerspielen angewandt und in einer ähnlichen Situation auch beim Layouten von Leiterbahnen auf Platinen.
* {{VisuAlgo|en/dfsbfs|Tiefensuche visualisiert}}


{{Navigationsleiste Graphalgorithmen}}
{{Navigationsleiste Graphalgorithmen}}
[[Kategorie:Algorithmen]]
[[Kategorie:Graphen]]

Aktuelle Version vom 1. April 2024, 02:00 Uhr

Ein Beispielgraph

Die Tiefensuche ist ein Algorithmus, um ein Element in einem Graphen zu suchen, ohne irgendwelche Informationen über dessen Verbindungen zu anderen Knoten zu haben.

Der Algorithmus beginnt bei einem Startknoten, besucht zunächst einen seiner noch nicht besuchten Nachbarn, dann einen von dessen noch nicht besuchten Nachbarn, dann einen von dessen noch nicht besuchten Nachbarn usw., bis er an einen Knoten gerät, dessen Nachbarn alle schon besucht worden sind. Falls dies geschieht, wird die Kette von besuchten Knoten rückwärts abgearbeitet, bis ein Knoten mit noch unbesuchten Nachbarn gefunden wird. Über diesen wird wieder eine Tiefensuche durchgeführt, bis der ganze Graph abgearbeitet ist.

Die Liste der noch zu besuchenden Knoten kann bei der Breitensuche als Stack modelliert werden.

Die betrachteten Knoten und Kanten bilden nach dem Ende einer Tiefensuche einen Spannbaum mit dem Startknoten als Wurzel, allerdings nicht zwingend einen minimalen.

Beispiel

Das Objekt E soll vom Startknoten aus gefunden werden.

Stack mit den noch nicht besuchten bekannten Nachbarn: B, C.
Stack mit den noch nicht besuchten bekannten Nachbarn: C, D, E, C.
Stack mit den noch nicht besuchten bekannten Nachbarn: D, D, E, C.
Stack mit den noch nicht besuchten bekannten Nachbarn: E, D, E, C.
E wurde gefunden.

Weblinks

Abgerufen von „https://wiki.kah.gs/index.php?title=Tiefensuche&oldid=4122“