Java Schleife abbrechen bzw. wieder bei 0 beginnen? Topologische Sortierung

[Slight]

Halloo

Ich habe eine topologische Sortierung programmiert, eigentlich funktioniert auch alles, aber wenn es mehrere Knoten mit Eingangsgrad=0 gibt, soll der Knoten mit dem kleinsten Index genommen werden.

Ich habe mir das jetzt so vorgestellt, dass die erste for-Schleife zuerst den ersten Knoten mit Eingangsgrad=0 findet, also auch den mit dem kleinsten Index, dann sollen ALLE Kanten die mit der Kante verbunden sind, entfernt werden, und der Knoten soll zu sortedNodes hinzugefügt werden. Nach meiner Ausgabe werden aber komischerweise direkt beide Knoten mit dem Eingangsgrad=0 entfernt, und auch nur je eine Kante. Das sieht man ja da, wo zum ersten Mal SortedNodes gefüllt ist mit 5 und 7. 7-6 und 5-1 wurden entfernt, aber nicht 5-4 und 7-8.
Mein eigentliches Problem ist aber, dass die 7 vor der 1 ausgegeben wird. Denn wenn die 5 entfernt wird, hat eigentlich die 1 schon den Eingangsgrad=0 und weil eben zuerst immer die mit dem kleinsten Index entfernt werden sollen, sollte dann nach der 5 die 1 kommen, es wird aber die 7 ausgegeben, weil die Schleife ja einmal komplett durchläuft und dann ja natürlich nach der 5 erst die 7 findet und nicht die 1.
Ich wollte mein Problem lösen, indem ich die Schleife abbreche, sobald die 5 gefunden wurde, damit sie wieder bei 0 beginnt, eigentlich müsste doch dann die 1 vor der 7 gefunden werden oder? Jedoch habe ich das schon mit break versucht, die Ausgabe ändert sich zwar, aber die 1 steht immer noch nach der 7. Kann mir da vielleicht jemand weiterhelfen?

while(!(G.getNodes().isEmpty()))
		{	
			for (int i=0; i<G.getNodes().size(); i++)
			{
				if(G.getNodes().get(i).indegree==0)
				{
					sortedNodes.add(G.getNodes().get(i));
					G.removeNode(G.getNodes().get(i));
				}
				for (int j=0; j<G.getEdges().size(); j++) 
				{
					if(sortedNodes.contains(G.getEdges().get(j).getSecondNode())||sortedNodes.contains(G.getEdges().get(j).getFirstNode()))
					{
						G.removeEdge(G.getEdges().get(j));
					}
					indegree(G);
				}

				System.out.println("Sorted Nodes:"+sortedNodes+"\n"+ "Edges:"+G.getEdges()+"\n"+ "Nodes:"+G.getNodes()+"\n");
			}
		}
		System.out.println("Sorted Nodes:"+sortedNodes);
	}

Meine Ausgabe:

Anfangswerte:
Nodes:[1, 6, 4, 2, 5, 9, 7, 3, 8]
Edges:[1-2, 1-3, 7-6, 7-8, 7-4, 5-4, 5-1, 6-8, 6-2, 5-6, 2-9]
Eingangsgrad von1:1
Eingangsgrad von6:2
Eingangsgrad von4:2
Eingangsgrad von2:2
Eingangsgrad von5:0
Eingangsgrad von9:1
Eingangsgrad von7:0
Eingangsgrad von3:1
Eingangsgrad von8:2

Schleifen-Durchläufe ergeben folgendes:
Sorted Nodes:[]
Edges:[1-2, 1-3, 7-6, 7-8, 7-4, 5-4, 5-1, 6-8, 6-2, 5-6, 2-9]
Nodes:[1, 6, 4, 2, 5, 9, 7, 3, 8]

Sorted Nodes:[]
Edges:[1-2, 1-3, 7-6, 7-8, 7-4, 5-4, 5-1, 6-8, 6-2, 5-6, 2-9]
Nodes:[1, 6, 4, 2, 5, 9, 7, 3, 8]

