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

| BFS | Breadth first search |

anchored to [[111.00_anchor]] proceeds from [[111.18_Graphen_Traversieren]]

primary difference to dfs: instead of traversing towards depth at first, we explore all edges of each node, colouring each vertex grey once explored.

Works with a simple queue, that enqueues the first node, then traversing trough all edges of it, adding them to the queue, popping the first element from queue and continuing with the next node, that is in the queue, exploring its edges- neighbours - enqueueing them, removing current node, continuing with the queue until its empty.

Exploration occurs in waves, exploring whole system step by step

[!Important] Äquivalent in ungerichteten Graphen Betrachten wir BFS, dann ist dieser in seiner Funktion bei ungerichteten Graphen prinzipiell das, was [[111.22_Graphen_SSSP_dijkstra]] in gerichteten Graphen macht.

Pseudocode:

for all u in V 
	u.color = white # not visited yet 
for all s in V 
	if s.color == white 
		BFS-Visit(G,s)
def BFS-Visit(G,s)
	s.color = grey # marked in progress
	Q = [s]# queue containing s now >> first to process
	while Q != empty():
		u = dequeue(Q)
		for all v in Adjacent(u) # all edges of current node 
			if v.color == white 
				v.color == grey 
				enqueue(Q,v)
			u.color=black

Wir möchten nochmal den ExploreGraph betrachten ( Kaufmann), aber dieses mal eine Queue nutzen für $S^{'}$ :

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')

[!Definition] ExploreGraph mit Queue wie läuft jetzt BFS ab? #card Es wird also mit jedem aufgenommenen Knoten $w$ ein neuer Eintrag in der Queue gesetzt ( er kommt an das Ende!) Dadurch wird er erst angeschaut, wenn alle zuvor ( also alle Nachbarn eines Knoten) besucht wurden ( Wir schauen uns also Wellen an!)

haben wir dann $w$ erreicht:

alle Nachbarn von $w$ werden danach chronologisch besucht / angeschaut. Danach deren Nachbarn komplett etcetc. ^1704708788138

Anwendung von BFS an Graph:

[!Example] Anwendung BFS an Graphen ![[Pasted image 20221111103047.png]] Betrachte folgenden Graphen, wie wird er mit BFS durchlaufen? #card

![[Pasted image 20221111103117.png]] ^1704708788146

Weitere Betrachtung:

Wenn wir einen ungerichteten Graphen mit einem BFS durchlaufen, können wir ferner ein Muster erkennen:

[!Definition] BFS traversiert in Schichten was meint die Aussage? #card Betrachten wir folgenden Graphen, sehen wir, dass bei diesem unter Anwendung von BFS die Knoten in Schichten durchgearbeitet werden. Dabei werden immer die benachbarten Knoten komplett abgearbeitet, bis eine nächste / neue Schicht geöffnet wird. ![[Pasted image 20231125185111.png]] ^1704708788154

| BFS Laufzeit |

Auch hier haben wir ähnliche Laufzeiten, wie mit einem DFS, bzw. ähnliche, wie mit dem Originalen Algorithmus (ExploreFrom(v)).

[!Important] Laufzeit mit Adjazenzliste: #card Mit einer Adjazenzliste werden wir folgende Laufzeit erhalten: $O (∣ E ∣ + ∣ V ∣)$ ^1704708788160

[!Important] Laufzeit mit einer Adjazenzmatrix #card Mit einer Adjazenzmatrix werden wir folgende Laufzeit bekommen: $O (∣ V^{2} ∣)$ Die Begründing ist hier gleich, wie bei DFS ^1704708788167

Difference of BFS - DFS ::

^1704708788174

Dfs travels “like ray”, BFS more “like a wave”
On high level: both nearly the same, main difference is that ==BFS utilises queue== where ==DFS uses a stack== ^1704708788182

Application : testing whether a graph is [[111.13_Graphen_basics#==Bipartite graphs==::|bipartite]]

durch sukzessives Einfärben der Knoten, um am Ende erkennen zu können, ob die Einfärbungen - rot oder grün für jede Menge - ==konfliktfrei== durchlaufen und somit bipartite sind ^1704708788199 oder wir treffen auf einen Konflikt - möchte rot einfärben, Target ist aber bereits grün >> somit nicht möglich - und sie sind nicht bipartite

==possible solution==:: ^1704708788208 Assume graph is connected - if not run algorithm on each of its components

Procedure

start at arbitrary vertex, color vertex red
for each neighbours of a ==red== vertex, we color them blue ^1704708788216
for each neighbour of a ==blue== vertex, we color them red ^1704708788225
The graph is bipartite if and only if we never encounter a color conflict - we find a ==red== vertex that now should be colored blue, or vice versa ) ^1704708788233

However this algorithm does not work with DFS, because there wer are exploring in depth first, thus not allowing the graps to be coloured correctly.

scattered-lenity