图

1.普里姆算法

image.png

public class Graph {
    public int vertexSize;//顶点数量
    public int[] vertexs;//顶点数组
    public int[][] matrix;
    public static final int MAX_WEIGHT = 10000;
    private boolean[] isVisited;

    public static void main(String[] args) {
        //初始化数组
        Graph graph = new Graph(9);

        int[] a0 = {0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT};
        int[] a1 = {10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12};
        int[] a2 = {MAX_WEIGHT, MAX_WEIGHT, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8};
        int[] a3 = {MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, MAX_WEIGHT, 16, 21};
        int[] a4 = {MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT};
        int[] a5 = {11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT};
        int[] a6 = {MAX_WEIGHT, 16, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT};
        int[] a7 = {MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT};
        int[] a8 = {MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0};

        graph.matrix[0] = a0;
        graph.matrix[1] = a1;
        graph.matrix[2] = a2;
        graph.matrix[3] = a3;
        graph.matrix[4] = a4;
        graph.matrix[5] = a5;
        graph.matrix[6] = a6;
        graph.matrix[7] = a7;
        graph.matrix[8] = a8;

//        int degree = graph.getOutDegree(4);
//        System.out.println(degree);
//        int exitDegree = graph.getExitDegree(2);
//        System.out.println(exitDegree);
//        int weight = graph.getWeight(0, 4);
//        System.out.println(weight);
//        graph.depthFirstSearch();
//        graph.broadFirstSearch();
        graph.prim();

    }
    /**
     * 创建数组，为最短路径最准备
     */
    public void createGraph(){
        int [] a1 = new int[]{0,1,5,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
        int [] a2 = new int[]{1,0,3,7,5,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
        int [] a3 = new int[]{5,3,0,MAX_WEIGHT,1,7,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
        int [] a4 = new int[]{MAX_WEIGHT,7,MAX_WEIGHT,0,2,MAX_WEIGHT,3,MAX_WEIGHT,MAX_WEIGHT};
        int [] a5 = new int[]{MAX_WEIGHT,5,1,2,0,3,6,9,MAX_WEIGHT};
        int [] a6 = new int[]{MAX_WEIGHT,MAX_WEIGHT,7,MAX_WEIGHT,3,0,MAX_WEIGHT,5,MAX_WEIGHT};
        int [] a7 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,3,6,MAX_WEIGHT,0,2,7};
        int [] a8 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,9,5,2,0,4};
        int [] a9 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,7,4,0};

        matrix[0] = a1;
        matrix[1] = a2;
        matrix[2] = a3;
        matrix[3] = a4;
        matrix[4] = a5;
        matrix[5] = a6;
        matrix[6] = a7;
        matrix[7] = a8;
        matrix[8] = a9;
    }

    /**
     * prim 普里姆算法
     */
    public void prim() {
        //最小代价顶点权值的数组,为0表示已经获取最小权值
        int[] lowcost = new int[vertexSize];
        //放顶点权值
        int[] adjvex = new int[vertexSize];
        int min, minId, sum = 0;
        for (int i =1; i < vertexSize; i++) {
            lowcost[i] = matrix[0][i];
        }
        for (int i = 1; i < vertexSize; i++) {
            min = MAX_WEIGHT;
            minId = 0;
            for (int j = 1; j < vertexSize; j++) {
                if (lowcost[j] > 0 && lowcost[j] < min) {
                    min = lowcost[j];
                    minId = j;
                }
            }
            System.out.println( adjvex[minId] + "------" + min);
            sum += min;
            lowcost[minId] = 0;
            for (int j = 1; j < vertexSize; j++) {
                if (lowcost[j] != 0 && matrix[minId][j] < lowcost[j]) {
                    lowcost[j] = matrix[minId][j];
                    adjvex[j] = minId;
                }
            }
        }
        System.out.println(sum);
    }