Sorted Nodes:[]
Edges:[1-2, 1-3, 7-6, 7-8, 7-4, 5-4, 5-1, 6-8, 6-2, 5-6, 2-9]
Nodes:[1, 6, 4, 2, 5, 9, 7, 3, 8]

Sorted Nodes:[]
Edges:[1-2, 1-3, 7-6, 7-8, 7-4, 5-4, 5-1, 6-8, 6-2, 5-6, 2-9]
Nodes:[1, 6, 4, 2, 5, 9, 7, 3, 8]

Sorted Nodes:[5, 7]
Edges:[1-2, 1-3, 7-8, 5-4, 6-8, 6-2, 2-9]
Nodes:[1, 6, 4, 2, 9, 3, 8]

Sorted Nodes:[5, 7, 1]
Edges:[1-3, 5-4, 6-8, 6-2, 2-9]
Nodes:[6, 4, 2, 9, 3, 8]

Sorted Nodes:[5, 7, 1]
Edges:[5-4, 6-8, 6-2, 2-9]
Nodes:[6, 4, 2, 9, 3, 8]

Sorted Nodes:[5, 7, 1]
Edges:[6-8, 6-2, 2-9]
Nodes:[6, 4, 2, 9, 3, 8]

Sorted Nodes:[5, 7, 1, 3, 6]
Edges:[6-2, 2-9]
Nodes:[4, 2, 9, 8]

Sorted Nodes:[5, 7, 1, 3, 6]
Edges:[2-9]
Nodes:[4, 2, 9, 8]

Sorted Nodes:[5, 7, 1, 3, 6, 8, 4]
Edges:[2-9]
Nodes:[2, 9]

Sorted Nodes:[5, 7, 1, 3, 6, 8, 4, 2]
Edges:[]
Nodes:[9]

Sorted Nodes:[5, 7, 1, 3, 6, 8, 4, 2, 9] Das ist nun die topologische Sortierung, aber die 1 sollte auf jeden Fall vor der 7 sein.


Liebe Grüße

 

[miac]

Also, ohne den Code jetzt durchzuschauen:
Häufiger Fehler ist, daß Elemente gelöscht und sortiert werden, ohne auf die Schleifenvariable Rücksicht zu nehmen.

So stimmen dann die Indizes nicht mehr. Hast Du das berücksichtigt?

Beispiel: Bei einer einfachen Liste wird der aktuelle Eintrag gelöscht. Damit rückt der Nachfolger an diesen Platz. Die Logik innerhalb der Schleife müßte mit gleichem Index nochmal durchlaufen werden, der maximale Index müßte um eins verringert werden.

 

[Slight]

Ich glaube schon dass ich das berücksichtigt habe, indem ich bei den Schleifen, for (int i=0; i<G.getNodes().size(); i++) und for (int j=0; j<G.getEdges().size(); j++) die Abbruchbedingung abhängig von der Größe der Listen gemacht habe, d.h. wenn z.B. in der Edge-Liste kein Eintrag mehr ist, wird die zweite Schleife auch nicht mehr durchlaufen.

 

[miac]

Ja, das Ändern der Abbruchbedingugn ist in Java erlaubt.

Bleibt also das korrigieren des Index Zugriffs.

Ich sehe im Code, daß Du mit Add und Remove offenbar Elementverschiebungen bezüglich des Indexes durchführst. Hast Du das im Index berücksichtigt?

 

[Slight]

Danke erstmal für die Antworten
Ich weiß aber irgendwie nicht genau worauf du hinaus möchtest, weil ich denke, dass mit dem Index alles stimmt, es wird ja alles ausgegeben, es kommt auch keine Fehlermeldung. Ich weiß ja auch wieso die Reihenfolge falsch ausgegeben wird, deswegen möchte ich ja, dass die Schleife mittendrin, also nach der 5, abgebrochen wird, nachdem alle Kanten die mit 5 verbunden sind gelöscht wurden. Dann müsste doch eigentlich alles an der richtigen Stelle ausgegeben werden. Nur ich frage mich wieso das mit break nicht klappt.

 

