1. 最小生成树

1.1 Prim算法

算法思路：

  1. 随机选取起点加入最小生成树集
  2. 遍历所有顶点，选择出未在最小生成树集中，且离最小生成树最近的顶点
  3. 将选择的顶点加入最小生成树集，并计算cost
  4. 更新剩下的顶点到最小生成树集的最近距离 ```java

public class PrimAlgorithm { public static void main(String[] args) { //测试看看图是否创建 ok char[] data = new char[]{‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’}; int verxs = data.length; //邻接矩阵的关系使用二维数组表示,10000 这个大数，表示两个点不联通 int[][] weight = new int[][]{ {10000, 5, 7, 10000, 10000, 10000, 2}, {5, 10000, 10000, 9, 10000, 10000, 3}, {7, 10000, 10000, 10000, 8, 10000, 10000}, {10000, 9, 10000, 10000, 10000, 4, 10000}, {10000, 10000, 8, 10000, 10000, 5, 4}, {10000, 10000, 10000, 4, 5, 10000, 6}, {2, 3, 10000, 10000, 4, 6, 10000},}; //创建 MGraph 对象 MGraph graph = new MGraph(verxs); //创建一个 MinTree 对象 MinTree minTree = new MinTree(); minTree.createGraph(graph,verxs,data,weight); //minTree.showGraph(graph); minTree.prim(graph,0); } }

//创建最小生成树 class MinTree {

  1. /**
  2.  *
  3.  * @param graph 图对象
  4.  * @param verxs 图对应的顶点个数
  5.  * @param data  图的各个顶点的值
  6.  * @param weight 图的邻接矩阵
  7.  */
  8. public void createGraph(MGraph graph,int verxs,char[] data,int[][] weight) {
  9.     for(int i = 0;i < verxs;i++) {
  10.         graph.data[i] = data[i];
  11.         for(int j = 0;j < verxs;j++) {
  12.             graph.weight[i][j] = weight[i][j];
  13.         }
  14.     }
  15. }
  17. //显示图的邻接矩阵
  18. public void showGraph(MGraph graph) {
  19.     for (int[] link : graph.weight) {
  20.         System.out.println(Arrays.toString(link));
  21.     }
  22. }
  24. /**
  25.  *
  26.  * @param graph 图对象
  27.  * @param v 从哪个节点开始
  28.  */
  29. public void prim(MGraph graph,int v) {
  30.     boolean[] visited = new boolean[graph.verxs];
  32.     visited[v] = true;
  33.     //记录两个顶点下标
  34.     int h1 = -1;
  35.     int h2 = -1;
  37.     int minWeight = Integer.MAX_VALUE;//每次比较的最小权重
  39.     for(int k = 1;k < graph.verxs;k++) {//因为有 graph.verxs 顶点，普利姆算法结束后，有 graph.verxs-1 边
  40.         for(int i = 0;i < graph.verxs;i++) {
  41.             if(!visited[i]) continue;
  42.             for(int j = 0;j < graph.verxs;j++) {
  43.                 if(!visited[j] && graph.weight[i][j] < minWeight) {
  44.                     minWeight = graph.weight[i][j];
  45.                     h1 = i;
  46.                     h2 = j;
  47.                 }
  48.             }
  49.         }
  50.         //找到一条边是最小
  51.         System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight); //将当前这个结点标记为已经访问
  52.         visited[h2] = true;
  53.         minWeight = Integer.MAX_VALUE;
  54.     }
  55. }
  57.  public void prim1(MGraph graph,int v) {
  58.     boolean[] visited = new boolean[graph.verxs];
  60.     int[] dist = new int[graph.verxs];
  61.     Arrays.fill(dist,Integer.MAX_VALUE);
  62.     int cost = 0;
  63.     List<Character> list = new ArrayList<>();
  64.     for(int i = 0;i < graph.verxs;i++) {
  65.         int t = -1;
  66.         //找到离最小生成树最近的点
  67.         for(int j = 0;j < graph.verxs;j++) {
  68.             if(!visited[j] && (t == -1 || dist[j] < dist[t])) t = j;
  69.         }
  70.         if(i != 0) cost += dist[t];
  71.         visited[t] = true;
  72.         list.add(graph.data[t]);
  73.         System.out.println("最小生成树集合:" + list);
  74.         //更新各个点到最小生成树的最小距离
  75.         for(int j = 0;j < graph.verxs;j++) {
  76.             if(dist[j] > graph.weight[t][j]) dist[j] = graph.weight[t][j];
  77.         }
  78.     }
  79.     System.out.println("代价：" + cost);
  80. }

} class MGraph { int verxs;//节点个数 char[] data;//存放节点的数据 int[][] weight;//存放边，邻接矩阵

  1. public MGraph(int verxs) {
  2.     this.verxs = verxs;
  3.     data = new char[verxs];
  4.     weight = new int[verxs][verxs];
  5. }

}

  1. 时间复杂度：O(n*n)<br />空间复杂度：O(n*n)
  2. <a name="dD5Yv"></a>
  3. ## 1.2 Kruskal算法
  4. 算法思路：该算法的基本思想是从小到大加入边，是一个贪心算法。
  6. 1. 将所有的边从小到大排序
  7. 1. 从小到大选择边，判断边对应的两个顶点是否会构成环，如果构成环，则放弃，继续选择下一条边，否则将这两个顶点加入最小生成树集。
  9. 是否成环的判断：可以利用并查集，如果两个顶点在同一集合里面，则会构成环。
  11. 代码例子是LC 1584
  12. ```java
  13. class UnionSet {
  14.         int[] fa;
  15.         int[] size;
  16.         UnionSet(int n) {
  17.             fa = new int[n];
  18.             size = new int[n];
  19.             for(int i = 0;i < n;i++) {
  20.                 fa[i] = i;
  21.                 size[i] = 1;
  22.             }
  23.         }
  24.         int find(int x) {
  25.             if(fa[x] == x) return x;
  26.             int root = find(fa[x]);
  27.             fa[x] = root;
  28.             return root;
  29.         }
  30.         void merge(int x,int y) {
  31.             int ra = find(x);
  32.             int rb = find(y);
  33.             if(ra == rb) return;
  34.             if(size[ra] < size[rb]) {
  35.                 fa[ra] = rb;
  36.                 size[rb] += size[ra];
  37.             } else {
  38.                 fa[rb] = ra;
  39.                 size[ra] += size[rb];
  40.             }
  41.         }
  42.         boolean isConnect(int x,int y) {
  43.             return find(x) == find(y);
  44.         }
  45.     }
  46.     public int minCostConnectPoints(int[][] points) {
  47.         int n = points.length;
  48.         List<int[]> edge = new ArrayList();
  49.         for(int i = 0;i < n;i++) {
  50.             for(int j = i + 1;j < n;j++) {
  51.                 int w = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
  52.                 edge.add(new int[]{i,j,w});
  53.             }
  54.         }
  55.         Collections.sort(edge,(o1,o2) -> {
  56.             return o1[2] - o2[2];
  57.         });
  58.         int cost = 0;
  59.         UnionSet u = new UnionSet(n);
  60.         for(int i = 0;i < edge.size();i++) {
  61.             int[] g = edge.get(i);
  62.             int t = g[0];
  63.             int v = g[1];
  64.             int w = g[2];
  65.             if(u.isConnect(t,v)) continue;
  66.             cost += w;
  67.             u.merge(t,v);
  68.         }
  69.         return cost;
  70.     }