    /**
     * 获取某个顶点的第一个邻结点
     */
    private int getFirstNeighbor(int index) {
        //遍历这个顶点所在的二维数组一行，当不为0并且不为MAX_WEIGHT时，将j（邻节点）返回，否则返回-1
        for (int j = 0; j < vertexSize; j++) {
            if (matrix[index][j] > 0 && matrix[index][j] < MAX_WEIGHT) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 根据前一个邻节点的下标来取得下一个邻节点
     * v表示要找的顶点
     * index:表示该顶点相对于哪个邻节点去获取的下一个邻节点
     */
    private int getNextNeighbor(int v, int index) {
        //不需要从头开始，从index后一个开始
        for (int j = index + 1; j < vertexSize; j++) {
            if (matrix[v][j] > 0 && matrix[v][j] < MAX_WEIGHT) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 图的深度优先遍历算法
     */
    private void depthFirstSearch(int i) {
        isVisited[i] = true;
        int w = getFirstNeighbor(i);
        while (w != -1) {
            if (!isVisited[w]) {
                System.out.println(w);
                depthFirstSearch(w);
            }
            w = getNextNeighbor(i, w);//第一个相对于w的邻接点
        }

    }

    /**
     * 对外的深度优先遍历
     */
    public void depthFirstSearch() {
        isVisited = new boolean[vertexSize];
        for (int i = 0; i < vertexSize; i++) {
            if (!isVisited[i]) {
                System.out.println(i);
                depthFirstSearch(i);
            }
        }
        isVisited = new boolean[vertexSize];
    }


    /**
     * 广度优先遍历
     */
    private void broadFirstSearch(int i) {
        int u, w;
        LinkedList<Integer> queue = new LinkedList<>();
        System.out.println(i);
        isVisited[i] = true;
        queue.add(i);//第一次把v0加到队列
        while (!queue.isEmpty()) {
            u = (Integer) (queue.removeFirst()).intValue();
            w = getFirstNeighbor(u);
            while (w != -1) {
                if (!isVisited[w]) {
                    System.out.println(w);
                    isVisited[w] = true;
                    queue.add(w);
                }
                w = getNextNeighbor(u, w);
            }
        }

    }

    /**
     * 对外的广度优化遍历
     */
    public void broadFirstSearch() {
        isVisited = new boolean[vertexSize];
        for (int i = 0; i < vertexSize; i++) {
            if (!isVisited[i]) {
                broadFirstSearch(i);
            }
        }

    }


    /**
     * 计算出度
     *
     * @param index
     */
    public int getOutDegree(int index) {
        int degree = 0;
        for (int j = 0; j < matrix[index].length; j++) {
            int weight = matrix[index][j];
            if (weight != 0 && weight < MAX_WEIGHT) {
                degree++;
            }
        }

        return degree;
    }

    /**
     * 计算入度
     *
     * @param index
     */
    public int getExitDegree(int index) {
        int exitDegree = 0;
        for (int j = 0; j < matrix[index].length; j++) {
            int weight = matrix[j][index];
            if (weight != 0 && weight < MAX_WEIGHT) {
                exitDegree++;
            }
        }
        return exitDegree;


    }

    /**
     * 获取两点之间的权值
     */
    public int getWeight(int v1, int v2) {
        int weight = matrix[v1][v2];
        return weight == 0 ? 0 : (weight == MAX_WEIGHT ? -1 : weight);

    }


    public Graph(int vertexSize) {
        this.vertexSize = vertexSize;
        matrix = new int[vertexSize][vertexSize];
        vertexs = new int[vertexSize];
        for (int i = 0; i < vertexSize; i++) {
            vertexs[i] = i;
        }
        isVisited = new boolean[vertexSize];

    }

    public int getVertexSize() {
        return vertexSize;
    }

    public void setVertexSize(int vertexSize) {
        this.vertexSize = vertexSize;
    }

    public int[][] getMatrix() {
        return matrix;
    }

    public void setMatrix(int[][] matrix) {
        this.matrix = matrix;
    }

    public int[] getVertexs() {
        return vertexs;
    }

    public void setVertexs(int[] vertexs) {
        this.vertexs = vertexs;
    }
}

2.克鲁斯卡尔算法

image.png

public class GraphKruskal {

    private Edge[] edges;
    private int edgeSize;


    public static void main(String[] args) {
        GraphKruskal graphKruskal = new GraphKruskal(15);
        graphKruskal.createEdgeArray();
        graphKruskal.miniSpanTreeKruskal();

    }

    public GraphKruskal(int edgeSize) {
        this.edgeSize = edgeSize;
        edges = new Edge[edgeSize];

    }

    /**
     * 根据克鲁斯卡尔表创建数组
     */
    public void createEdgeArray() {
        Edge edge0 = new Edge(4, 7, 7);
        Edge edge1 = new Edge(2, 8, 8);
        Edge edge2 = new Edge(0, 1, 10);
        Edge edge3 = new Edge(0, 5, 11);
        Edge edge4 = new Edge(1, 8, 12);
        Edge edge5 = new Edge(3, 7, 16);
        Edge edge6 = new Edge(1, 6, 16);
        Edge edge7 = new Edge(5, 6, 17);
        Edge edge8 = new Edge(1, 2, 18);
        Edge edge9 = new Edge(6, 7, 19);
        Edge edge10 = new Edge(3, 4, 20);
        Edge edge11 = new Edge(3, 8, 21);
        Edge edge12 = new Edge(2, 3, 22);
        Edge edge13 = new Edge(3, 6, 24);
        Edge edge14 = new Edge(4, 5, 26);
        edges[0] = edge0;
        edges[1] = edge1;
        edges[2] = edge2;
        edges[3] = edge3;
        edges[4] = edge4;
        edges[5] = edge5;
        edges[6] = edge6;
        edges[7] = edge7;
        edges[8] = edge8;
        edges[9] = edge9;
        edges[10] = edge10;
        edges[11] = edge11;
        edges[12] = edge12;
        edges[13] = edge13;
        edges[14] = edge14;
    }

    public void miniSpanTreeKruskal() {
        int n, m, sum = 0;
        int[] parent = new int[edgeSize];
        //开始所以的数据都是0
        for (int i = 0; i < edgeSize; i++) {
            parent[i] = 0;
        }
        for (int i = 0; i < edgeSize; i++) {
            n = find(parent, edges[i].begin);//找到开始点
            m = find(parent, edges[i].end);//找到结束点
            //如果两个点不想等，就添加到数据里
            if (n != m) {
                parent[n] = m;
                sum += edges[i].weight;
            }
        }
        System.out.println(sum);
    }

    private int find(int[] parent, int i) {
        while (parent[i] > 0) {
            i = parent[i];
        }
        return i;
    }

    class Edge {
        private int begin;
        private int end;
        private int weight;

        public Edge(int begin, int end, int weight) {
            this.begin = begin;
            this.end = end;
            this.weight = weight;
        }

        public int getBegin() {
            return begin;
        }

        public void setBegin(int begin) {
            this.begin = begin;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }
}

3.最短路径

image.png

public class DnjavaDijstra {
    private static final int MAXVER = 9;//最大的顶点
    private static final int MAXWEIGHT = 10000;//记录无穷大
    private int shortTablePath[] = new int[MAXVER];//记录v0到某个顶点的最短路径和

    public static void main(String[] args) {
        Graph graph = new Graph(MAXVER);
        graph.createGraph();
        DnjavaDijstra dn = new DnjavaDijstra();
        dn.getShortPath(graph);
    }

    /**
     * 获取一个图的最短路径
     */
    public void getShortPath(Graph graph) {
        int min;//最小值
        int k = 0;//下标
        boolean[] isgetPath = new boolean[MAXVER];//记录是否获取最短路径
        //初始化这个数组的各组值
        for (int v = 0; v < graph.getVertexSize(); v++) {
            shortTablePath[v] = graph.matrix[0][v];
        }

        shortTablePath[0] = 0;
        isgetPath[0] = true;
        for (int v = 1; v < graph.getVertexSize(); v++) {
            min = MAXWEIGHT;
            //对v行的每横组遍历获取最小值
            for (int w = 0; w < graph.getVertexSize(); w++) {
                if (!isgetPath[w] && shortTablePath[w] < min) {
                    k = w;
                    min = shortTablePath[w];
                }
            }

            isgetPath[k] = true;

            //通过获取的最小值，然后在遍历最小值那一行的所以元素和最小值的和数与shortTablePath数组内对应的数比较
            //如果大则不管，如果下，则要替换
            for (int j = 0; j < graph.getVertexSize(); j++) {
                if (!isgetPath[j] && min + graph.matrix[k][j] < shortTablePath[j]) {
                    shortTablePath[j] = min + graph.matrix[k][j];
                }
            }
        }

        for (int i = 0; i < shortTablePath.length; i++) {
            System.out.println(i + "------" + shortTablePath[i]);
        }


    }
}

4.拓扑排序

image.png image.png

public class DnGraphTopologic {

    private VertexNode[] adjList;
    private int numVertexes;

    public static void main(String[] args) {
        DnGraphTopologic dnGraphTopologic = new DnGraphTopologic(14);
        dnGraphTopologic.create();
        try {
            dnGraphTopologic.topologicalSort();
        } catch (Exception e) {
            e.printStackTrace();
        }

    }

    public DnGraphTopologic(int numVertexes) {
        this.numVertexes = numVertexes;
    }

    /**
     * 拓扑排序
     */
    public void topologicalSort() throws Exception {
        Stack<Integer> stack = new Stack<>();
        int count = 0;
        int k = 0;
        for (int i = 0; i < numVertexes; i++) {
            //遍历adjList集合中所有元素的入度，入度为0，就放入栈中
            if (adjList[i].in == 0) {
                stack.push(i);
            }
        }

        while (!stack.isEmpty()) {
            //取出入度为0的元素的下标
            int pop = stack.pop();
            System.out.println(adjList[pop].data);//输出这个data
            count++;
            //循环取出的入度为0的元素的第一个邻数，并且node不断的获取他的下一个元素
            for (EdgeNode node = adjList[pop].firstEdge; node != null; node = node.next) {
                //获取下标
                k = node.adjvex;//下标
                //当下标减少为0时，放入栈中
                if (--adjList[k].in == 0) {
                    stack.push(k);
                }

            }
        }

        if (count < numVertexes) {
            throw new Exception("完犊子了，拓扑排序失败");
        }
    }

    private void create() {
        VertexNode node0 = new VertexNode(0, "v0");
        VertexNode node1 = new VertexNode(0, "v1");
        VertexNode node2 = new VertexNode(2, "v2");
        VertexNode node3 = new VertexNode(0, "v3");
        VertexNode node4 = new VertexNode(2, "v4");
        VertexNode node5 = new VertexNode(3, "v5");
        VertexNode node6 = new VertexNode(1, "v6");
        VertexNode node7 = new VertexNode(2, "v7");
        VertexNode node8 = new VertexNode(2, "v8");
        VertexNode node9 = new VertexNode(1, "v9");
        VertexNode node10 = new VertexNode(1, "v10");
        VertexNode node11 = new VertexNode(2, "v11");
        VertexNode node12 = new VertexNode(1, "v12");
        VertexNode node13 = new VertexNode(2, "v13");
        adjList = new VertexNode[numVertexes];
        adjList[0] = node0;
        adjList[1] = node1;
        adjList[2] = node2;
        adjList[3] = node3;
        adjList[4] = node4;
        adjList[5] = node5;
        adjList[6] = node6;
        adjList[7] = node7;
        adjList[8] = node8;
        adjList[9] = node9;
        adjList[10] = node10;
        adjList[11] = node11;
        adjList[12] = node12;
        adjList[13] = node13;
        node0.firstEdge = new EdgeNode(11);
        node0.firstEdge.next = new EdgeNode(5);
        node0.firstEdge.next.next = new EdgeNode(4);
        node1.firstEdge = new EdgeNode(8);
        node1.firstEdge.next = new EdgeNode(4);
        node1.firstEdge.next.next = new EdgeNode(2);
        node2.firstEdge = new EdgeNode(9);
        node2.firstEdge.next = new EdgeNode(6);
        node2.firstEdge.next.next = new EdgeNode(5);
        node3.firstEdge = new EdgeNode(13);
        node3.firstEdge.next = new EdgeNode(2);
        node4.firstEdge = new EdgeNode(7);
        node5.firstEdge = new EdgeNode(12);
        node5.firstEdge.next = new EdgeNode(8);
        node6.firstEdge = new EdgeNode(5);
        node8.firstEdge = new EdgeNode(7);
        node9.firstEdge = new EdgeNode(11);
        node9.firstEdge.next = new EdgeNode(10);
        node10.firstEdge = new EdgeNode(13);
        node12.firstEdge = new EdgeNode(9);
    }

    //边表顶点
    class EdgeNode {

        private int adjvex;
        private EdgeNode next;
        private int weight;

        public EdgeNode(int adjvex) {
            this.adjvex = adjvex;
        }

        public int getAdjvex() {
            return adjvex;
        }

        public void setAdjvex(int adjvex) {
            this.adjvex = adjvex;
        }

        public EdgeNode getNext() {
            return next;
        }

        public void setNext(EdgeNode next) {
            this.next = next;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }

    //邻接顶点
    class VertexNode {
        private int in;//入度
        private String data;
        private EdgeNode firstEdge;

        public VertexNode(int in, String data) {
            this.in = in;
            this.data = data;
        }

        public int getIn() {
            return in;
        }

        public void setIn(int in) {
            this.in = in;
        }

        public String getData() {
            return data;
        }

        public void setData(String data) {
            this.data = data;
        }

        public EdgeNode getFirstEdge() {
            return firstEdge;
        }

        public void setFirstEdge(EdgeNode firstEdge) {
            this.firstEdge = firstEdge;
        }
    }
}