Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Topological Sort?
void topologicalSort(int x){
if(nodes[x-1] == null){
System.out.println("Keine richtige Sortierung möglich");
return;
}
LinkedList Q = new LinkedList();
LinkedList L = new LinkedList();
int[] s = new int[nodes.length];
for(int i = 0; i < s.length; i++){
s[i] = 0;
}
int index = 1;
Q.addFirst(new Integer(x-1));
while(!Q.isEmpty()){
Integer z = (Integer) Q.getLast();
Q.removeLast();
L.addFirst(z);
s[z.intValue()] = index++;
if(nodes[z.intValue()] != null){
AdjListenElement e = nodes[z.intValue()];
while (e != null){
Integer y = new Integer(e.getNodeNumber() - 1);
if(!Q.contains(y) && !L.contains(y)){
Q.addFirst(y);
}
e = e.getNext();
}
}
}
for(int i = 0; i < s.length; i++){
System.out.println("Knoten " + (i+1) + " : " + s[i]);
}
}
Gut so? Hab ich den Sinn verstanden?
was bedeutet denn dein parameter x? muesste das nicht parameterlos sein?
Ich geb dem einen Startknoten mit. Der Algorithmus braucht ja einen, und wenn ich standardmäßig z.B. den 1. nehme, könnte es ja sein dass nur Mist rauskommt. Evtl könnte man für jeden Startknoten eine top. Sortierung erstellen und dann z.B. die nehmen, die am längsten gedauert hat oder so. Oder bei der die meisten Knoten auch eine Zahl zugewiesen bekommen haben. K.A.
Noch eine Frage: Wenn ich eine Queue haben will (oder Stack, halt irgendwas Listenartiges), die int speichern soll, welche gibts da in Java schon? Diese ArrayList ist ja schön und gut, aber speichert halt immer nur Object, und dann muss ich andauernd zwischen Object und Integer hin und her machen.
Was nehm ich da am besten?
Hab ich jetzt den Sinn der topologischen Sortierung verstanden?
War das nicht so, dass alle Knoten in eine Reihenfolge gebracht werden, dass die Kanten nur auf nachfolgende Knoten zeigen, und keiner wieder zurück geht? (Zyklenfreiheit vorausgesetzt)
Ist diese Sortierung überhaupt eindeutig? Kann ich mir nicht ganz vorstellen. Und wenn in der Sortierung alle Knoten berücksichtigt werden sollen, ist es doch egal, wo ich anfange?
Soweit ich weiß, musst du dir dann schnell selbst eine Klasse schreiben. So ganz triviale Arrays (keine Objekte, sondern echte Arrays wie in C) gibt es in Java scheinbar nicht. Würde auch in das (sowieso schon recht versaute) Objekt-Konzept nicht reinpassen.
Was macht eigentlich das erste if? Prüft das, ob der Startknoten irgendwelche Nachfolger hat und entscheidet dann, ob eine topologische Sortierung möglich ist?
Das wäre imho allerdings nicht ganz korrekt. Eine topologische Sortierung ist nicht möglich, wenn ein Zyklus vorhanden ist, sprich eine Ordnungszahl vergeben wird, die größer als die Anzahl der Knoten ist (Hab jetzt nicht geschaut, ob das Programm das macht). Anderer Zyklusfall besteht, wenn man keinen Knoten findet, der einen Indegree von 0 hat. Also man findet keinen Knoten, der keine eingehenden Pfade hat.
Aber es ist nicht wichtig, dass ein Knoten Nachfolger hat.
Topologische Sortierungen müssen, glaube ich, nicht zwangsläufig eindeutig sein. In irgendeiner Algoklausur war so ein Graph gegeben, bei dem die Indegree Sortierung für einen Knoten etwas anderes ergeben hat, als diese andere Variante, die auch in der Lösung des Übungsblattes 8 steht. (Sofern ich nichts falsch gemacht habe)
Also, das stimmt schon dass, eine top. Sortierung bei einem Graphen mit Zyklen nicht geht , aber ich hab mir das so gedacht, dass wenn ein Knoten entweder in L oder Q ist, ich ihn nicht mehr weiterverfolge. Dass ist dann praktisch wie eine top. Sortierung gemischt mit dem Algorithmus für den aufspannenden Baum (richtig???).
Auf jedenfall stoppt der Algorithmus, wenn er auf einen Zyklus trifft und überspringt den (zum 2. Mal auftretenden) Knoten.
Beim indegree-Algorithmus geht das gar nicht, weil sobald ein Zyklus auftritt, keine zeroInNode mehr gibt:
z.B. Pfad 1-2, 2-3, 3-1 : Jeder Knoten hat indegree von 1, zeroInNodes ist leer.
Und die 1. If Abfrage hat nur den Sinn, dass er keine Sortierung ausgibt, bei der nur 1 Knoten eine Ordnungszahl bekommen hat.