kruskals-algorithm-minimum-spanning-tree

[Maouo]

Hat jemand einen einfachen beispiel für ein Programm der mit kruskals-algorithm erstellt ist !?

 

[mihe7]

Ja.

 

[mrBrown]

Hier gibt es ein einfaches Beispiel.

 

[Blender3D]

Hat jemand einen einfachen beispiel für ein Programm der mit kruskals-algorithm erstellt ist !?

import java.util.Arrays;
import java.util.Vector;

public class Graph {
    public static final int NO_EDGE = -1;
    public static final int MAX_NODES = 26;
    public int[][] matrix;
    private boolean found = false;

    public Graph(int nodes) {
        if (nodes < 1 || nodes > MAX_NODES)
            throw new IllegalArgumentException("Maximum allowed nodes are " + MAX_NODES + " and minimum is 1 !");
        matrix = new int[nodes][nodes];
        for (int i = 0; i < nodes; i++)
            for (int ii = 0; ii < nodes; ii++)
                matrix[i][ii] = NO_EDGE;
    }

    public Edge[] getEdges() {
        if (matrix == null)
            return null;
        Vector<Edge> tmp = new Vector<Edge>();
        for (int y = 0; y < size(); y++) {
            String edgeStart = indexToNode(y) + "";
            for (int x = 0; x < size(); x++) {
                if (y < x && matrix[x][y] > NO_EDGE)
                    tmp.add(new Edge(edgeStart + indexToNode(x), matrix[x][y]));
            }
        }
        return tmp.toArray(new Edge[tmp.size()]);
    }

    public int getEdgeValue(String edge) {
        return matrix[nodeToIndex(edge.charAt(0))][nodeToIndex(edge.charAt(1))];
    }

    public int getEdgeValue(char n1, char n2) {
        return matrix[nodeToIndex(n1)][nodeToIndex(n2)];
    }

    public static Graph getMinSpanningGraph(final Graph g) {
        Graph tmp = new Graph(g.size());
        Edge[] edges = g.getEdges();
        Arrays.sort(edges);
        tmp.setEdge(edges[0]);
        for (int i = 1; i < edges.length; i++) {
            tmp.setEdge(edges[i]);
            if (tmp.hasCycle())
                tmp.removeEdge(edges[i]);
        }
        return tmp;
    }

    public boolean hasCycle() {
        boolean visited[] = new boolean[size()];
        boolean finished[] = new boolean[size()];
        found = false;
        for (int i = 0; i < size(); i++) {
            hasCycle(visited, finished, i, -1);
            if (found)
                return true;
        }
        return false;
    }

    private void hasCycle(boolean[] visited, boolean[] finished, int x, int lastX) {
        if (finished[x] || found)
            return;
        if (visited[x]) {
            found = true;
            return;
        }
        visited[x] = true;
        for (int y = 0; y < size(); y++) {
            if (x != y && y != lastX && matrix[x][y] != NO_EDGE)
                hasCycle(visited, finished, y, x);
        }
        finished[x] = true;
        return;
    }

    public static char indexToNode(int i) {
        if (i < 0 || i > 25)
            throw new IllegalArgumentException("Maximum allowed index is " + (MAX_NODES - 1) + " !");
        char c = 'A';
        return (char) (c + i);

    }

    public static boolean isValidNodeName(char node) {
        return !(node < 'A' || node > 'Z');
    }

    public static int nodeToIndex(char node) {
        if (!isValidNodeName(node))
            throw new IllegalArgumentException("only A - Z allowed!");
        return (int) (node - 'A');

    }

    public void removeEdge(String name) {
        setEdge(name, NO_EDGE);

    }

    public void removeEdge(Edge edge) {
        removeEdge(edge.name);
    }

    public void setEdge(Edge edge) {
        setEdge(edge.name, edge.value);
    }

