| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung |
| talit:algorithmen [2025-03-02 19:24] – hof | talit:algorithmen [2025-03-03 21:01] (aktuell) – [Aufgabe 4 - Graph Walk] hof |
|---|
| Wie könnten wir das Weg-Problem (von der KSR an den Bahnhof) abstrakt erfassen? Wir könnten die verschiedenen Wege zum Beispiel so erfassen: | Wie könnten wir das Weg-Problem (von der KSR an den Bahnhof) abstrakt erfassen? Wir könnten die verschiedenen Wege zum Beispiel so erfassen: |
| |
| | <figure graph_romis> |
| {{:talit:pasted:20220423-154956.png?600}} | {{:talit:pasted:20220423-154956.png?600}} |
| | <caption>Graph mit drei Pfaden zum Bahnhof</caption> |
| | </figure> |
| |
| Aus was besteht ein Graph? Aus **Knoten** (en. _nodes_ oder _vertices_) und **Kanten** (_edges_). In unserem Fall haben die Kanten **Gewichte**, die die Länge oder Fahrtdauer der einzelnen Strecken repräsentieren. | Aus was besteht ein Graph? Aus **Knoten** (en. _nodes_ oder _vertices_) und **Kanten** (_edges_). In unserem Fall haben die Kanten **Gewichte**, die die Länge oder Fahrtdauer der einzelnen Strecken repräsentieren. |
| |
| Wie könnten wir diesen Graphen in Python repräsentieren | Wie könnten wir diesen Graphen in Python repräsentieren? |
| ? | |
| #### Adjazenzmatrix | #### Adjazenzmatrix |
| |
| </code> | </code> |
| ++++ | ++++ |
| |
| ### Tiefensuche | ### Tiefensuche |
| |
| Bevor wir den schnellsten Weg an den Bahnhof zu finden versuchen, wären wir schon mal nur froh, überhaupt einen Weg zu finden. Es könnte ja auch sein, dass wir uns in die Turnhalle begeben, von wo kein Weg zum Bahnhof führt. Oder dass wir von der Bahnhofstrasse zurück zur KSR gelangen: | Bevor wir den schnellsten Weg an den Bahnhof zu finden versuchen, wären wir schon mal nur froh, überhaupt einen Weg zu finden. Es könnte ja auch sein, dass wir uns in die Turnhalle begeben, von wo kein Weg zum Bahnhof führt. Oder dass wir von der Bahnhofstrasse zurück zur KSR gelangen: |
| | |
| | <figure graph_romis2> |
| | [[http://magjac.com/graphviz-visual-editor/?dot=digraph%20Romanshorn%20%7B%0A%20%20%20%20rankdir%3DTB%3B%0A%09node%20%5Bshape%20%3D%20doublecircle%3B%20width%3D1%5D%3B%20KSR%20Bahnhof%3B%0A%09node%20%5Bshape%20%3D%20circle%3B%20width%3D1%3B%20fixedwidth%3Dtrue%5D%3B%0A%09KSR%20-%3E%20Turnhalle%20%5B%20label%20%3D%201%20%5D%3B%0A%09KSR%20-%3E%20Weitenzelgstr%20%5B%20label%20%3D%201%20%5D%3B%0A%09Weitenzelgstr%20-%3E%20Bahnhofstr%20%5B%20label%20%3D%208%20%5D%3B%0A%09KSR%20-%3E%20Sek%20%5B%20label%20%3D%202%20%5D%3B%0A%09Sek%20-%3E%20Bahnhofstr%20%5B%20label%20%3D%203%20%5D%3B%0A%09Bahnhofstr%20-%3E%20Bahnhof%20%5B%20label%20%3D%207%20%5D%3B%0A%09Bahnhofstr%20-%3E%20KSR%20%5B%20label%20%3D%204%20%5D%3B%0A%09Sek%20-%3E%20Hafenstrasse%20%5B%20label%20%3D%205%20%5D%3B%0A%09Hafenstrasse%20-%3E%20Bahnhof%20%5B%20label%20%3D%204%20%5D%3B%0A%09Sek%20-%3E%20Zelgstrasse%20%5B%20label%20%3D%207%20%5D%3B%0A%09Zelgstrasse%20-%3E%20Bahnhof%20%5B%20label%20%3D%205%20%5D%3B%0A%7D%0A|{{:talit:pasted:20220521-145117.png?400|Graph}}]] |
| | <caption>Detaillierter Graph von der KSR zum Bahnhof</caption> |
| | </figure> |
| |
| |
| [[http://magjac.com/graphviz-visual-editor/?dot=digraph%20Romanshorn%20%7B%0A%20%20%20%20rankdir%3DTB%3B%0A%09node%20%5Bshape%20%3D%20doublecircle%3B%20width%3D1%5D%3B%20KSR%20Bahnhof%3B%0A%09node%20%5Bshape%20%3D%20circle%3B%20width%3D1%3B%20fixedwidth%3Dtrue%5D%3B%0A%09KSR%20-%3E%20Turnhalle%20%5B%20label%20%3D%201%20%5D%3B%0A%09KSR%20-%3E%20Weitenzelgstr%20%5B%20label%20%3D%201%20%5D%3B%0A%09Weitenzelgstr%20-%3E%20Bahnhofstr%20%5B%20label%20%3D%208%20%5D%3B%0A%09KSR%20-%3E%20Sek%20%5B%20label%20%3D%202%20%5D%3B%0A%09Sek%20-%3E%20Bahnhofstr%20%5B%20label%20%3D%203%20%5D%3B%0A%09Bahnhofstr%20-%3E%20Bahnhof%20%5B%20label%20%3D%207%20%5D%3B%0A%09Bahnhofstr%20-%3E%20KSR%20%5B%20label%20%3D%204%20%5D%3B%0A%09Sek%20-%3E%20Hafenstrasse%20%5B%20label%20%3D%205%20%5D%3B%0A%09Hafenstrasse%20-%3E%20Bahnhof%20%5B%20label%20%3D%204%20%5D%3B%0A%09Sek%20-%3E%20Zelgstrasse%20%5B%20label%20%3D%207%20%5D%3B%0A%09Zelgstrasse%20-%3E%20Bahnhof%20%5B%20label%20%3D%205%20%5D%3B%0A%7D%0A|{{:talit:pasted:20220521-145117.png?400}}]] | |
| #### Aufgabe 2 | #### Aufgabe 2 |
| |
| ++++ | ++++ |
| </nodisp> | </nodisp> |
| |
| #### Aufgabe 4 - Graph Walk | #### Aufgabe 4 - Graph Walk |
| |
| **Aufgabe**: Schreibe eine Funktion `dfs(graph)`, die die Knoten eines Graphen mittels Tiefensuche ausgibt. | **Aufgabe**: Schreibe eine Funktion `dfs(graph)`, die die Knoten eines Graphen mittels Tiefensuche ausgibt. |
| * Die Ausgabe kann mit `print()` erfolgen oder eine Liste zurückgeben. | * Die Ausgabe kann mit `print()` erfolgen oder eine Liste zurückgeben. |
| * Herausforderung: schreibe eine [[https://en.wikipedia.org/wiki/Generator_(computer_programming)#Python|Generator-Funktion]] mit dem `yield` Keyword. | * Herausforderung: schreibe eine [[talit:generators|Generator-Funktion]] mit dem `yield` Keyword. |
| |
| <nodisp 1> | <nodisp 1> |
| ++++ | ++++ |
| </nodisp> | </nodisp> |
| | ### Visualisierung |
| | Mit Folium lassen sich die gefundenen Pfade hübsch visualiseren. Der Code für untenstehende Grafik findet sich auf [[https://github.com/tkilla77/ksr_talenta_graphs/blob/main/sbb.ipynb|github]]. |
| | |
| | <figure shortest_path> |
| | {{:talit:algorithmen:pasted:20250302-193146.png?nolink}}<caption>Pfad von Romanshorn nach Bern --- Rot: BFS, Grün: DFS, Blau: Dijkstra</caption> |
| | </figure> |
hof