图

• 图的特点：
  1.通常用V(Vertex)表示一组定点的集合；
  2.通常用E(Edge)表示一组边的集合。
• 顶点：
  图中的一个结点
• 图的边：
  顶点和顶点间的连线，有向图中的边叫做弧
• 相邻顶点：
  由一条边连接在一起的顶点
• 顶点的度：
  相邻顶点的数量叫做顶点的度
• 连通图：
  在无向图中，若任意两个顶点Vi与Vj都有路径相通，则称该无向图为连通图
• 强连通图：
  在有向图中，若任意两个顶点Vi与Vj都有路径相通，则称该有向图为强连通图
• 连通网：
  在连通图中，若图的边具有一定的意义，每一条边都有一个对应数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网
• 生成树：
  一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则会形成环

• 图的深度优先遍历：
  假设初始状态是图中所有顶点都未被访问，从图中某个顶点v出发，先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时还有剩余顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

• 图的广度优先遍历：
  假设从图中某个顶点v出发，在访问了顶点v之后依次访问顶点v的各个未曾访问过的邻接顶点，然后分别从这些邻接顶点再出发依次访问它们的邻接顶点，并使“先被访问的顶点的邻接顶点”先于“后被访问的顶点的邻接顶点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到；若此时图中还有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

• 最小生成树：
  在连通网的所有生成树中，所有边的代价总和最小的生成树，称为最小生成树

1.普里姆算法(Prim算法)：

描述：
1.定义一个加权连通图，其中顶点集合V、Vnew，Vnew是V的子集，边的集合E、Enew，Enew是E的子集；
2.初始化集合Vnew{x},x(起始点)是集合V中任意一结点，Enew{}；
3.从边的集合E中选取权值最小的边<u, v>(其中u是顶点集合Vnew的元素，v属于顶点集合V，而不在新顶点集合Vnew中。若权值相同时，任意取值)；
4.将v加入新顶点集合Vnew，将边<u, v>加入新边集合Enew中；
5.重复操作3和4步骤 ，知道Vnew=V时，输出集合Vnew和Enew，Vnew和Enew即是来描述该加权连通图的最小生成树。
代码实现：

 static class GraphMatrix {
        /**
         * 边的数量
         */
        private int edgeNum;
        /**
         * 顶点集合
         */
        private char[] vertex;
        /**
         * 邻接矩阵
         */
        private int[][] matrix;

        public GraphMatrix(char[] vertex, int[][] matrix) {
            this.vertex = vertex;
            this.matrix = matrix;
            getEdgeNum();
        }

        private void getEdgeNum() {
            int length = vertex.length;
            for (int i = 0; i < length; i++) {
                for (int j = i + 1; j < length; j++) {
                    //矩阵值等于Integer.MAX_VALUE表示不相邻，等于0是自己到自己
                    if (matrix[i][j] != Integer.MAX_VALUE) {
                        edgeNum++;
                    }
                }
            }
        }

        /**
         * print matrix
         */
        private void printMatrix() {
            System.out.println("矩阵:");
            for (int[] m : matrix) {
                for (int c : m) {
                    System.out.print(c + " ");
                }
                System.out.println();
            }
        }

        /**
         * 获取字符在结点里的位置
         *
         * @param c 字符
         * @return 返回-1没该字符，其他位置
         */
        private int getVertexPosition(char c) {
            for (int i = 0; i < vertex.length; i++) {
                if (c == vertex[i]) {
                    return i;
                }
            }

            return -1;
        }

        /**
         * 输入开始顶点位置
         *
         * @param x 开始顶点位置
         */
        public void prime(int x) {
            int num = vertex.length;
            //邻边权重
            int[] weights = new int[num];
            //prime最小生成树结果
            char[] result = new char[num];
            //result当前索引
            int index = 0;

            //复制第一个顶点值
            result[index] = vertex[x];
            index++;

            //init weight 找到顶点相邻边的权重赋值weights[i]
            for (int i = 0; i < num; i++) {
                weights[i] = matrix[x][i];
            }
            weights[x] = 0;

            //循环遍历娶到最短权重值添加到result中
            for (int i = 0; i < num; i++) {
                if (x == i) {
                    continue;
                }

                int minWeight = Integer.MAX_VALUE;
                int minWeightIndex = 0;


                for (int j = 0; j < num; j++) {
                    if (weights[j] != 0 && weights[j] < minWeight) {
                        minWeight = weights[j];
                        minWeightIndex = j;
                    }
                }

                //保存最短权重顶点
                result[index] = vertex[minWeightIndex];
                index++;
                weights[minWeightIndex] = 0;

                for (int j = 0; j < num; j++) {
                    if (weights[j] != 0 && matrix[minWeightIndex][j] < weights[j]) {
                        weights[j] = matrix[minWeightIndex][j];
                    }
                }
            }


            //计算最小生成树的权重
            int sum = 0;
            for (int i = 1; i < index; i++) {
                int min = Integer.MAX_VALUE;

                int n = getVertexPosition(result[i]);
                //求当前节点到上面其他节点的最小值
                for (int j = 0; j < i; j++) {
                    int m = getVertexPosition(result[j]);
                    if (matrix[m][n] < min) {
                        min = matrix[m][n];
                    }
                }

                sum += min;
            }

            //打印最小生成树
            System.out.printf("PRIME(%c):", vertex[x]);
            for (int i = 0; i < index; i++) {
                System.out.printf("%c ", result[i]);
            }
            System.out.println();
            System.out.printf("权重：%d", sum);

        }
    }
