- 浏览: 604291 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
import java.util.Scanner; 方法一:时间复杂度O(n^3) class Edge { /** * 边的起点 */ char vexa; /** * 边的终点 */ char vexb; /** * 边的权植 */ int weight; Edge(char vexa, char vexb, int weight) { this.vexa = vexa; this.vexb = vexb; this.weight = weight; } } public class MST { int n; int m; Edge[] e ; public MST(int n,int m,Edge[] e){ this.n=n; this.m=m; this.e=e; } /** * w函数 * @param x 起点序号 * @param y 终点序号 * @return 返回起点序号为x,终点序号为y的边的权植。如果没有这条边就返回无穷大 */ private int w(int x, int y) { char from = (char) (x + 97); char to = (char) (y + 97); for (int i = 0; i < m; i++) { if (e[i].vexa == from && e[i].vexb == to) { return e[i].weight; } if (e[i].vexa == to && e[i].vexb == from) { return e[i].weight; } } return Integer.MAX_VALUE; // 用Integer.MAX_VALUE代表无穷大 } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt();//图的顶点数 int m = sc.nextInt(); //图的边数 if (n == 0 && m == 0) break; Edge[] e=new Edge[m]; for (int i = 0; i < m; ++i) { int u = sc.nextInt(); int v = sc.nextInt(); int w = sc.nextInt(); e[i]=new Edge((char)(u+97),(char)(v+97),w); } MST mst=new MST(n,m,e); Edge[] ee =mst.prime(); //存放最小生成树的n-1条边 for (int i = 0; i < n - 1; ++i) { System.out.println(ee[i].vexa + " " + ee[i].vexb + " " + ee[i].weight); } } } public Edge[] prime(){ Edge[] e=new Edge[n];//存放最小生成树的n-1条边 // 表示已经加入最小生成树(mst)的结点, 数组元素从0到n-1分别对应结点a到(char)(n-1+97) // 如果vex_mst[i]=0,表示对应结点没有加入到mst // 如果vex_mst[i]=1,表示对应结点已经加入到mst int[] vex_mst = new int[n]; for (int i = 0; i < n; i++) // 初始化 vex_mst[i] = 0; vex_mst[0] = 1; // 设置初始结点为a // 将n-1条边加入到最小生成树 for (int i = 0; i < n-1; i++) { // 加入一条边。 // 这条边的两个结点一个在mst中,而另一个不在mst中而且具有最小权植 int add_vex = 0; // 选中的结点 int min_weight = Integer.MAX_VALUE; // 最小权植,初始值为Integer.MAX_VALUE Edge adde = new Edge(' ', ' ', 0); for (int j = 0; j < n; j++) if (vex_mst[j] == 1) { // j是mst中的结点 for (int k = 0; k < n; k++) { if (vex_mst[k] == 0 && w(j, k) < min_weight) { add_vex = k; min_weight = w(j, k); adde.vexa = (char) (j + 97); adde.vexb = (char) (k + 97); adde.weight = w(j,k); } } } vex_mst[add_vex] = 1; // 将选择的结点加入mst e[i]=adde; } return e; } }
运行:
C:\aaa>java MST
5 8
0 1 2
1 4 9
4 3 7
3 0 10
0 2 12
2 4 3
1 2 8
2 3 6
a b 2
b c 8
c e 3
c d 6
方法二:时间复杂度O(n^2)
import java.io.BufferedInputStream; import java.util.Scanner; import java.util.Arrays; public class PrimTest{ private int[][] arr;//邻接矩阵 private boolean flag[]; //用来标记节点i是否已加入到MST private int n; //顶点数 private int sum;//最小权值和 static final int maxInt = Integer.MAX_VALUE; public PrimTest(int[][] arr,int n){ this.arr=arr; this.n=n; flag=new boolean[n]; } public static void main(String[] args) { Scanner s = new Scanner(new BufferedInputStream(System.in)); int n = 7; int arr[][] = {{maxInt,28, maxInt,maxInt,maxInt, 10, maxInt}, {28, maxInt,16, maxInt,maxInt, maxInt,14 }, {maxInt,16, maxInt,12, maxInt, maxInt,maxInt}, {maxInt,maxInt,12, maxInt,22, maxInt,18 }, {maxInt,maxInt,maxInt,22, maxInt, 25, 24 }, {10, maxInt,maxInt,maxInt,25, maxInt,maxInt}, {maxInt,14, maxInt,18, 24, maxInt,maxInt}}; System.out.println(new PrimTest(arr,n).prim()); } public int prim(){ sum = 0; flag[0] = true; //选取第一个节点 int mst[]=new int[n];//存储最小权值边的起点 Arrays.fill(mst,0);//最小权值边的起点默认为0 for(int k=1; k<n; k++){ //循环n-1次 int min = maxInt,min_i = 0; for(int i=0; i<n; i++){//选一条权值最小的。 if( !flag[i] && arr[0][i] < min){ min = arr[0][i]; min_i = i; } } flag[min_i] = true; //加入 System.out.print("边"+mst[min_i]+"-"+min_i); for(int i=0; i<n; i++){ //更新 if( !flag[i] && arr[0][i] > arr[min_i][i]){//若同一个未加入点与多个已加入点相连接,取权值较小的。 arr[0][i] = arr[min_i][i]; mst[i] = min_i;//更新最小权值边的起点 } } System.out.println("--"+arr[0][min_i]); sum += arr[0][min_i];//加上权值 } return sum; } }
运行:
边0-5--10
边5-4--25
边4-3--22
边3-2--12
边2-1--16
边1-6--14
99
下载源码:
发表评论
-
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1679POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
图的练习题(有解答)
2012-12-27 22:23 26581. 填空题 ⑴ 设无向图G ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2463//邻接表实现图的广搜和深搜(java模板) impor ... -
邻接矩阵实现图的广搜和深搜(java模板)
2012-12-10 20:37 1922经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 ... -
如何求无向图的最小环
2012-11-13 19:02 2797POJ1734 题意:给定一个N个点的无向图,求一个最小环(各 ... -
深度优先搜索输出有向图中的所有环(JAVA)
2012-11-06 14:22 9626如图:求出有向图的所有环。 import java.uti ... -
三种算法(Floyd、Dijkstra、SPFA)求单源点最短路径。
2012-11-05 13:15 1865题(HDU2544): 在每年的校赛里,所有进入决赛 ... -
Dijkstra算法解HDU1874
2012-11-05 10:15 1364Dijkstra算法是用来解 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1943很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5941Bellman-Ford算法: ... -
Bellman-Ford算法教学PPT
2012-11-03 12:06 1456Dijkstra算法是处理单源最短路径的有效算法,但它 ... -
昆虫的同性恋
2012-11-01 19:21 1399题目大意: 输入一个数t,表示测试组数。然后每组第一行两 ... -
拓扑排序入门练习
2012-11-01 16:51 1582拓扑排序简单来说 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4070一、什么是并查集 ... -
无前趋的顶点优先的拓扑排序方法(JAVA)
2012-10-28 20:20 1883无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输 ... -
Kruskal算法和prim算法求最小生成树学习小结(JAVA)
2012-10-26 14:02 5051prim算法是用来实现图最小生成树的2种常用方法之一,P ... -
图的邻接表存储及遍历(JAVA)
2012-10-10 10:58 5427为图的每个顶点所发出的边建立一个单链表,用一顶点数组存储 ... -
弗洛伊德(Floyd)算法求任意两点间的最短路径
2012-10-01 07:46 6305Floyd-Warshall算法(Floyd-Warsha ... -
单源最短路径( Dijkstra算法)JAVA实现
2012-09-14 14:30 9129单源最短路径问题,即在图中求出给定顶点到其它任一顶 ... -
深度优先搜索与有向无环图的拓扑排序(java实现)
2012-09-11 13:05 5543当每个任务有前后置关系时,需要找到一种满足前后置关系的路 ...
相关推荐
在这个问题中,Prim算法和Kruskal算法是两种常用的方法。 1. Prim算法: Prim算法是一种贪心策略,它从一个起始顶点开始,逐步添加边,每次添加一条与已选择顶点集形成最小权重边的新边。这个过程不断进行,直到...
### 使用Prim算法实现最小生成树 #### 一、最小生成树简介 最小生成树(Minimum Spanning Tree, MST)是指在一个加权的无向图中找到一棵包含所有顶点的生成树,使得所有边的权重之和最小。最小生成树在实际应用中...
标题中的“POJ 1789 最小生成树之prim算法”指的是一个在线编程竞赛题目,来源于普林斯顿开放在线课程(POJ)平台。该题目要求参赛者实现Prim算法,这是一种解决图论问题中寻找最小生成树的经典算法。最小生成树是在...
标题 "POJ 1751 求最小生成树Prim算法(JAVA)" 提到的是一个编程挑战,涉及图论中的经典算法——Prim算法。在计算机科学中,Prim算法是用于寻找加权无向图的最小生成树的一种有效方法。最小生成树是一棵树形结构,...
Prim算法和Kruskal算法是两种常用求解最小生成树的算法。 1. **Prim算法**: Prim算法是从一个顶点开始,逐步扩展生成树,每次添加一条与当前生成树相连且权值最小的边。它以贪心策略为基础,确保每一步都选择...
在这个问题上,Kruskal算法和Prim算法是非常经典的解决方案,它们都是在寻找图的最小生成树。这两种算法虽然目标相同,但其思想和实现过程有所不同。 **Kruskal算法** 是基于**并查集**的数据结构来实现的。算法的...
### Kruskal算法求最小生成树的Java实现 #### 一、Kruskal算法简介 Kruskal算法是一种用于寻找图中的最小生成树(Minimum Spanning Tree, MST)的算法。最小生成树是指在一个加权无向图中,连接所有顶点形成的树,...
Prim算法是一种常用的求解最小生成树的方法,它通过逐步构建最小生成树,每次选择与当前生成树连接的边中权重最小的那一条。 在Java中实现Prim算法,首先需要创建一个表示图的数据结构。在提供的代码中,`...
最小生成树的算法主要有两种经典实现: - **Prim算法**: 从任意一个顶点开始,逐步加入边直到连接所有顶点,每次选择当前未加入树且具有最小权重的边。 - **Kruskal算法**: 首先对所有边按权重排序,然后依次加入边...
在本示例中,我们将探讨如何通过Java实现最小生成树的动态演示,特别是Prim和Dijkstra两种算法。 首先,Prim算法是一种贪心算法,用于寻找加权连通图的最小生成树。它的基本思想是从图中任意一个顶点开始,逐步添加...
最小生成树的算法主要有两种经典方法:Prim算法和Kruskal算法。 1. **Prim算法**: Prim算法是从一个顶点开始,逐步扩展生成树,每次选择与当前生成树连接且权值最小的边。这个过程不断进行,直到所有顶点都被包含...
Prim算法是一种经典的图论算法,用于寻找加权无向图中的最小生成树。最小生成树是连接图中所有顶点的树形子图,其边的权重之和最小。这个算法由Eugene Prim在1930年提出,是解决网络设计、资源分配等实际问题的重要...
这个程序是基于Prim算法和Kruskal算法的Java GUI实现,帮助用户直观地理解这两种算法的工作原理。 1. **Prim算法**: Prim算法是一种贪心算法,它从图中的任意一个顶点开始,逐步添加边,每次添加一条与当前生成树...
在这个问题中,我们将探讨两种常见的算法来找到一个无向加权图的最小生成树:Prim算法和Kruskal算法。同时,我们将讨论“备份边”的概念,它在处理网络故障或恢复时具有重要意义。 首先,让我们了解Prim算法。Prim...
代码可能使用了某种编程语言,如C++、Java或Python,通过数据结构(如邻接矩阵或邻接表)来表示图,然后应用Prim算法找出最小生成树。如果代码使用了优先队列,那么在每轮迭代中,它会找出当前未加入树的顶点中与树...
最小生成树问题在计算机科学中是一个经典的图论问题,主要应用于网络设计、优化问题等领域,如构建通信网络、交通网络等。最小生成树是指在给定的连通加权图中找到一棵包含所有顶点的树,使得树上所有边的权值之和...
在这个ACM习题中,你可能需要实现Prim算法或Kruskal算法来找到最小生成树。Prim算法从一个初始节点开始,逐步添加边,每次添加的边都是当前未加入树的边中与树中节点连接且权重最小的那条。而Kruskal算法则是按边的...
本项目提供的Java实现主要涵盖了两种经典算法:Prim算法和Kruskal算法。 **Prim算法** 是一种贪心算法,其基本思想是从一个起始顶点开始,逐步将顶点加入到已选择的顶点集合中,每次都添加一条与当前集合连接且权值...