Algorithmensammlung: Graphentheorie

Aus Wikibooks

Algorithmensammlung: Graphentheorie

• Algorithmus von Kruskal
• Algorithmus von Prim
• Breitensuche (BFS - breadth first search)
• Dijkstra-Algorithmus
• Tiefensuche (DFS - depth first search)

[Bearbeiten] Graphentheorie

Algorithmen 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.

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