[striker159]

Schau dir den Ablauf doch mal im Debugger Schritt für Schritt an.

Überschreibt deine Node Klasse die equals-Methode?


Edit: was miac mit den Indizes meint.

Stell dir eine liste mit zwei Elementen vor:
17 -> 23 . An Pos 0 steht also 17, an Pos 1 steht 23.

Wenn du jetzt naiv per for-schleife
for(int i = 0; i < list.size(); i++) list.remove(i);

ausführst, wird deine liste immernoch ein Element haben. Denn:
0.te iteration : 17 wird gelöscht => 23 rückt auf pos 0 vor.
1.te iteration : abbruch, da 1 >= list.size()

 

[Slight]

Nein die equals Methode wird nicht überschrieben.
Ich habe gerade bemerkt, dass wenn ich das break hinzufügen, fast alles richtig läuft, auch die Kanten werden zuerst alle entfernt, bevor ein weiterer Knoten entfernt wird, was ja vorher nicht so war.
Das Problem ist jetzt, dass zwei Knoten auf einmal in einem Schritt der SortedList hinzugefügt werden, es soll aber nur je ein Knoten hinzugefügt werden, der mit dem kleinsten Index. Dann würde alles passen.

 

[striker159]

poste doch mal den vollständigen code.

ist sortedNodes eine normale java list? in dem falle musst du doch deine equals methode überschreiben, um die knoten in der liste vergleichen zu können, da list.contains() equals aufruft.

 

[Slight]

SortedNodes ist eine LinkedList<Node>, die Objekte vom Typ Node beinhaltet.

Ergänzung (13. Dezember 2015)

Das ist mein Code:

package TopoSort;

import java.util.LinkedList;
import java.util.List;

public class TopologicSort 
{
	//Eingangsgrad berechnen
	public void indegree(Graph G)
	{
		for (int x=0; x<G.getNodes().size(); x++){
		G.getNodes().get(x).indegree=0;
		}
		for (int i=0; i<=G.getNodes().size()-1; i++)
		{
			for (int j=0; j<=G.getEdges().size()-1; j++) 
			{
				if(G.getEdges().get(j).getSecondNode()==(G.getNodes().get(i)))
				{
					G.getNodes().get(i).indegree++;
				} 
			}
		}
		
	}
	
	public void sort(Graph G) 
	{
		indegree(G);
		List<Node> sortedNodes = new LinkedList<Node>();

		while(!(G.getNodes().isEmpty()))
		{	
			for (int i=0; i<G.getNodes().size(); i++)
			{
				if(G.getNodes().get(i).indegree==0)
				{
					sortedNodes.add(G.getNodes().get(i));
					G.removeNode(G.getNodes().get(i));
					break;
				}
				for (int j=0; j<G.getEdges().size(); j++) 
				{
					if(sortedNodes.contains(G.getEdges().get(j).getSecondNode()) ||sortedNodes.contains(G.getEdges().get(j).getFirstNode()))
					{
						G.removeEdge(G.getEdges().get(j));
					}
					indegree(G);
				}

				System.out.println("Sorted Nodes:"+sortedNodes+"\n"+ "Edges:"+G.getEdges()+"\n"+ "Nodes:"+G.getNodes()+"\n");
			}
		}
		System.out.println("Sorted Nodes:"+sortedNodes);
	}
}

public class Graph {
	private List<Node> nodes;
	private List<Edge> edges;
	
	public Graph(List<Node> nodes, List<Edge> edges) 
	{
		this.nodes = nodes;
		this.edges = edges;
	}
	
	public List<Node> getNodes() 
	{
		return nodes;
	}
	
	public List<Edge> getEdges() 
	{
		return edges;
	}
	
	public void addEdge(Edge edge) 
	{
		edges.add(edge);
	}
	
	public void removeEdge(Edge edge) 
	{
		edges.remove(edge);
	}
	
