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?
Danke für eure Hilfe!
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?
Java:
//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!