cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

Graphen Traversieren | verschiedene Methoden

anchored to [[111.00_anchor]]

Overview:

Es existieren verschiedene Konzepte / Ansätze, um einen Graphen zu durchlaufen / oder durchsuchen. All diese Möglichkeiten sind Prinzipiell nach einem systematischen Ansatz designed, aber haben verschiedene Umsetzungen bzw Konepte in ihrere Durchführung.

Wir können hier so verschiedene Fragen lösen / bearbeiten, welche jeweils darauf aufbauen, dass man den Graphen durchläuft:

[!example] Mögliche Fragen:

finding out whether theres a path between A and B in a road network

crawl trough an amount of webpages

traverse directory to find particular file

Es bieten sich uns jetzt hier zwei große Ansätze:

DFS - Depth First Search
BFS - Breadth First Search

Prinzip des Durchmustern von Graphen:

Sei ein Graph $G = (V, E)$ gegeben und weiterhin ein Startknoten $s$ , sowie eine Menge von bekannten Knoten $S$ .

Wir möchten jetzt mit einem Algorithmus beschreiben, wann wir eine Kante benutzt haben oder nicht.

[!Definition] Finden aller erreichbaren Kanten in einem Graphen wie gehen wir algorithmisch vor? #card
s; // Startknoten
S = s // Menge von bekannten Knoten 
while ( exists v in S mit unbenutzer Kante (v,w) in E){
  e wird als "benutzt" markiert
  S = S vereinigt mit w // w ist der neue Knoten, den wir erreichen können
  }
Unter Anwendung dieses Algorithmus können wir jetzt alle erreichbaren Knoten von einem Startknoten $s$ beschreiben / definieren. ^1704708778664

Fragen zur Musterung:

Betrachten wir den obigen Algorithmus kommen diverse Fragen auf: 1. Wie kann man etwas als benutzt definieren? 2. wie finden wir diese Kanten, die entsprechend verbunden sind? 3 wie kann man die zu füllende Menge $S$ beschreiben, also die, wo alle bekannten Knoten ( und somit auch erreichbare!) sind )

[!Important] Wie realisieren wir die Markierungen “benutzt” für kanten? #card Wir können diesen Zustand einfach mit Adjazenzlisten lösen. Wir werden dafür die Kanten in der Reihenfolge der Liste durchlaufen und uns die Stelle merken, bis wohin wir die Kanten schon betrachtet haben Es sind dann darin nur noch die unbenutzten enthalten.

Das heißt mehr oder weniger, dass wir in der Adjazenzliste die Stelle speichern ab welcher dann die unbekannten / bzw unbenutzten Kanten gespeichert werden. ^1704708778675

[!Important] Wie finden wir jetzt entsprechende Kanten $(v, w)$ die noch nicht benutzt wurden? #card

