[java] złe sortowanie w programie sortowania topologicznego

mistrz23 · Post autor: **mistrz23** » 19 cze 2015, o 15:40

Dlaczego w poniższym programie sortowania topologicznego wyświetlany jest zły wynik?

package sortowanietopologiczne;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

class ListaSasiedztwa {
    int n;
    ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
    
    ListaSasiedztwa (int n0) {
        n = n0;
        for (int i = 0; i < n; i++) 
            adj.add(new ArrayList<Integer>());
    } 
    
    void addEdge(int i, int j) {
        adj.get(i).add(j);
    }
    
    void removeEdge(int i, int j) {
        Iterator<Integer> it = adj.get(i).iterator();
        while (it.hasNext()) {
            if (it.next() == j) {
                it.remove();
                return;
            }
        }    
    }
    
    boolean hasEdge(int i, int j) {
        return adj.get(i).contains(j);
    }
    
    List<Integer> outEdges(int i) {
        return adj.get(i);
    }
    
    List<Integer> inEdges(int i) {
        List<Integer> edges = new Stack();
        for (int j = 0; j < n; j++)
            if (adj.get(j).contains(i))    edges.add(j);
        return edges;
    }
    
    ArrayList noSuccessors(int poziom) {
        boolean prawda = false;
        ArrayList<Integer> liczby = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((adj.get(i).size() - poziom) == 0)
                prawda = true;
            if (prawda == true) {
                liczby.add(i);
            }
            prawda = false;
        }
        return liczby;
    }
     
}

public class SortowanieTopologiczne {
    
    static void topo(ListaSasiedztwa listalin) {
        Stack<Integer> pomoc = new Stack();
        ArrayList<Integer> sortowana = new ArrayList<>();
        
        for (int j = 0; j < listalin.n; j++) {
            ArrayList<Integer> rob = listalin.noSuccessors(j);
            for (int i = 0; i < rob.size(); i++) {
                pomoc.push(rob.get(i));
            }
        
            while (!pomoc.isEmpty()) {
                sortowana.add(pomoc.pop());
            }    
        }
        System.out.println(Arrays.toString(sortowana.toArray()));
    }
    
    public static void main(String[] args) {
        ListaSasiedztwa ListaLin = new ListaSasiedztwa(10);
        
        ListaLin.addEdge(1,2);
        ListaLin.addEdge(2,4);
        ListaLin.addEdge(4,6);
        ListaLin.addEdge(2,10);
        ListaLin.addEdge(4,8);
        ListaLin.addEdge(6,3);
        ListaLin.addEdge(1,3);
        ListaLin.addEdge(3,5);
        ListaLin.addEdge(5,8);
        ListaLin.addEdge(4,5);
        ListaLin.addEdge(7,9);
        ListaLin.addEdge(9,4);
        ListaLin.addEdge(9,10);
        System.out.println(Arrays.toString(ListaLin.adj.toArray()));
        
        
        topo(ListaLin);
}
}

wynik programu:

Kod: Zaznacz cały

[[], [2, 3], [4, 10], [5], [6, 8, 5], [8], [3], [9], [], [4, 10]]
[8, 0, 7, 6, 5, 3, 9, 2, 1, 4]

a powinien być:
7, 9, 1, 2, 4, 6, 3, 5, 8, 10?