Frage zur topologischen Sortierung

[Reality]

Hallo,
ich bin gerade dabei eine topologische Sortierung in Java zu implementieren und ich frage mich, wie ich das am Besten effizient mache.
Ich habe hier im Forum einen Code-Beispiel gefunden, allerdings stolpere ich gerade an eine Stelle, die ich nicht ganz verstehe.
Mein Problem ist, dass wenn ich den Code im Kopf durchgehe, dass dann die Indizes von inCount[] bei der ersten For-Schleife, nicht mit den Indizes bei der zweiten, inneren For-Schleife übereinstimmen.
Angenommen der 10. Knoten hat keine Vorgänger, dann wird dieser zuerst in die Queue eingefügt. In der While-Schleife wird dieser dann zuerst abgearbeitet. Die Nachfolger von dem Startknoten haben nun die Indizes 10 oder größer, tatsächlich fängt man aber in der inneren For-Schleife bei 0 an.
Habe ich da einen Denkfehler? Kann mich jemand aufklären?

public static int[] topologicSort(Graph g) {

	LinkedQueue q = new LinkedQueue();
	int[] result = new int[g.size()];
	int[] inCount = new int[g.size()];
	int i = 1;

	for (int j = 0; j < g.size(); j++) {
		inCount[j] = g.edgesIn(j);
		if (inCount[j] == 0) //Angenommen j sei 9, dann wird der 10. Knoten in die Queue hinzugefügt.
			q.enqueue(new Integer(j));
	}
	while (!q.isEmpty()) { // Am Anfang wird erst mal der Startknoten bearbeitet...
		int u = ((Integer) (q.dequeue())).intValue();
		result[i - 1] = u;
		i++;
		for (int w = 0; w < g.size(); w++) {
			if (g.hasEdge(u, w)) { // Hier werden lediglich die Nachfolger von u betrachtet! Angenommen, beim ersten Durchlauf existiert ein Nachfolger w von u...
				inCount[w]--; // Beim ersten Durchlauf ist w noch 0. Also wird inCount in einer anderen Reihenfolge abgearbeitet als in der oberen For-Schleife am Anfang.
				if (inCount[w] == 0)
					q.enqueue(new Integer(w));
			}
		}
	}
	return result;
}

Danke, im Voraus!

L. G.
Reality

 

[Marco13]

Erstens sollte man den Code selbst schreiben. Zweitens muss man nicht davon ausgehen, dass irgendein Code, den man in irgendeinem einzelnen, unkommentierten Forenbeitrag findet, "richtig" ist. Drittens ... könnte er aber richtig sein, aber mir ist nicht klar, warum die Reihenfolge, in der die Knoten abgearbeitet werden, Fragen aufwirft. Hast du ihn mal getestet? Wie so oft, ein paar
System.out.println("Bearbeite "+x+" mit Vorgängern "+y+" und Nachfolgern "+z);
könnten schon die nötigen Einsichten bringen. Niemand hat gesagt, dass es einfach ist.

 

[Reality]

Hi,
keine Angst, ich habe vor das anders zu implementieren. Er macht das mit Arrays und ich mit HashMaps, deswegen bin ich da auch ein bisschen durcheinenader gekommen, was die Indizes angeht. Das hat sich nun geklärt.

Schönen Sonntag noch!

L. G.
Reality