import collections
|
from typing import Mapping
|
|
from graphdemo import Graph
|
|
|
def bfs(g: Graph, start: int) -> Graph:
|
"""
|
|
:param g:
|
:param start:
|
:return:
|
"""
|
tree = Graph()
|
queue = collections.deque()
|
VISITED = "visited"
|
not_visited = {VISITED: False}
|
visited = {VISITED: True}
|
g.for_each_vertices(lambda v : g.merge_attribute(v, not_visited))
|
queue.append(start) # append() is the enqueue() operation of a Queue
|
g.merge_attribute(start, visited)
|
while queue:
|
u = queue.popleft() # popleft() is the dequeue() operation of a Queue
|
for v in g.adjacent_of(u):
|
if not g.get_attribute(v)[VISITED]:
|
tree.add_edge(u, v)
|
g.merge_attribute(v, visited)
|
queue.append(v)
|
return tree
|
|
|
def bfs_dict(g: Graph, start: int) -> Mapping[int, int|None]:
|
tree = {start:None}
|
queue = collections.deque()
|
VISITED = "visited"
|
not_visited = {VISITED: False}
|
visited = {VISITED: True}
|
g.for_each_vertices(lambda v : g.merge_attribute(v, not_visited))
|
queue.append(start) # append() is the enqueue() operation of a Queue
|
g.merge_attribute(start, visited)
|
while queue:
|
u = queue.popleft() # popleft() is the dequeue() operation of a Queue
|
for v in g.adjacent_of(u):
|
if not g.get_attribute(v)[VISITED]:
|
tree[v] = u
|
g.merge_attribute(v, visited)
|
queue.append(v)
|
return tree
|
pass
|
|
|
def find_path(g: Graph, u: int, v: int) -> list[int]:
|
tree = bfs_dict(g, v)
|
path = [u]
|
while (current := path[-1]) != v:
|
precedent = tree[current]
|
path.append(precedent)
|
return path
|
|
|
def find_path_gpt(g: Graph, u: int, v: int) -> list[int]:
|
# Erstelle einen BFS-Baum, beginnend bei Knoten v
|
bfs_tree = bfs_dict(g, v)
|
|
# Wenn u nicht in bfs_tree ist, gibt es keinen Pfad von u nach v
|
if u not in bfs_tree:
|
return [] # Kein Pfad gefunden
|
|
# Den Pfad von u nach v rekonstruieren
|
path = []
|
current = u
|
while current is not None:
|
path.append(current)
|
current = bfs_tree[current]
|
|
# Den Pfad umkehren, da wir rückwärts von u nach v gehen
|
path.reverse()
|
|
return path
|