时间复杂度：O(m log(m) + m α(m) ), 排序带来了m log(m)的时间复杂度，并查集合并带来m α(m)的时间复杂度，m为索引对的数量,近似于n n。
空间复杂度：O(nn)

1.3 小结

Prim算法，该算法以顶点为单元，与图中边数无关，比较适合于稠密图
Kruskal算法，该算法以边为单元，时间主要取决于边数，比较适合于稀疏图

2. 最短路径

2.1 Dijkstra算法

  1.     public static int N = 100000;
  2.     public static void main(String[] args) {
  3.         int[][] matrix=new int[7][7];
  4.         matrix[0]=new int[]{N,    5,    7,    N,    N,    N,  2};
  5.         matrix[1]=new int[]{5,  N,    N,    9,    N,    N,  3};
  6.         matrix[2]=new int[]{7,  N,  N,  N,  8,  N,  N};
  7.         matrix[3]=new int[]{N,  9,  N,  N,  N,  4,  N};
  8.         matrix[4]=new int[]{N,  N,  8,  N,  N,  5,  4};
  9.         matrix[5]=new int[]{N,  N,  N,  4,  5,  N,  6};
  10.         matrix[6]=new int[]{2,  3,  N,  N,  4,  6,  N};
  12.         int source = 0;
  13.         dijstra(matrix, source);
  14.     }
  16.     public static void dijstra(int[][] matrix, int source) {
  17.         //最短路径长度
  18.         int[] shortest = new int[matrix.length];
  19.         //判断该点的最短路径是否求出
  20.         int[] visited = new int[matrix.length];
  21.         //存储输出路径
  22.         String[] path = new String[matrix.length];
  24.         //初始化输出路径
  25.         for (int i = 0; i < matrix.length; i++) {
  26.             path[i] = new String(source + "->" + i);
  27.         }
  28.         Arrays.fill(shortest,N);
  29.         //初始化源节点
  30.         shortest[source] = 0;
  31.         visited[source] = 1;
  33.         for(int i = 0;i < matrix.length;i++) {
  34.             if(i != source) {
  35.                 if(matrix[source][i] != N) {
  36.                     shortest[i] = matrix[source][i];
  37.                 }
  38.             }
  39.         }
  40.         for (int i = 1; i < matrix.length; i++) {
  41.             int min = N;
  42.             int index = -1;
  44.             for (int j = 0; j < matrix.length; j++) {
  45.                 //已经求出最短路径的节点不需要再加入计算并判断加入节点后是否存在更短路径
  46.                 if (visited[j] == 0 && shortest[j] < min) {
  47.                     min = shortest[j];
  48.                     index = j;
  49.                 }
  50.             }
  52.             //更新最短路径
  53.             shortest[index] = min;
  54.             visited[index] = 1;
  56.             //更新从index跳到其它节点的较短路径
  57.             for (int m = 0; m < matrix.length; m++) {
  58.                 if (visited[m] == 0 && shortest[index] + matrix[index][m] < shortest[m]) {
  59.                     shortest[m] = shortest[index] + matrix[index][m];
  60.                     path[m] = path[index] + "->" + m;
  61.                 }
  62.             }
  64.         }
  66.         //打印最短路径
  67.         for (int i = 0; i < matrix.length; i++) {
  68.             if (i != source) {
  69.                 if (shortest[i] == N) {
  70.                     System.out.println(source + "到" + i + "不可达");
  71.                 } else {
  72.                     System.out.println(source + "到" + i + "的最短路径为：" + path[i] + "，最短距离是：" + shortest[i]);
  73.                 }
  74.             }
  75.         }
  76.     }