	public void addNode(Node node) 
	{
		nodes.add(node);
	}	
	
	public void removeNode(Node node) 
	{
		nodes.remove(node);
	}
	public static void main (String [] args) {
		Node one = new Node(1);
		Node two = new Node(2);
		Node three = new Node(3);
		Node four = new Node(4);
		Node five = new Node(5);
		Node six = new Node(6);
		Node seven = new Node(7);
		Node eight = new Node(8);
		Node nine = new Node(9);
		
		Edge e1 = new Edge(one, two);
		Edge e2= new Edge(one, three);
		Edge e3 = new Edge(seven, six);
		//Edge e4 = new Edge(nine, eight);
		Edge e5= new Edge(seven, eight);
		Edge e6 = new Edge(seven, four);
		Edge e7 = new Edge(five, four);
		Edge e8= new Edge(five, one);
		Edge e9 = new Edge(six, eight);
		Edge e10 = new Edge(six, two);
		//Edge e11 = new Edge(eight, two);
		Edge e12= new Edge(five, six);
		Edge e13= new Edge(two, nine);
	
		
		List<Node> list1N = new LinkedList<Node>();
		list1N.add(one);
		list1N.add(six);
		list1N.add(four);
		list1N.add(two);
		list1N.add(five);
		list1N.add(nine);
		list1N.add(seven);
		list1N.add(three);
		list1N.add(eight);
		
		
		
		List<Edge> list1E= new LinkedList<Edge>();
		list1E.add(e1);
		list1E.add(e2);
		list1E.add(e3);
		//list1E.add(e4);
		list1E.add(e5);
		list1E.add(e6);
		list1E.add(e7);
		list1E.add(e8);
		list1E.add(e9);
		list1E.add(e10);
		//list1E.add(e11);
		list1E.add(e12);
		list1E.add(e13);
		
		Graph G1 = new Graph(list1N, list1E);
		System.out.println("Nodes:"+G1.getNodes());
		System.out.println("Edges:"+G1.getEdges());
		
		TopologicSort t = new TopologicSort();
		t.indegree(G1);
		for (int i=0; i<G1.getNodes().size();i++){		System.out.println("Eingangsgrad von"+G1.getNodes().get(i)+":"+G1.getNodes().get(i).indegree++);}
		
		t.sort(G1);

		
		
		
		
	}
	
}

public class Node {
	private Object obj;				
	public int indegree;
	
	public Node(Object obj) {
		this.obj = obj;
	}
	
	public Object getObject() 
	{
		return obj;
	}
	
	public String toString() 
	{
		return ""+obj;
	}

}

public class Edge {
	private Node firstNode;
	private Node secondNode;
	
	public Edge(Node firstNode, Node secondNode) 
	{
		this.firstNode = firstNode;
		this.secondNode = secondNode;
	}
	
	Node getFirstNode() 
	{
		return firstNode;
	}
	
	Node getSecondNode() 
	{
		return secondNode;
	}
	
	
	public Node[] getNodes()
	{
		Node[]  n=new Node[2];
		n[0]=firstNode;
		n[1]=secondNode;
		return n;
	}
	
	public String toString()
	{
		return firstNode+"-"+secondNode;	
	}
	
}

 

[Killkrog]

Ich habe mal ausprobiert, wie ich das implementieren würde. Eventuell hilft dir das weiter.
Falls etwas unklar ist, einfach fragen!

Example.java (Einstiegspunkt)

Spoiler

import java.util.ArrayList;

public class Example {

