Algorithmensammlung: Graphentheorie
Algorithmensammlung: Graphentheorie
- Algorithmus von Kruskal
- Algorithmus von Prim
- Breitensuche (BFS - breadth first search)
- Dijkstra-Algorithmus
- Tiefensuche (DFS - depth first search)
Graphentheorie
BearbeitenAlgorithmen aus der Graphentheorie finden im Computer im großen Stil Anwendung, da sich viele Datenstrukturen gut mit Graphen abbilden lassen. So wird eine HTML-Webseite intern als gewurzelter Baum behandelt. Die freie Python-Bibliothek NetworkX enthält viele wichtige Algorithmen.
Bei der Darstellung von Graphen am Computer verwendet man in der Regel die Adjazenzlistendarstellung oder bildet den Graphen auf Objekte ab.
| Hinweis |
| Für Autoren: Für Algorithmen in dieser Kategorie sollte einheitlich die Adjazenzlistendarstellung verwendet werden oder, falls die jeweilige Sprache standardmäßig eine Struktur zur Repräsentation von Graphen mitbringt, diese. Im Fall von gewurzelten Bäumen ist eventuell auch das DOM sinnvoll |