From 8a9933e4decb3b6a57b47b6409474bd476920c24 Mon Sep 17 00:00:00 2001
From: Hong-Phuc Bui <hong-phuc.bui@htwsaar.de>
Date: Fri, 27 Sep 2024 01:22:49 +0200
Subject: [PATCH] demo show image
---
stundenplan/src/pygraph/shortestpath.py | 53 ++++++++++++++++++++++++++++++++++++++++++++++++++++-
1 files changed, 52 insertions(+), 1 deletions(-)
diff --git a/stundenplan/src/pygraph/shortestpath.py b/stundenplan/src/pygraph/shortestpath.py
index 4426f95..5d3e2af 100644
--- a/stundenplan/src/pygraph/shortestpath.py
+++ b/stundenplan/src/pygraph/shortestpath.py
@@ -1,9 +1,10 @@
import collections
+from typing import Mapping
from pygraph.graphdemo import Graph
-def bfs(g: Graph, start: int) -> {int:int|None}:
+def bfs(g: Graph, start: int) -> Graph:
"""
:param g:
@@ -26,3 +27,53 @@
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
\ No newline at end of file
--
Gitblit v1.10.0-SNAPSHOT