    // ===================================================================
    // {[> Initializers and Constructors
    // =================================
    public Example() {

        ArrayList<Node> nodes = new ArrayList<>();

        // create 9 nodes
        for (int i = 0; i < 9; i++) {
            nodes.add(new Node("Node #" + (i + 1)));
        }

        // define edges between nodes
        nodes.get(1 - 1).addEdgeTo(nodes.get(2 - 1)); // 1 -> 2
        nodes.get(1 - 1).addEdgeTo(nodes.get(3 - 1)); // 1 -> 3
        nodes.get(7 - 1).addEdgeTo(nodes.get(6 - 1)); // 7 -> 6
        nodes.get(7 - 1).addEdgeTo(nodes.get(8 - 1)); // 7 -> 8
        nodes.get(7 - 1).addEdgeTo(nodes.get(4 - 1)); // 7 -> 4
        nodes.get(5 - 1).addEdgeTo(nodes.get(4 - 1)); // 5 -> 4
        nodes.get(5 - 1).addEdgeTo(nodes.get(1 - 1)); // 5 -> 1
        nodes.get(6 - 1).addEdgeTo(nodes.get(8 - 1)); // 6 -> 8
        nodes.get(6 - 1).addEdgeTo(nodes.get(2 - 1)); // 6 -> 2
        nodes.get(5 - 1).addEdgeTo(nodes.get(6 - 1)); // 5 -> 6
        nodes.get(2 - 1).addEdgeTo(nodes.get(9 - 1)); // 2 -> 9

        // sort the nodes
        TopologicalSort.sort(nodes);

        // print the results
        for (Node n : nodes) {
            System.out.println(n);
        }
    }



    // ===================================================================
    // {[> Public Static Methods
    // =========================
    public static void main(String[] args) {
        new Example();
    }
}

Node.java

Spoiler

import java.util.ArrayList;

public class Node implements Comparable<Node>{

    // ===================================================================
    // {[> Attributes
    // ==============
    private ArrayList<Node> out = new ArrayList<>();
    private ArrayList<Node> in = new ArrayList<>();
    private String identifier;
    private int outDegree;
    private int inDegree;



    // ===================================================================
    // {[> Initializers and Constructors
    // =================================
    public Node(String identifier) {
        this.identifier = identifier;
    }



    // ===================================================================
    // {[> Private Methods
    // ===================
    private void addEdgeFrom(Node oNode) {
        if (!in.contains(oNode)) {
            inDegree++;
            in.add(oNode);
        }
    }



    // ===================================================================
    // {[> Public Methods
    // ==================
    public void addEdgeTo(Node oNode) {
        if (!out.contains(oNode)) {
            outDegree++;
            out.add(oNode);
            oNode.addEdgeFrom(this);
        }
    }
    
    public int compareTo(Node o) {
        return identifier.compareTo(o.identifier);
    };
    
    public boolean equals(Object obj) {
        return (obj instanceof Node) && identifier.equals(((Node)obj).identifier);
    }
    
    public ArrayList<Node> getIncomingEdges() {
        return in;
    }
    
    public int getInDegree() {
        return inDegree;
    }
    
    public int getOutDegree() {
        return outDegree;
    }
    
    public String toString() {
        return identifier;
    }
}

TopologicalSort.java

Spoiler

import java.util.ArrayList;
import java.util.Collections;

public class TopologicalSort {

    public static final void sort(ArrayList<Node> nodes) {
        sort(nodes, false);
    }

