Beiträge

Beginner   Java allgemein   JDBC   JNI   Networking   Online-Ressourcen   Swing + AWT   XML   Meckerecke    Antworten     Neuer Beitrag     Gesamtdarstellung Detaildarstellung Einzeldarstellung Threaddarstellung

Beitrag 540 von 2212 (24%)

Autor	Rok
Datum	22.06.04, 15:31
Betreff	Komplexität TopologicSort

---

Hi

Kann mir jemand etwas über die Komplexität des TopologicSort sagen?


public class GraphAlgorithms {
    
    // Topologisches Sortieren
    // @return List of vertix-indices
    
    
    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)
            q.enqueue(new Integer(j));
        }
        while (!q.isEmpty()) {
            int u = ((Integer) (q.dequeue())).intValue();
            result[i - 1] = u;
            i++;
            for (int w = 0; w < g.size(); w++) {
                if (g.hasEdge(u, w)) {
                    inCount[w]--;
                    if (inCount[w] == 0)
                    q.enqueue(new Integer(w));
                }
            }
        }
        return result;
    }
    
}




// Graph dargestellt durch adjacent matrix.

public class Graph {
    
    private int[][] graph;
    
    
    // Neuen Graph erzeugen
    // @param size Number of Vertices
    
    public Graph(int size) {
        graph = new int[size][size];
    }
    
    /**
    * Add a directed edge to the graph.
    *
    * @param from
    * @param to
    */
    public void addEdge(int from, int to) {
        graph[from][to] = 1;
    }
    
    /**
    * Count edges that ends in vertex i.
    *
    * @param i index of vertex
    * @return number of edges
    */
    public int edgesIn(int i) {
        int sum = 0;
        for (int j = 0; j < graph.length; j++)
        sum += graph[j][i];
        return sum;
    }
    
    /**
    * Ask, if a directed edge exists.
    *
    * @param from start vertex
    * @param to destination vertex
    * @return boolean value
    */
    
    public boolean hasEdge(int from, int to) {
        return graph[from][to] != 0;
    }
    
    // Größe des Graphen (d.h. number of vertices).
    // @return size
    
    public int size() {
        return graph.length;
    }
    
}

---

Auf diesen Beitrag antworten   Neuen Beitrag verfassen