topologische Sortierung

[pramort]

Hallo zusammen,

ich würde mich sehr freuen, wenn mir jemand mit dem folgenden Problem helfen könnte..
Ich versuche gerade, einen Algorithmus umzusetzen, der eine topologische Sortierung eines Graphen ausgibt. Als erstes will ich Eingangsgrade der Knoten berechnen. Überall wird angegeben, dass dies in linearer Zeit möglich ist. Ich habe eine Vermutung, dass die Laufzeit meiner Version quadratisch ist.. Könnte mir jemand bitte sagen, ob das tatsächlich so ist?

//adjLists[u][j] is the j-th neighbor of vertex u in G
for(int i = 0; i < adjLists.length; i++) {
   //outdegrees[u] is the out-degree of vertex u in G
   for(int j = 0; j < outdegrees[i]; j++) {
      indegrees[adjLists[i][j]] = indegrees[adjLists[i][j]] + 1;
   }
}

Danke für eure Hilfe!

 

[mrBrown]

Überall wird angegeben, dass dies in linearer Zeit möglich ist.

Linear zu was? 😉

Wenn ich dein Code-Stück richtig interpretiere, läuft die äußere Schleife über alle Knoten und die innere über alle ausgehenden Kanten dieses Knotens - insgesamt also über alle Kanten genau einmal -> ist also linear zur Kantenzahl, aber nicht linear zur Knotenzahl.

EDIT: Kantenzahl zu Knotenzahl geändert -.-

 

[Xyz1]

Linear zu was?

Zur Knotenanzahl davon wird üblicherweise ausgegangen.

ist also linear zur Kantenzahl, aber nicht linear zur Kantenzahl.

mrBrown ist schon leicht tüdelig.


An den TE : Von einer Adjazenzliste hast du in Deiner Frage nichts geschrieben, wäre toll wenn du diese nicht nehmen würdest. 🙂 Das verringert die Zeit in erheblichem Maße. 🙂

 

[mrBrown]

mrBrown ist schon leicht tüdelig.

Danke für den Hinweis^^

An den TE : Von einer Adjazenzliste hast du in Deiner Frage nichts geschrieben, wäre toll wenn du diese nicht nehmen würdest. 🙂 Das verringert die Zeit in erheblichem Maße. 🙂

Inwiefern geht Eingangsgrade ermitteln mit Adjazenzmatrix oder Kantenliste schneller?

 

[Xyz1]

Inwiefern geht Eingangsgrade ermitteln mit Adjazenzmatrix oder Kantenliste schneller?

quadratische Zeit vermeiden ist gut.

Es kommt auf den Problemgraph an.

Will pramort eigentlich noch was wissen?

 

[mrBrown]

Ich will auf jeden Fall was wissen: was Adajzenzmatrix oder Kantenliste beim ermitteln des Eingangsgrades schneller macht, als Adjazenzliste.

Und bitte nicht nur Inhaltsleere Floskeln.

 

[Xyz1]

Und bitte nicht nur Inhaltsleere Floskeln.

Naja, wenn dich 0en interessieren kannst gerne jedes mal über ne komplette Matrix laufen.

Außerdem gewöhne dir richtige Begriffe an.

 

[mrBrown]

Du schaffst es wohl wirklich nicht, auf eine ganz einfache Frage zu antworten. Wohl typischer Fall von völlig Ahnungslos...

 

[pramort]

Hallo liebe Leute!
Ich war über ein paar Tage weg und kann mich leider erst jetzt für eure Hinweise bedanken!

Mein Problem ist einfach, dass ich versuche, topologische Sortierung in Zeit O(|V|+|E|) umzusetzen. Dabei versuche ich als Erstes Eingangsgrade der Knoten zu berechnen. Verstehe ich es richtig, dass wenn der o.g. Code-Teil in quadratischer Laufzeit läuft, dann komme ich ja nicht auf lineare Zeit (|V|+|E|) des gesamten Algorithmus? In meinem Skript steht, dass es möglich ist, Eingangsgrade in Zeit |E| zu berechnen (die Schleife in Schritt 3). Die Schleifen in den Schritten 2 und 4 haben eine Laufzeit O(|V|).

 