    public static final void sort(ArrayList<Node> nodes, boolean initialSortNeeded) {

        // check arguments before proceeding
        if (nodes == null) {
            throw new IllegalArgumentException("list is null!");
        }

        if (nodes.isEmpty()) {
            throw new IllegalArgumentException("empty list!");
        }

        if (nodes.size() == 1) {
            return;
        }



        // if required, sort the nodes by natural order
        if (initialSortNeeded) {
            Collections.sort(nodes);
        }



        // this list will contain the eventually sorted nodes
        ArrayList<Node> sortedList = new ArrayList<>();



        // grab the node with the smallest index that has
        // an indegree of zero and put it into the sorted list
        int tmp;
        int minIndex = 0;
        int minDegree = nodes.get(0).getInDegree();
        for (int i = 1; i < nodes.size(); i++) {
            tmp = nodes.get(i).getInDegree();
            if (tmp < minDegree) {
                minIndex = i;
                minDegree = tmp;
            }
        }
        sortedList.add(nodes.remove(minIndex));



        // define some variables that will be used a lot in loops
        boolean valid, changeOccured;
        Node n;



        // process the remaining nodes
        while (!nodes.isEmpty()) {

            // track if the sorted list changed in the current iteration
            // that is important in order to identify circular dependencies!
            changeOccured = false;

            for (int i = 0; i < nodes.size(); i++) {

                n = nodes.get(i);

                // a node is valid for being put into the sorted list
                // if it has an indegree of zero...
                if (n.getInDegree() == 0) {
                    sortedList.add(nodes.remove(i));
                    changeOccured = true;
                    break;
                }

                // ... or if all its incoming edges are present in the already
                // sorted list of nodes
                valid = true;
                for (Node e : n.getIncomingEdges()) {
                    if (!sortedList.contains(e)) {
                        valid = false;
                        break;
                    }
                }

                if (valid) {
                    sortedList.add(nodes.remove(i));
                    changeOccured = true;
                    break;
                }
            }

            if (!changeOccured) {
                throw new RuntimeException("Circular dependency found, unable to sort!");
            }
        }

        nodes.addAll(sortedList);
        sortedList.clear(); // helping the garbage collector
    }
}

 

[Slight]

Dankeschön für die Antwort und das du dir so viel Mühe machst
Ich verstehe nur noch nicht ganz wofür das valid und changeOccured bewirkt und frag mich wo die Kanten entfernt werden.
Aber mir hat es auch sehr geholfen, es ist echt viel einfacher die Knoten selbst nochmal in eine variable zu speichern, danke

 

[Killkrog]

Ein Knoten darf ja unter anderem nur dann ans Ende der sortierten Liste gesetzt werden, wenn alle seine Ausgangsknoten bereits in der sortierten Liste vorliegen.

Beispiel: Ich darf "Schuhe anziehen" nur dann ans Ende der sortierten Liste setzen, wenn die sortierte Liste bereits "Socken anziehen" beinhaltet.

Um das zu überprüfen, benutze ich 'valid' als eine reine Hilfsvariable.

Ich nehme zuerst 'valid = true' an. Dann iteriere ich über jeden Ausgangsknoten und überprüfe, ob er in der sortierten Liste steht. Falls dies nicht der Fall ist, setze ich 'valid = false', was für mich bedeutet, dass ich den Knoten nicht in die sortierte Liste setzten darf.

Die Variable 'changedOccured' benutze ich, um invalide Eingaben abzufangen.
Stell dir vor wir haben wieder die zwei Aufgaben 'Schuhe anziehen' und 'Socken anziehen'. Logischerweise sollte nur eine Kante von 'Socken anziehen' zu 'Schuhe anziehen' führen. Angenommen der Benutzer unseres Algorithmus macht einen Fehler und definiert zusätzlich eine Kante von 'Schuhe anziehen' zu 'Socken anziehen'. Damit könnten wir diese zwei Knoten niemals sortieren und würden in einer Endlosschleife sitzen.
Damit das nicht passieren kann nehme ich an, dass unser Algorithmus in jedem Durchlauf genau einen Knoten sortieren können muss! Ob das passiert ist speichere ich in 'changeOccured'. Am Ende der while-Schleife überprüfe ich dann, ob diese Variable 'true' ist. Falls nicht bedeutet das, dass wir keinen Knoten sortieren konnten und in eine Endlosschleife kommen würden. Dann kommt die RuntimeException zum Einsatz.

Bezüglich deiner Frage, wo ich Kanten entferne:
Ich habe Kanten nirgends als eigene Objekte sondern ausschließlich innerhalb der Knoten selbst definiert.
Das bedeutet weiterhin, dass sobald ich aus der Liste der zu sortierenden Knoten einen Knoten entferne und in die sortierte Liste lege verschwinden alle Kanten, die zu dem entfernten Knoten führen oder von ihm abgehen.


Hoffe das hilft weiter. Falls nicht, einfach nochmal anhauen.

 

[Slight]

