Eine Kante (englisch edge) ist in der Graph-Datenstruktur die Verbindung zwischen zwei Knoten.
Gerichtet oder ungerichtet
Bei einer ungerichteten Kante ist die Verbindung symmetrisch: Sie führt von A nach B und genauso von B nach A. Bei einer gerichteten Kante (Pfeil) gibt es eine eindeutige Richtung von A nach B. Graphen mit gerichteten Kanten heißen Digraphen und sind typisch für Abhängigkeiten, Navigationsnetze oder soziale Netzwerke mit Follower-Beziehung.
Kantengewichte
Kanten können ein Gewicht tragen, etwa eine Entfernung, Kosten oder Laufzeit. Der Dijkstra-Algorithmus findet kürzeste Wege über gewichtete Kanten, der Bellman-Ford-Algorithmus funktioniert zusätzlich mit negativen Kantengewichten.
Kanten in Bäumen
Ein Baum ist ein zusammenhängender Graph mit genau n Knoten und n − 1 Kanten. Der minimale Spannbaum wählt aus allen möglichen Kanten diejenigen aus, die alle Knoten mit minimalem Gesamtgewicht verbinden.
Kanten speichern
Die Adjazenzliste speichert für jeden Knoten seine ausgehenden Kanten, die Adjazenzmatrix markiert jedes Knotenpaar mit einer Kanten-Eintragung. Beide Darstellungen sind äquivalent, unterscheiden sich aber im Speicher- und Zugriffsverhalten.