Hallo,
hätte jemand eine Idee?
Gegeben sei ein gerichteter Graph G = (V,E) mit den Knoten V und den Kanten E. Wir konstruieren daraus den transponierten Graphen GT = (V,ET) mit ET = {(v,u) ∈ V × V : (u,v) ∈ E}, der gerade G mit den umgekehrten Kanten enthält. Beschreiben Sie einen effizienten Algorithmus für die Berechnung von GT aus G, wenn die Repräsentation des Graphen als adjazenzmatrix und adjazenzliste vorliegt.
Mir ist nicht klar, was für Algorithmus ich schreiben soll.. Bei adjazenzmatrix wird ja von Zeilen Spalten gemacht. Und was soll ich damit machen? Ich muss noch die Laufzeit angeben.
hätte jemand eine Idee?
Gegeben sei ein gerichteter Graph G = (V,E) mit den Knoten V und den Kanten E. Wir konstruieren daraus den transponierten Graphen GT = (V,ET) mit ET = {(v,u) ∈ V × V : (u,v) ∈ E}, der gerade G mit den umgekehrten Kanten enthält. Beschreiben Sie einen effizienten Algorithmus für die Berechnung von GT aus G, wenn die Repräsentation des Graphen als adjazenzmatrix und adjazenzliste vorliegt.
Mir ist nicht klar, was für Algorithmus ich schreiben soll.. Bei adjazenzmatrix wird ja von Zeilen Spalten gemacht. Und was soll ich damit machen? Ich muss noch die Laufzeit angeben.