``` 

2.克鲁斯卡尔算法(Kruskal算法)：

描述：  
首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。  
代码实现：  

``` java
 /**
         * 克鲁斯卡尔算法
         */
        public void Kruskal() {
            //结果数组的当前索引
            int index = 0;
            //输出的结果数组
            Edge[] results = new Edge[edgeNum];
            //保存某个顶点在该最小生成树的终点
            int[] vends = new int[edgeNum];

            //获取图中所有的边
            Edge[] edges = getEdges();

            //将边按权重从小到大排序
            sortEdges(edges);

            for (int i = 0; i < edgeNum; i++) {
                int p1 = getVertexPosition(edges[i].start);
                int p2 = getVertexPosition(edges[i].end);

                int m = getEdgesEnd(vends, p1);
                int n = getEdgesEnd(vends, p2);
                if (m != n) {//表示没有形成闭环
                    vends[m] = n;
                    results[index++] = edges[i];
                }
            }

            //统计并打印最小生成树的信息
            int length = 0;
            for (int i = 0; i < index; i++) {
                length += results[i].weight;
            }

            System.out.println("Kruskal：");

            for (int i = 0; i < index; i++) {
                System.out.printf("(%c,%c) ", results[i].start, results[i].end);
            }
            System.out.println();
            System.out.println("Kruskal的权重：" + length);

        }

        //连通图的边结构
        private static class Edge {
            char start;//边的起点
            char end;//边的终点
            int weight;//边的权重

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

        /**
         * 获取图中的边
         */
        private Edge[] getEdges() {
            int index = 0;
            Edge[] edges = new Edge[edgeNum];
            for (int i = 0; i < vertex.length; i++) {
                for (int j = i + 1; j < vertex.length; j++) {
                    if (matrix[i][j] != Integer.MAX_VALUE) {
                        edges[index++] = new Edge(vertex[i], vertex[j], matrix[i][j]);
                    }
                }
            }
            return edges;
        }

        /**
         * 根据权重从小到大排序
         *
         * @param edges edges
         */
        private void sortEdges(Edge[] edges) {
            Edge tmp;
            for (int i = 0; i < edges.length; i++) {
                for (int j = (i + 1); j < edges.length; j++) {
                    if (edges[i].weight > edges[j].weight) {//若大于则交换位置
                        tmp = edges[i];
                        edges[i] = edges[j];
                        edges[j] = tmp;
                    }
                }
            }
        }

        /**
         * 取终点
         */
        private int getEdgesEnd(int[] vends, int i) {
            //若C->D,D->F则取F的值
            while (vends[i] != 0) {
                i = vends[i];
            }
            return i;
        }

• 最短路径：