[Xyz1]

In meinem Skript steht, dass es möglich ist, Eingangsgrade in Zeit |E| zu berechnen

Dein Script ist nicht falsch.

(die Schleife in Schritt 3)

Ich brauch aber 30-60 Minuten dafür um den "Pseudocode" zu verstehen.
Die Zeit habe ich gerad nicht.

Vielleicht nochmal Das Problem und Lösung einmal beschreiben dann denke ich mir selbst was aus... 🙂 (brauch ich für evtl. nur 20 Minuten)

 

[mrBrown]

Verstehe ich es richtig, dass wenn der o.g. Code-Teil in quadratischer Laufzeit läuft, dann komme ich ja nicht auf lineare Zeit (|V|+|E|) des gesamten Algorithmus?

Dein obiger Code läuft nicht in quadratischer Zeit, sondern linear.
Deine äußere Schleife läuft über alle Knoten.
Die innere läuft für jeden Knoten über dessen Kanten, also insgesamt über alle Kanten das Graphen.

Macht |V|+|E|.

Das Skript nutzt für die Kanten allerdings eine Kantenliste, hier muss man nur einmal über alle Kanten laufen - also |E|

 

[mihe7]

Wenn ich mich auf die Schnelle nicht vertan habe, dürften die Zeitkomplexitäten im Skript wie folgt sein:

Zeile 1: O(1)
Zeile 2: O(|V|), bis dahin O(|V|)
Zeile 3: O(|E|), bis dahin O(|V| + |E|)
Zeilen 4-5: O(|V|), bis dahin O(|V| + |E|)
Zeile 6: O(1), bis dahin O(|V| +|E|)
Zeilen 7 bis 12 sind nicht ganz trivial: die beiden Schleifen erwecken den Anschein, als würde hier |V|*|E| gelten, das ist aber nicht der Fall, denn es werden für jeden Knoten nur die von ihm ausgehenden Kanten berücksichtigt. Am Ende werden also alle Knoten und Kanten des Graphen einmal durchlaufen: O(|V| + |E|)
Zeile 13: O(1), Gesamt: O(|V|+|E|)

 

[pramort]

Vielen Dank euch allen!!

 

[pramort]

Das Skript nutzt für die Kanten allerdings eine Kantenliste, hier muss man nur einmal über alle Kanten laufen - also |E|

Könntest du mir bitte kurz erklären, wie so eine Liste aufgebaut ist. Also, ich weiß, was eine Liste ist. Ich verstehe nur nicht, wie man mit einer Schleife alle Kanten durchlaufen kann. Z.B. habe ich ein Array und jedes Arrayelement ist eine Liste. So z.B. arr[0] - hier drin sind alle Kanten als Liste, die von diesem Knoten ausgehen. Wie könnte man diese Struktur mit nur einer Schleife durchlaufen? Danke nochmals für deine Hilfe!

 

[mrBrown]

Könntest du mir bitte kurz erklären, wie so eine Liste aufgebaut ist. Also, ich weiß, was eine Liste ist. Ich verstehe nur nicht, wie man mit einer Schleife alle Kanten durchlaufen kann. Z.B. habe ich ein Array und jedes Arrayelement ist eine Liste. So z.B. arr[0] - hier drin sind alle Kanten als Liste, die von diesem Knoten ausgehen. Wie könnte man diese Struktur mit nur einer Schleife durchlaufen? Danke nochmals für deine Hilfe!

Das was du nutzt ist eine Ajazenzliste, zu jedem Knoten werden dabei alle ausgehende Kanten gespeichert.

So etwa :
1: 2,3
2: 3
3:
(1 hat Kante zu 2 und 3, 2 nur zu 3, 3 keine ausgehenden)

Bei einer Kantenliste speichert man nur alle Kanten:
(1,2),(1,3)(2,3)
(Kanten von 1 zu 2, von 1 zu 3, von 2 zu 3)

 

[pramort]

Bei einer Kantenliste speichert man nur alle Kanten:
(1,2),(1,3)(2,3)
(Kanten von 1 zu 2, von 1 zu 3, von 2 zu 3)

Jetzt ist alles klar, danke schön!