def entsch_Path(G,s,t): edges = G

next_nodes = [s]
nodes_visited = {s}


while len(next_nodes) != 0:
    node = next_nodes.pop(0)

    if node == t:
        return '1'
    else:
        for edge in edges:
            if edge[0] == node:
                if edge[1] not in nodes_visited:
                    next_nodes.append(edge[1])
                    nodes_visited.add(edge[1])

return '0'

if name == 'main':

edge_list = [(1,2),(2,3),(2,4),(2,2),(4,5),(6,3)]

print(entsch_Path(edge_list,1,6))

Wir betrachten das Programm path.py, welches Sie in Moodle unter “zusa ̈tzliches Material” finden. Als Eingabe erha ̈lt die Funktion entsch Path(G,s,t) einen Graphen G, kodiert als Liste der Kanten (die wir auch als E bezeichnen), und zwei Knoten s und t. Die Menge der Knoten V in G ergibt sich aus der Menge der Kanten.

a) Die Funktion entsch Path(G,s,t) in path.py erreicht die in der Vorlesung angegebene Zeit- schranke fu ̈r Path von O(|V | + |E|) nicht. Geben Sie an, welche Zeitkomplexita ̈t das Programm entsch Path(G,s,t) in Abha ̈ngigkeit der Gro ̈ßen von V und E hat. Gesucht ist hier nicht eine exakte Angabe, sondern die asymptotisch am schwa ̈chsten wachsende Funktion f(|V|,|E|), welche die Laufzeit beschra ̈nkt. Begru ̈nden Sie anhand des Algorithmus, warum dieser langsamer als O(|V | + |E|) ist.

b) Beschreiben Sie kurz, wie der Algorithmus verbessert werden kann, um sich der Zeitkomplexita ̈t von O(|V | + |E|) anzuna ̈hern. Diese Schranke muss durch die angegebene Verbesserung nicht erreicht werden. Ihre Verbesserung sollte sich aber um mehr als einen konstanten Faktor auf die Zeitschranke aus a) auswirken.