Topologische Sortierung

[Maultäschle]

Hey Leute,

ich hab da mal Fragen:
1. Spielen Kantengewichte bei der topologischen Sortierung eine Rolle?
2. Ist die topologische Sortierung eindeutig, also maximal eine topologische Sortierung pro Graph.

Danke im Voraus🙂

 

[TheFrog]

Guten Morgen,

1. der Beitrag hat nichts mit Java Grundlagen zu tun, es ist ein Thema der Informatik allgemein.
2. Wikipedia hat zur Topologischen Sortierung einen guten Eintrag.
3. Kantengewichte gibt es nicht. Du speicherst allerdings für jeden Knoten die Anzahl der Vorgänger (eingehende Pfeile).
4. Fur einen gerichteten Graphen kann es keine, eine oder auch mehrere topologische Sortierungen geben. Zyklische Graphen sind nicht top. sortierbar. Ein gerichteter Pfad ist eindeutig top. sortierbar und ein gerichteter Baum hat mehrere Sortierungen.