Ihr habt mir echt voll geholfen, jetzt habe ich verstanden was ihr alle mit dem Index meint
Ich habe das Problem nun so gelöst, dass ich j-- gemacht habe nach jedem Durchlauf, so kommt auf jeden Fall das richtige Ergebnis.

		while(!(G.getNodes().isEmpty()))
		{	
			for (int i=0; i<G.getNodes().size(); i++)
			{
				Node n = G.getNodes().get(i);
				
				if(n.indegree==0)
				{
					G.removeNode(n);
					for (int j=0; j<G.getEdges().size(); j++) 
					{
						Edge e=G.getEdges().get(j);
						
						if(e.getSecondNode()==n||e.getFirstNode()==n)
						{
							G.removeEdge(G.getEdges().get(j));
							System.out.println("ich lösche: "+e);
							j--;
						}
					}
					sortedNodes.add(n);
					indegree(G);
					System.out.println("!Sorted Nodes:"+sortedNodes+"\n"+ "Edges:"+G.getEdges()+"\n"+ "Nodes:"+G.getNodes()+"\n");
					for (int i2=0; i2<=G.getNodes().size()-1; i2++){System.out.println("Eingangsgrad von "+G.getNodes().get(i2)+": "+G.getNodes().get(i2).indegree); }

					break;
				}
			}
			
		}
		System.out.println("Sorted Nodes:"+sortedNodes);
	}
}

Danke, danke, danke für eure Mühe!

 

[Killkrog]

Achte auf meinen Kommentar...

    public void sort(Graph G) 
        {
            indegree(G);
            List<Node> sortedNodes = new LinkedList<Node>();
            
            while(!(G.getNodes().isEmpty()))
            {    
                for (int i=0; i<G.getNodes().size(); i++)
                {
                    Node n = G.getNodes().get(i);
                    if(n.indegree==0)
                    {
                        G.removeNode(n);
                        sortedNodes.add(n);
                        
                        System.out.println("!Sorted Nodes:"+sortedNodes+"\n"+ "Edges:"+G.getEdges()+"\n"+ "Nodes:"+G.getNodes()+"\n");
                        for (int i2=0; i2<=G.getNodes().size()-1; i2++){System.out.println("Eingangsgrad von "+G.getNodes().get(i2)+": "+G.getNodes().get(i2).indegree); }
                        break; // <--------------- Hier gehst du aus der Schleife raus, bevor du Kanten entfernst...
                    }
                    
                    
                    for (int j=0; j<G.getEdges().size(); j++) 
                    {
                        Edge e=G.getEdges().get(j);
                        
                        if(e.getSecondNode()==n||e.getFirstNode()==n)        //
                        {
                            G.removeEdge(G.getEdges().get(j));
                        
                        }
                    }
                    indegree(G);
            
                }
                
            }
            System.out.println("Sorted Nodes:"+sortedNodes);
        }

Versuch auch, ein bisschen einheitlicheres Codebild zu erzeugen. Es ist wirklich verdammt schwer für jemanden, der das nicht geschrieben hat, sich da reinzufuchsen.

// edit

Ich würde es wohl so umschreiben, wenn ich an deiner Stelle wäre.

public void sort(Graph G) {
    
    ArrayList<Node> sortedNodes = new ArrayList<Node>();
    Node sortedNode;
        
    while(!G.getNodes().isEmpty()) {
        
        indegree(G);
        
        sortedNode = null;
        
        for (int i=0; i < G.getNodes().size(); i++) {
            if (G.getNodes().get(i).indegree == 0) {
                sortedNode = G.getNodes().remove(i);
                sortedNodes.add(sortedNode);
                break;
            }
        }
        
        if (sortedNode == null) {
            throw new RuntimeException();
        }
            
        for (int j=0; j < G.getEdges().size(); j++) {
            
            Edge e = G.getEdges().get(j);
            
            if (e.getFirstNode() == sortedNode || e.getSecondNode() == sortedNode) {
                G.removeEdge(G.getEdges().get(j));
            }
        }
    }
}