网站模板被抄袭怎么办,wordpress手机验证码,网站建设 搜狐,精品课程网站建设论文之前我们介绍了求最短路径算法#xff0c;现在又讲最小生成树算法#xff0c;这两个算法有什么区别呢#xff1f;
首先要明确#xff0c;最短路径和最小生成树是两个不同的概念。 最短路径是对于一个图的两个结点而言的。在一个图中#xff0c;结点A通过某些结点和边可以…之前我们介绍了求最短路径算法现在又讲最小生成树算法这两个算法有什么区别呢
首先要明确最短路径和最小生成树是两个不同的概念。 最短路径是对于一个图的两个结点而言的。在一个图中结点A通过某些结点和边可以走到结点B这些结点和边组成的从A到B的路径中最短路径就这些路径中权值总和最小的那一条或多条。 最短路径常用算法有Floyd、Dijkstra、SPFA、A*等
最小生成树是对于一个图本身而言的。对于一个有n个结点的无向连通图必然可以去掉某些边,使得最终剩下n-1条边与n个结点共同组成原图的一个生成树而最小生成树就是所有可能的生成树中n-1条边的权值总和最小的那一个或多个。 常用算法有Kruskal、Prim 我们现在在1号位置我们要走遍图中的所有顶点各条路上的数值即为权值求这个过程中的最小权值是多少 Input: 6 9 2 4 11 3 5 13 4 6 3 5 6 4 2 3 6 4 5 7 1 2 1 3 4 9 1 3 2 Output: 19
Kruskal
又称 “加边法” 适用于稀疏图 时间复杂度O(MlogN),但通常边M的数目要比顶点N的数目多很多所以最终时间复杂度为O(MlogM)
import java.util.Scanner;class edge {int u, v, w;edge(int u, int v, int w) {this.u u;this.v v;this.w w;}
}
public class Kruskal {static edge[] e new edge[10];static int n, m;static int[] f new int[7];static int sum 0;static int count 0;static Scanner input new Scanner(System.in);public static void main(String[] args) {n input.nextInt();m input.nextInt();for (int i 1; i m; i) {int a input.nextInt();int b input.nextInt();int c input.nextInt();e[i] new edge(a, b, c);}/*** 按权值排序* */quicksort(e, 1, m);for (int i 1; i n; i) {f[i] i;}kruskal();System.out.println(sum);}private static void kruskal() {/*** 从小到大枚举每一条边* */for (int i 1; i m; i) {/*** 检查一条边的两个顶点是否已经连通即判断是否在同一个集合中* */if (merge(e[i].u, e[i].v)) {count;sum sum e[i].w;}/*** 选到n-1边之后退出循环* */if (count n - 1) {break;}}}public static int partition(edge[] a, int p, int q) {int x a[p].w;int i p;for (int j p1; j q; j) {if (a[j].w x) {i 1;edge temp a[i];a[i] a[j];a[j] temp;}}edge temp a[p];a[p] a[i];a[i] temp;return i;}public static void quicksort(edge[] a,int p, int q) {if (p q) {int r partition(a ,p ,q);quicksort(a, p, r - 1);quicksort(a, r 1, q);}}private static int getf(int v) {if (f[v] v) {return v;} else {/*** 压缩路径每次函数返回时将该位置的编号转成祖宗编号* */f[v] getf(f[v]);return f[v];}}private static boolean merge(int v, int u) {int t1 getf(v);int t2 getf(u);/*** 判断祖先是否相同* */if (t1 ! t2) {/*** 靠左原则* */f[t2] t1;return true;}return false;}
}
prim
又称 “加点法” 适用于稠密图 时间复杂度O(N^2)
import java.util.Scanner;public class prim {static int[][] e new int[7][7];static int[] book new int[7];static int[] dis new int[7];static int count 0;static int sum 0;static int n, m;static int min, mark;static Scanner input new Scanner(System.in);public static void main(String[] args) {n input.nextInt();m input.nextInt();for (int i 1; i n; i) {for (int j 1; j n; j) {if (i j) {e[i][j] 0;} else {e[i][j] 99999999;}}}for (int i 1; i m; i) {int a input.nextInt();int b input.nextInt();int c input.nextInt();e[a][b] c;e[b][a] c;}for (int i 1; i n; i) {dis[i] e[1][i];}book[1] 1;prime();System.out.println(sum);}private static void prime() {count;while (count n) {min 99999999;for (int i 1; i n; i) {if(book[i] 0 dis[i] min) {min dis[i];mark i;}}book[mark] 1;count;sum dis[mark];for (int i 1; i n; i) {if (book[i] 0 dis[i] e[mark][i]) {dis[i] e[mark][i];}}}}
}而如果借助“堆”每次选边的时间复杂度可以变为O(logM)
方法 数组dis用来记录生成树到各个顶点的距离。 数组h是一个最小堆堆里面存储的是顶点的编号。这里不是按照顶点编号的大小创建的而是按照顶点在数组dis中对应的值建立这个最小堆。 **数组po**s用来记录每个顶点的最小堆的位置 下面的左图代表 1号结点到2号点的距离为1 1号结点到3号点的距离为2 1号结点到6号点的距离为max 1号结点到4号点的距离为max 1号结点到5号点的距离为max 下面的右图代表 dis数组存放了左图的信息 h数组存放堆 poa数组存放了顶点对应在堆中的位置
import java.util.Scanner;
public class prim2 {static int[] book new int[7];static int[] dis new int[7];static int[] h new int[7];static int[] pos new int[7];static int[] u new int[19];static int[] v new int[19];static int[] w new int[19];static int[] first new int[7];static int[] next new int[19];static int count 0, size;static int sum 0;static int n, m;static int min, mark, mark2;static Scanner input new Scanner(System.in);public static void main(String[] args) {n input.nextInt();m input.nextInt();for (int i 1; i m; i) {u[i] input.nextInt();v[i] input.nextInt();w[i] input.nextInt();}/*** 无向图需要再将所有边反向存储一次* */for (int i m 1; i 2 * m; i) {u[i] v[i - m];v[i] u[i - m];w[i] w[i - m];}/*** 邻接表* */for (int i 1; i n; i) {first[i] -1;}for (int i 1; i 2 * m; i) {next[i] first[u[i]];first[u[i]] i;}prime();System.out.println(sum);}private static void prime() {book[1] 1;count;dis[1] 0;/*** 初始化dis数组存放1到其他各点的距离* */for (int i 2; i n; i) {dis[i] 99999999;}mark2 first[1];while (mark2 ! -1) {dis[v[mark2]] w[mark2];mark2 next[mark2];}/*** 初始化堆* */size n;for (int i 1; i size; i) {h[i] i;pos[i] i;}for (int i size / 2; i 1; i--) {siftdown(i);}/*** 直接弹出堆顶元素* */pop();while (count n) {mark pop();book[mark] 1;count;sum dis[mark];/*** 扫描mark的所有边以j为中间节点进行松弛* */mark2 first[mark];while (mark2 ! -1) {if (book[v[mark2]] 0 dis[v[mark2]] w[mark2]) {dis[v[mark2]] w[mark2];/*** 对该点在堆中进行向上调整pos[v[k]]是订点v[k]在堆中的位置* */siftup(pos[v[mark2]]);}mark2 next[mark2];}}}private static void siftup(int i) {int flag 0;/*** 堆顶* */if (i 1) {return;}while (i ! 1 flag 0) {/*** 当前节点是否小于父结点* */if (dis[h[i]] dis[h[i/2]]) {swap(i, i/2);} else {flag 1;}/*** 向上调整* */i i/2;}}private static void swap(int x, int y) {int temp h[x];h[x] h[y];h[y] temp;temp pos[h[x]];pos[h[x]] pos[h[y]];pos[h[y]] temp;}private static void siftdown(int i) {int t, flag 0;while (i * 2 size flag 0) {if (dis[h[i]] dis[h[i*2]]) {t i * 2;} else {t i;}if (i * 2 1 size) {if (dis[h[t]] dis[h[i * 2 1]]) {t i * 2 1;}}if (t ! i) {swap(t, i);i t;} else {flag 1;}}}private static int pop() {/*** 记录栈顶元素* */int t h[1];pos[t] 0;/*** 将堆底元素赋到堆顶* */h[1] h[size];pos[h[1]] 1;/*** 栈元素数目减 1* */size--;siftdown(1);return t;}
}