Wir haben zuvor betrachtet, wie wir die entsprechended Kanten, die unbenutzt sind, finden und beschreiben können. Das machen wir hier also darüber, dass wir Adjazenzlisten nutzen. Wir bauen eine Menge $S^{'} \subset S$ , die alle Knoten drin hat, wo die Kanten noch unbenutzt sind ^1704708778682

Intuitiv haben wir also eine Menge aller Knoten, wo wir schauen, ob es für diese noch unbenutzte Kanten gibt. Wenn ja, dann bleibt sie in der Menge, sonst wird sie irgendwann entfernt.

[!Error] Bedeutung von $S^{'}$ nach Ausführung des Durchmusterungs-Algorithmus ? #card Wenn wir den obigen Algorithmus dabei an einem Graphen ausführen, wird am Ende diese Menge $S^{'}$ alle die Knoten enthalten, die wir nicht erreichen können ^1704708778688

[!Definition] Implementation von $S$ , also der Menge von bekannten Knoten? #card wir können ihn einfach als bool’schen Array definieren, denn so sparen wir Platz ( wir müssen ja nur wissen, ob wir sie kennen oder nicht) ^1704708778695

Betrachtung $S$ und $S^{'}$ :

Wir möchten folgend beide Knoten-Mengen $S, S^{'}$ betrachten:

Wir brauchen für beide bestimmte Funktionen, um sinnig mit ihnen arbeiten zu können:

[!Definition] Welche Operationen brauch $S$ #card

Initialisieren ( leer mit false überall, außer $s$ )

Einfügen eines Knoten ( finde Position und setze auf true) ^1704708778701

[!Definition] Operationen für $S^{'}$ Welche Operationen brauch $S^{'}$ #card Auch hier brauchen wir basic Operationen:

Initialize ( hat hier alle Knoten außer $s$ )

Test $S^{'} = e m pt yse t$ –> wenn keine unbenutzt sind, haben wir scheinbar alles erreicht!

Einfügen eines neuen Knoten in die Menge!

nehme einen beliebigen knoten $v \in S^{'}$

entferne Knoten aus $S \in S^{'}$

wir können diese Struktur etwas mit einem [[111.08_algo_datastructures#Stacks Keller|Stack]] oder einer [[111.08_algo_datastructures#Queues Warteschlangen|Queue]] implementieren ^1704708778708

Je nachdem, wie wir diese Struktur jetzt umsetzen, erhalten wir dann folgend: DFS –> Stack! BFS –> Queue!

verbesserte Version der Durchmusterung:

Wir möchten jetzt die vorherige Implementation anpassen / verbessern: Sei wieder $G = (V, E)$ ein Graph und weiter $S, S^{'}$ die entsprechenden Mengen von “entdeckten / unentdeckten Knoten”.

[!Definition] Beschreibung des PseudoCode unter Anwendung der Mengen $S, S^{'}$ und Adjazenzlisten? #card

Name des Algorithmus: Explore-From(s)

S = S' = s // setze alle so, dass wir nur den Start kennen
for all (v in V) 
  p(v) = adjazenzlistenstart(v) //wir schreiben den Pfad **nach v** indem wir den adjazenzlistenstart nehmen
while( S' != 0):
  sei v in S' beliebig gewählt ( irgendein knoten);
  if(p(v) nicht am Listenende )
  	w = p(v) // verschiebe also p(v) 
  	if w nicht in S:
  		füge (w,S) und auch (w,S') ein 
  else 
  	entferne (v,S')

^1704708778716

Laufzeit der verbesserten Version:

Wir wissen dass jede Operation mit $O (1)$ definiert ist.

[!Important] Laufzeit von “Explorefrom(s)”, welche Abhängigkeit besteht? #card Weiterhin ist die Laufzeit immer proportional zur Größe des erreichten Graph n $G_{s} = (V_{s}, E_{s})$ –> also alles das, was wir erreichen konnten ( dabei lassen wir also unerkanntes raus, quasi)

Wir wollen das zeigen, indem wir darstellen, wie dieser neue Graph aussieht bzw aufgebaut sein wird ( also was enthalten ist / was nicht): Wir beschreiben die Menge von Knoten folgend: $V_{s} = {v ∣ s ⟶ v == P f a d (s, v) \neq = 0,} ∣ V_{s} ∣ = n_{s}$ und die Menge der Kanten, die wir betrachten können: $E_{s} = {e = (v, w) \in E ∣ v \land w \in V_{s}}, ∣ E_{s} ∣ = m_{s}$ Also die Menge der Kanten ist abhängig von der Menge der Knoten, die wir haben ( weil wir logischerweise nur die Kanten kennen, die wir auch zwischen bekannten Knoten gehen dürfen)

Es folgt hieraus jetzt eine Laufzeit von: $O (n_{s} + m_{s})$ ^1704708778724

| DFS | Depth-First-Search |

Eine Erklärung zu DFS, seiner Anwendung und Prinzipien findet sich folgend: [[111.20_Graphen_DFS|DFS]]

| BFS | Breadth-First-Search |

Eine Erklärung zu DFS, seiner Anwendung und Prinzipien findet sich folgend: [[111.19_Graphen_BFS|BFS]]

Verwendung und ähnliche Prinzipien

There are additional topics, spaces where we require either DFS or BFS traversal of a Graph:

minimal spanning trees <-> MST [[111.29_Graphen_MST_find_safe_edges]]
Point to Point shortest paths [[111.99_algo_graphs_ptp_shortestpath|point to part]]
ShortestPathProblems [[111.21_algo_graphs_ShortesPathProblems]]
[[111.22_Graphen_SSSP_dijkstra|Dijkstras]] ist in seiner Anwendung eher einem BFS ähnlich

scattered-lenity

Eine Erklärung zu DFS, seiner Anwendung und Prinzipien findet sich folgend: [[111.20_Graphen_DFS|DFS]]

Eine Erklärung zu DFS, seiner Anwendung und Prinzipien findet sich folgend: [[111.19_Graphen_BFS|BFS]]