    public void setEdge(String edge, int value) {
        char n1 = edge.charAt(0);
        char n2 = edge.charAt(1);
        setEdge(n1, n2, value);
    }

    public void setEdge(char n1, char n2, int value) {
        int idStart = nodeToIndex(n1);
        int idAim = nodeToIndex(n2);
        matrix[idStart][idAim] = value;
        matrix[idAim][idStart] = value;
    }

    public int size() {
        return matrix.length;
    }

    public String toMatrixString() {
        StringBuffer tmp = new StringBuffer();
        String nl = System.getProperty("line.separator");
        if (matrix == null)
            return "";
        int width = size();
        int height = size();
        if (width == 0)
            return "";
        tmp.append("\t" + indexToNode(0));
        for (char i = 1; i < width; i++)
            tmp.append("\t" + indexToNode(i));
        tmp.append(nl);
        for (int y = 0; y < width; y++) {
            tmp.append(indexToNode(y) + "");
            for (int x = 0; x < height; x++) {
                tmp.append(matrix[x][y] < 0 ? "\t-" : "\t" + matrix[x][y]);
            }
            tmp.append(nl);
        }
        return tmp.toString();
    }

    @Override
    public String toString() {
        Edge[] nodes = getEdges();
        if (nodes == null || nodes.length == 0)
            return "";
        StringBuffer tmp = new StringBuffer(nodes[0].toString());
        for (int i = 1; i < nodes.length; i++) {
            tmp.append(", ");
            tmp.append(nodes[i].toString());
        }
        return tmp.toString();
    }

}

public final class Edge implements Comparable<Edge> {
    public final String name;
    public final int value;
    public final String seperator = "|";

    public Edge(String edge, int value) {
        edge = edge.trim();
        if (value < 0)
            value = Graph.NO_EDGE;
        assertEdgeName(edge);
        this.name = edge;
        this.value = value;
    }

    public static void assertEdgeName(String name) {
        if (name.length() != 2 || !Graph.isValidNodeName(name.charAt(0)) || !Graph.isValidNodeName(name.charAt(1)))
            throw new IllegalArgumentException("Invalid edge name!");
        return;
    }

    @Override
    public int compareTo(Edge o) {
        if (value == o.value)
            return 0;
        return value > o.value ? 1 : -1;
    }

    @Override
    public String toString() {
        return name + seperator + value;
    }

}

public class start {
    public static void main(String[] args) {
        Graph g = new Graph(7);
        g.setEdge("AB", 7);
        g.setEdge("AD", 5);
        g.setEdge("BD", 9);
        g.setEdge("BC", 8);
        g.setEdge("BE", 7);
        g.setEdge("CE", 5);
        g.setEdge("DE", 15);
        g.setEdge("FG", 11);
        g.setEdge("FE", 8);
        g.setEdge("EG", 9);
        g.setEdge("DF", 6);
        System.out.println(g.toMatrixString() + "\n" + g + "\n");
        Graph min = Graph.getMinSpanningGraph(g);
        System.out.println("\nminimum graph\n" + min);
    }
}

 

[Tarrew]

Nach

Kanten und Knoten,
Suche Programmierer für eine Labor Aufgabe und
kruskals-algorithm-minimum-spanning-tree

kommt gleich der vierte Thread "Wie wende ich diesen Code auf mein Beispiel an?" (mit dem Code von Blender3D). Dann hat sich der Kreis endlich geschlossen. Die Strategie ist nicht schlecht.

 

[flopalko]

Nach

Kanten und Knoten,
Suche Programmierer für eine Labor Aufgabe und
kruskals-algorithm-minimum-spanning-tree

kommt gleich der vierte Thread "Wie wende ich diesen Code auf mein Beispiel an?" (mit dem Code von Blender3D). Dann hat sich der Kreis endlich geschlossen. Die Strategie ist nicht schlecht.

Für den minimum spanning tree sollte sich der Kreis aber besser nicht schließen