精华内容
下载资源
问答
  • 具体讲解请参考最小生成树算法,大佬写的非常易懂 参考资料:大话数据结构 以下是java代码实现 创建一个关于图的类 import java.util.Scanner; /** 1. @author Aaron 2. @date 2020/3/29 - 17:48 */ public class ...
  • 最小生成树的Prim算法 java实现 看的其它大佬的代码 在这记录一下 方便复习 ```java public class Main{ public static void PRIM(int[][] graph,int start,int n) { int[][] min = new int[n][2];//保存到子图...

    最小生成树的Prim算法 java实现

    看的其它大佬的代码 在这记录一下 方便复习

    
    ```java
    public class Main{
    
        public static void PRIM(int[][] graph,int start,int n)
        {
            int[][] min = new int[n][2];//保存到子图的最短距离以及前驱节点
            //初始化
            for(int i=0;i<n;i++)
            {
                if(i==start)
                {
                    min[i][0]=-1;
                    min[i][1]=0;         //它到子图的距离
                }
                else if(graph[i][start]!=-1)
                {
                    min[i][0]=start;
                    min[i][1]=graph[i][start];
                }else{
                    min[i][0]=-1;
                    min[i][1]=Integer.MAX_VALUE;
                }
            }
    
            for(int i=0;i<n-1;i++)            //遍历n-1次
            {
                int minval = Integer.MIN_VALUE;
                int minnode = -1;
                for(int j=0;j<n;j++)
                {
                    if(min[j][1]!=0&&min[j][1]<minval)
                    {
                        minval = min[j][1];
                        minnode = j;
                    }
                }
                min[minnode][1]=0;  //将最小节点加入子集
                for(int j=0;j<n;j++)
                {
                    if(min[j][1]!=0&&graph[j][minnode]!=-1&&graph[minnode][j]<min[j][1])
                    {
                        min[j][0]=minnode;
                        min[j][1]=graph[minnode][j];
                    }
                }
            }
    
    
        }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    }
    
    
    
    
    
    
    展开全文
  • /**日期:2010-04-18 11:37*开发者:heroyan*联系方式:zndxysf@126.com*功能:无向图最小生成树Prim算法实现案例*/import java.util.Scanner;import java.util.Arrays;import java.util.ArrayList;public class ...

    /*

    *日期:2010-04-18 11:37

    *开发者:heroyan

    *联系方式:zndxysf@126.com

    *功能:无向图最小生成树Prim算法实现案例

    */

    import java.util.Scanner;

    import java.util.Arrays;

    import java.util.ArrayList;

    public class SpanningTree{

    private static int MAX = 100;

    private double cost[][] = new double[MAX][MAX];

    private ArrayList edge = new ArrayList();

    private int[] near = new int[MAX];

    private static double INFINITY = 99999999.99;//定义无穷大

    private double mincost = 0.0;//最小成本

    private int n;//结点个数

    public SpanningTree(){}

    public static void main(String args[]){

    SpanningTree sp = new SpanningTree();

    sp.init();

    sp.prim();

    sp.print();

    }

    //初始化

    public void init(){

    Scanner scan = new Scanner(System.in);

    int p,q,w;

    System.out.println("spanning tree begin!Input the node number:");

    n = scan.nextInt();

    //二维数组的填充要注意

    for(int i = 0; i < MAX; ++i){

    Arrays.fill(cost[i],INFINITY);

    }

    System.out.println("Input the graph(-1,-1,-1 to exit)");

    while(true){

    p = scan.nextInt();

    q = scan.nextInt();

    w = scan.nextInt();

    if(p < 0 || q < 0 || w < 0){

    break;

    }

    cost[p][q] = w;

    cost[q][p] = w;

    }

    Edge tmp = getMinCostEdge();

    edge.add(tmp);

    p = tmp.start;

    q = tmp.end;

    mincost = cost[p][q];

    for(int i = 1; i <= n; ++i){

    if(cost[i][p] < cost[i][q]){

    near[i] = p;

    }else{

    near[i] = q;

    }

    }

    near[p] = near[q] = 0;

    }

    //寻找最小成本的边

    public Edge getMinCostEdge(){

    Edge tmp = new Edge();

    double min = INFINITY;

    for(int i = 1; i < n; ++i){

    for(int j = i+1; j <= n; ++j){

    if(cost[i][j] < min){

    min = cost[i][j];

    tmp.start = i;

    tmp.end = j;

    }

    }

    }

    //System.out.println(min);

    return tmp;

    }

    //prim算法主体

    public void prim(){

    //找剩下的n-2条边

    for(int i = 2; i < n; ++i){

    double min = INFINITY;

    Edge tmp = new Edge();

    for(int j = 1; j <= n; ++j){

    if(near[j] != 0 && cost[j][near[j]] < min){

    tmp.start = j;

    tmp.end = near[j];

    min = cost[j][near[j]];

    }

    }

    mincost += cost[tmp.start][tmp.end];

    edge.add(tmp);

    near[tmp.start] = 0;

    for(int k = 1; k <= n; ++k){

    if(near[k] != 0 && cost[k][near[k]] > cost[k][tmp.start]){

    near[k] = tmp.start;

    }

    }

    }

    if(mincost >= INFINITY){

    System.out.println("no spanning tree");

    }

    }

    //打印结果

    public void print(){

    for(int i = 0; i < edge.size(); ++i){

    Edge e = edge.get(i);

    System.out.println("the " + (i+1) + "th edge:" + e.start + "---" + e.end);

    }

    }

    }

    class Edge

    {

    public int start;//始边

    public int end;//终边

    }

    展开全文
  • /**日期:2010-04-18 11:37*开发者:heroyan*联系方式:zndxysf@126.com*功能:无向图最小生成树Prim算法实现案例*/import java.util.Scanner;import java.util.Arrays;import java.util.ArrayList;public class ...

    /*

    *日期:2010-04-18 11:37

    *开发者:heroyan

    *联系方式:zndxysf@126.com

    *功能:无向图最小生成树Prim算法实现案例

    */

    import java.util.Scanner;

    import java.util.Arrays;

    import java.util.ArrayList;

    public class SpanningTree{

    private static int MAX = 100;

    private double cost[][] = new double[MAX][MAX];

    private ArrayList edge = new ArrayList();

    private int[] near = new int[MAX];

    private static double INFINITY = 99999999.99;//定义无穷大

    private double mincost = 0.0;//最小成本

    private int n;//结点个数

    public SpanningTree(){}

    public static void main(String args[]){

    SpanningTree sp = new SpanningTree();

    sp.init();

    sp.prim();

    sp.print();

    }

    //初始化

    public void init(){

    Scanner scan = new Scanner(System.in);

    int p,q,w;

    System.out.println("spanning tree begin!Input the node number:");

    n = scan.nextInt();

    //二维数组的填充要注意

    for(int i = 0; i < MAX; ++i){

    Arrays.fill(cost[i],INFINITY);

    }

    System.out.println("Input the graph(-1,-1,-1 to exit)");

    while(true){

    p = scan.nextInt();

    q = scan.nextInt();

    w = scan.nextInt();

    if(p < 0 || q < 0 || w < 0){

    break;

    }

    cost[p][q] = w;

    cost[q][p] = w;

    }

    Edge tmp = getMinCostEdge();

    edge.add(tmp);

    p = tmp.start;

    q = tmp.end;

    mincost = cost[p][q];

    for(int i = 1; i <= n; ++i){

    if(cost[i][p] < cost[i][q]){

    near[i] = p;

    }else{

    near[i] = q;

    }

    }

    near[p] = near[q] = 0;

    }

    //寻找最小成本的边

    public Edge getMinCostEdge(){

    Edge tmp = new Edge();

    double min = INFINITY;

    for(int i = 1; i < n; ++i){

    for(int j = i+1; j <= n; ++j){

    if(cost[i][j] < min){

    min = cost[i][j];

    tmp.start = i;

    tmp.end = j;

    }

    }

    }

    //System.out.println(min);

    return tmp;

    }

    //prim算法主体

    public void prim(){

    //找剩下的n-2条边

    for(int i = 2; i < n; ++i){

    double min = INFINITY;

    Edge

    展开全文
  • 最小生成树Prim算法java实现

    千次阅读 2018-10-17 19:47:25
    package prim; import java.util.*; public class PrimTest { public static void main(String[] args) { //交互输入图的邻接矩阵表示,为方便测试,直接给定了邻接矩阵值 // System.out.println(&quot;请...
    package prim;
    
    import java.util.*;
    
    public class PrimTest {
    	
    	public static void main(String[] args) {
    //交互输入图的邻接矩阵表示,为方便测试,直接给定了邻接矩阵值
    //		System.out.println("请输入图定点个数: ");
    //		Scanner sc = new Scanner(System.in);
    //		String line = sc.nextLine();
    //		int n = Integer.parseInt(line);
    //		System.out.println("请输入图的路径长度: ");
    //		int[][] c = new int[n+1][n+1];
    //		for(int i = 0; i < n; i++) {
    //			line = sc.nextLine();
    //			String[] ds = line.split(",");
    //			for(int j = 0;j < ds.length; j++) {
    //				c[i+1][i+1] = Integer.parseInt(ds[j]);
    //				
    //			}
    //		}
    //		System.out.println("一次构成树的边为: ");
    		int n = 6;
    		//c[i][j]表示从i到j的权,
    		自己到自己的权,以及不能直接到的值置-1,方便后面处理
    		int[][] c = {
    						{0,0,0,0,0,0},
    						{0,-1,6,1,5,-1,-1},
    						{0,6,-1,5,-1,3,-1},
    						{0,1,5,-1,5,6,4},
    						{0,5,-1,5,-1,-1,2},
    						{0,-1,3,6,-1,-1,6},
    						{0,-1,-1,4,2,6,-1}
    		};
    		prim(n,c);
    		
    	}
    	public static void prim(int n, int[][] c) {
    		//lowcost[i] 表示 从1到i的最短权值
    		int[] lowcost = new int[n+1];
    		//closest[i]的表示:
    		将整个节点空间定为V,已选的空间从S=1(只有第一个点)开始,
    		j在V-S中,找到S里离j最近的节点i ,就记录在closest[j]int[] closest = new int[n+1];
    		//哪些节点已经进入S空间
    		boolean[] s = new boolean[n+1];
    		//节点1进入S中,此为初始化
    		s[1] = true;
    		//初始化
    		for(int i = 2; i <= n; i++) {
    			//初始化第一个节点到每个节点权值
    			lowcost[i] = c[1][i];
    			//初始化,因为S中只有1,所以每个V-S中的节点最近的S中的节点一定是1
    			closest[i] = 1;
    			//这些节点都初始化为不在S中的状态
    			s[i] = false;
    		}
    		//n-1次遍历,把S空间扩充成V
    		for(int i = 1;i < n; i++) {
    			//记录一个当前最小权值,不断比较最终变为整个1次遍历过程的最小权值
    			int min = Integer.MAX_VALUE;
    			//初始化j,j其实代表的是V-S空间中被选进S的节点
    			//它的特征是,它到S(任何节点)的权值比其他节点到S(同样随便哪个节点)都小
    			//这里的思想就是贪心的概念,通过局部最优可以得到全局最优
    			int j = 1;
    			//遍历除了直接初始化在S中的1节点外的其他所有节点
    			for(int k = 2; k <= n; k++) {
    				//不等于-1即,直接有权值,然后迭代出最小的lowcost,同时更新一些值。
    				//这里举例更容易说明,如lowcost[k]其实代表的是目前的S空间到k的最小权值,迭代找到了这个k,那么 显然 j就应该是k
    				if(lowcost[k] != -1 && lowcost[k] < min && !s[k]) {
    					min = lowcost[k];
    					j = k;
    				}
    			}
    			//输出这对连接,closest[j]记录的其实就是达成lowcost[k]这一最小权值时,S中具体是哪个节点
    			System.out.println(closest[j] + "-" + j);
    			//如此,把j纳入S空间
    			s[j] = true;
    			//j进入S空间后,更新除1节点外所有节点的状态,他们到S的最小权值还得看看他们到 新进入的j是否更小
    			for(int k = 2; k <= n; k++) {
    				if(!s[k] && c[j][k] != -1) {
    					//这里注意,如果lowcost[k]本来是-1
    					说明本来都不相连直接可以更新了
    					//这里的逻辑要搞清楚,先判断有必要更新么?(c[j][k]!= -1),然后判断 要么c[j][k]比之前的权值更小,要么原来都不相连(c[j][k] < lowcost[k] || lowcost[k] == -1) 此时进行更新!
    				if(c[j][k] < lowcost[k] || lowcost[k] == -1) {
    						//更新该节点最小的权值
    						lowcost[k] = c[j][k];
    						//更新该节点在S中最近的点
    						closest[k] = j;
    					}
    				}
    			}
    			
    		}
    	}
    }
    
    展开全文
  • Prim 算法 Java实现

    2019-01-05 17:36:08
    import java.util.Arrays; class MST{ int startVertex; int endVertex; int length; boolean sure = false; public MST(int startVertex, int endVertex, int length) { this.sta...
  • import java.util.Scanner; public class prim1 { public static void main(String[] args) { int [][] s=new int[100][100]; int i,j; int counter=2,startmin=1000; for( i=0;i<100;i++) { ...
  • 本文本采用的是java编写的最小生成树Prim算法,参考书:计算机算法设计与分析
  • prim算法(java)附代码

    千次阅读 2019-09-12 12:24:54
    记录prim算法学习
  • java实现Prim算法

    万次阅读 多人点赞 2019-07-22 20:57:51
    何为Prim算法? 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边...
  • Prim算法java实现

    2020-05-04 10:57:26
    LinkedHashSet actual = new Prim().prim(n, grap, 1); Iterator it = actual.iterator(); while (it.hasNext()) { Vertex vertex = it.next(); System.out.println(vertex.index + ", " + vertex.parent + ", " + ...
  • Prim算法Java实现

    2017-04-12 17:01:55
  • java算法分析与设计之最小生成树(prim算法)源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少...
  • JAVA实现Prim算法

    2021-01-03 16:34:56
    普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为...
  • 边的实现,同时表示了两个顶点和权重,个人理解 Prim 算法是不断的找最小的横切边,因此边使用这样的表示方便我们获得边的信息 /** 边的构建 */ class Edge implements Comparable<Edge> { int v; int w; ...
  • prim算法的实现

    2011-11-28 15:41:38
    prim算法是关于求一个图的最小生成树问题,算法简单易懂,容易实现。
  • Prim 算法本质就是就是求最小生成树问题, 最小生成树(Minimum Cost Spanning Tree),简称MST。 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树 N个顶点,一定有N-1条...
  • prim算法创造一个随机生成的迷宫,墙和道路分别用0和1来表示,只有一个入口但可以有一个或者两个出口,请用二维数组构建迷宫,迷宫的长和宽由使用者来输入(如果需要,可以假设长和...
  • 算法思路 以图的一个节点开始 遍历已被访问的节点,找出未访问且权值最小的节点以及边,加入树中 只要树的边数小于节点数 - 1就执行第二步 算法实现 图的实现 此实现方法没有节点类 采用邻接矩阵和顶点索引 边类...
  • Prim算法JAVA

    2020-12-21 15:27:22
    import java.util.Arrays; public class Prim { public static void main(String[] args) { //测试看看图是否创建成功 char[] data = new char[]{'A','B','C','D','E','F','G'}; int verxs = data.length; //...
  • 普里姆算法介绍普里姆(Prim)算法,是用来求加权连通图的最小生成树的算法。基本思想对于图G而言,V是所有顶点的集合;现在,设置两个新的集合U和T,其中U用于存放G的最小生成树中的顶点,T存放G的最小生成树中的边。...
  • /// ///普利姆迷宫生成法/// /// 起始点X坐标/// 起始点Y坐标/// 迷宫宽度/// 迷宫高度/// 迷宫是否含有墙private int[,] Prim(int startX, int startY, int widthLimit, int heightLimit,boolhaveBorder){//block:...
  • Prim算法 基本思想 确定一个顶点集合U和一个边集合TE,确定初始顶点并放入U中,寻找其邻接边中的最小值边,并将这条边放入TE,将连着的另一个顶点也放入U中 将U中的顶点看作一个整体(看作一个顶点),寻找这个整体...
  • 普里姆算法是图结构中寻找最小生成树的一种算法。所谓生成树,即为连通图的极小连通子图,其包含了图中的n个顶点,和n-1条边,这n个顶点和n-1条边所构成的树即为生成树。当边上带有权值时,使生成树中的总权值最小的...
  • prim算法:将顶点分成两个集合 U和 V,U用来存放每次遍历得到的与U中顶点最小路径的邻接顶点,V用来存放U中没有的顶点。U初始化存放任意一个顶点,每次从V中遍历得到与U集合中的顶点最小路径的顶点后,放入U,将V中...
  • Prim算法java

    2018-11-17 20:56:21
    import java.util.ArrayList; import java.util.List; import java.util.Scanner;...public class Prim { public char[] vexs;//节点 public int vex_number;//节点数 public int edge_number;//边数 publ...
  • Java实现最小生成树算法(Prim算法)

    千次阅读 2019-06-21 10:29:15
    Prim算法 Prim算法,每一步都会为一颗生长中的树添加一条边。一开始这棵树只有一个顶点,然后哦会向它添加V-1条边,每次总是将下一条连接树的顶点与不在树中且权重最小的边加入树中 实现 最小生成树的延迟实现 通过...
  • Prim算法JAVA 清楚易懂

    2021-06-03 16:19:45
    import java.util.Scanner; public class Prim { static int map[][];//图 static int n;//节点个数 static boolean vis[];//标记节点是否在树中 public static void main(String[] args) { Scanner in =new ...
  • 最小生成树1,普里姆算法Prim)2,克鲁斯卡尔算法(Kruskal) 1,普里姆算法Prim) 此算法可以称为“加点法”,每次迭代选择代价最小的边对应的点,加入到最小生成树中。算法从某一个顶点s开始,逐渐长大覆盖...
  • Java 算法:Prim算法

    2019-04-24 11:43:15
    Prim算法的第一个实现 Lazy Prim 从0开始: 此时与0相连的边就放入最小堆中。 思想:例如从0开始寻找最小切分边,此时的与7连接的边就是最小生成边,所以就将7这个节点变为和0一样的颜色: 此时就产生了新的横...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,945
精华内容 1,978
关键字:

prim算法java

java 订阅