demo show image

Hong-Phuc Bui

2024-09-27 8a9933e4decb3b6a57b47b6409474bd476920c24

 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