精华内容
下载资源
问答
  • 最小代价生成 树是各边权值的总和最小的生成树普里姆算法(Prim)步骤:1、选取源点作为最小生成树的结点,并初始化当前与生成树相连的最好情况,即权值最小的边2、选取权值最小的边加入生成树,并更新各顶点的最好...

    最小生成树:带权图的生成树上的各边权 值之和称为这棵树的代价。最小代价生成 树是各边权值的总和最小的生成树。

    普里姆算法(Prim)步骤:
    1、选取源点作为最小生成树的结点,并初始化当前与生成树相连的最好情况,即权值最小的边

    2、选取权值最小的边加入生成树,并更新各顶点的最好情况。

    3、重复步骤2,直到所有顶点都加入生成树当中。

    代码如下:
    #include<stdio.h> #include<string.h> #include<iostream> #define MAX 100 #define INF 10000000 typedef struct { int adjvex; //存放的这条权值最小的边的另一个顶点 int lowcost;           //存放的这条权值最小的边的权值 }Path; typedef struct { int arc[MAX][MAX]; int arcnum, vexnum; }AGraph; AGraph T; int minclosedge(Path closedge[]) { int min, j, k; min = INF; k = -1; for (j = 0; j < T.vexnum; j++) { if (closedge[j].lowcost != 0 && closedge[j].lowcost < min) { min = closedge[j].lowcost; k = j; } } return k; } void prim(AGraph T, int u) //起点为u { int i, j, k; Path closedge[MAX]; for (j = 0; j < T.vexnum; j++) { closedge[j].adjvex = u; closedge[j].lowcost = T.arc[u][j]; } closedge[u].lowcost = 0; // closedge[w].lowcost==0表示w已经加入生成树 for (i = 1; i < T.vexnum; i++) { k = minclosedge(closedge); printf("<%d,%d> ", closedge[k].adjvex, k); closedge[k].lowcost = 0; for (j = 0; j < T.vexnum; j++) { if (T.arc[k][j] < closedge[j].lowcost) { closedge[j].lowcost = T.arc[k][j]; closedge[j].adjvex = k; } } } } int main() { int i, j; printf("请输入图的顶点数:\n"); scanf_s("%d", &T.vexnum); printf("请%d阶输入邻接矩阵的值:\n", T.vexnum); for(i = 0; i < T.vexnum; i++) for (j = 0; j < T.vexnum; j++) scanf_s("%d", &T.arc[i][j]); prim(T, 0); //起点为0 system("pause"); }

    编译环境: Visual Studio
    展开全文
  • 普里姆算法基本思想】从图中任取一个顶点作为一棵树。然后从与这棵树相连的边中选取...以此类推,直到图中所有顶点都被并入这棵树中为止,此时便得到了该图的最小代价生成树。【普里姆算法用到的存储结构】用普里...

    【普里姆算法基本思想】从图中任取一个顶点作为一棵树。然后从与这棵树相连的边中选取一条最短(权值最小)的边,并将该边及其所连接的顶点也并入这个树中,此时便得到了具有两个顶点的树。接着从与这棵树相连的边中选取一条最短的边,并将该边及其所连接的顶点也并入这个树中,得到了了具有三个顶点的树。以此类推,直到图中所有顶点都被并入这棵树中为止,此时便得到了该图的最小代价生成树。

    【普里姆算法用到的存储结构】用普里姆算法构造最小代价生成树的过程中,需要建立两个数组vset[]和lowcost[]。vset[i]=1表示顶点i已经被并入生成树中,vset[i]=0表示顶点i还没有被并入生成树中。lowcost[]数组中存放当前生成树到剩余各个顶点最短边的权值。即,当前生成树这一个整体到其余各个顶点的权值的最小值(因为当前生成树到其余各个顶点的边可能存在多条,固然可能存在多个权值,但是lowcost[]中只存权值的最小值),而不是针对生成树中的某一个顶点。

    【普里姆算法执行过程】从某一个顶点V0开始构造最小生成树:① 将V0到其他顶点的所有边作为当前的候选边;② 重复以下步骤n-1次,使得其余n-1个顶点被并入到生成树中;(1)从候选边中挑选出权值最小的边输出,并将与该边另一端相连的顶点V并入到生成树中;(2)考查所有剩余顶点Vi,如果(V,Vi)的权值比lowcost[Vi]小,则用V,Vi)的权值更新lowcost[Vi]。

    【普里姆算法时间复杂度分析】普里姆算法的时间复杂度为O(n2)。可见普里姆算法的时间复杂度只与图中顶点有关系,与边数没有关系,因此普里姆算法适用于稠密图(我的理解就是点相对于边来说要少)。

    【普里姆算法Java代码】

    public class Main{
    	public int prim(int[][] graph,int v0){
    		int[] vset = {0,0,0,0,0};
    		int lowcost[] = {0,0,0,0,0};
    		int min_index = 0;
    		int v = v0;
    		int sum = 0;
    		//初始化lowcost数组
    		for (int i = 0; i < graph.length; i++) {
    			lowcost[i] = graph[v0][i];
    		}
    		//将顶点v0并入生成树
    		vset[v0] = 1;	
    		//重复以下步骤n-1次,直到所有顶点都被并入生成树
    		for (int i = 1; i < graph.length; i++) {
    			int min = 10;
    			//选出当前生成树到其余顶点最短边中最短的一条
    			for (int j = 0; j < graph.length; j++) {
    				if (vset[j] == 0 && lowcost[j] < min) {
    					min = lowcost[j];
    					min_index = j;
    				}
    			}
    			//将最短边连接的顶点并入生成树
    			vset[min_index] = 1;
    			v = min_index;
    			sum += min;
    			System.out.println("第"+i+"次加入到生成树中的顶点为:"+v);
    			//考查所有剩余顶点Vi,如果(V,Vi)的权值比lowcost[Vi]小,则用V,Vi)的权值更新lowcost[Vi]
    			for (int k = 0; k < graph.length; k++) {
    				if (vset[k] == 0 && graph[v][k] < lowcost[k]) {
    					lowcost[k] = graph[v][k];
    				}
    			}
    		}
    		return sum;
    	}
    	
        public static void main(String[] args) {
            Main main = new Main();
            int[][] graph = {{10,5,1,2,10},
    				 {5,10,3,10,4},
    				 {1,3,10,6,2},
    				 {2,10,6,10,3},
    				 {10,4,2,3,10}};
            System.out.println("最小生成树的代价为:"+main.prim(graph, 0));
        }
    }

    展开全文
  • 最小生成树 普里姆算法

    千次阅读 2020-02-15 11:56:24
    构造成连通网的最小代价生成树(MinimumCostSpanningTree)称为最小生成树(简称MST)。 找连通网的最小生成树,经典的有两种算法,普里姆算法和克鲁斯卡尔算法。 普里姆(Prim)算法 对于图中的网来看,找出了它...

    构造成连通网的最小代价生成树(MinimumCostSpanningTree)称为最小生成树(简称MST)。

    找连通网的最小生成树,经典的有两种算法,普里姆算法和克鲁斯卡尔算法。

    普里姆(Prim)算法

    对于图中的网来看,找出了它所有的生成树,其中T3和T5的各边权值之和最小,所以T3和T5都是最小生成树,可见最小生成树不一定为1。

    普里姆算法思想:

    假设N= (P;{E}) 是连通网,TE是N上最小生成树中边的集合。算法从U={uo}(uo∈V), TE={}开始。重复执行下述操作:在所有u∈U,v∈V←U的边(u,v) ∈E中找-一条代价最小的边(uo,vo) 并入集合TE,同时vo并入U,直至U=V为止。此时TE中必有n-1条边,则T= (V,{TE})为N的最小生成树。

    • G=(V,E)是具有n个顶点的连通图,设U是最小生成树中顶点的集合,TE是最小生成树中边的集合;
    • 初始,U={u1},TE={ }
    • 重复执行:在所有u∈U,v∈V-U的边(u,v)中寻找代价最小的边(u’,v’),并纳入集合TE中;同时将v’纳入集合U中;
    • 直至U=V为止。
    • 集合TE中必有n-1条边
    • 普利姆算法的时间复杂度为O(n2),与网中的边数无关,因此适用于求边稠密的网的最小生成树。

    void MiniSpanTree Prim(MGraph G)
    {
    	int min, i, j, k;
    	int adjvex[MAXVEX]; /* 保存相关顶点下标*/
    	int lowcost[MAXVEX]; /* 保存相关顶点间边的权值 */
    	lowcost[0] = 0;  /*初始化第一个权值为0, 即v。加入生成树* /
    					/* lowcost的值为0,在这里就是此下标的顶点已经加入生成树*/
    	adjvex[0] = 0; /* 初始化第一一个顶点下标为0 */
    	for (i = 1; i < G.numVertexes; i++) /*循环除下标为0外的全部顶点*/
    	{
    		lowcost[i] = G.arc[0][i];/*将Vo顶点与之有边的权值存入数组*/
    		adjvex[i] = 0;			/*初始化都为v0的下标*/
    	}
    	for (i = 1; 1 < G.numVertexes; i++)
    	{
    		min = INFINITY; /*初始化最小权值为∞,*/
    		/*通常设置为不可能的大数字如32767、 65535等*/
    		j = 1; k = 0;
    		while (j < G.numVertexes)	/*循环全部顶点 */
    		{
    			if (lowcost[j]!= 0 && lowcost[j] < min)      //生成树的顶点不参与最小权值的查找
    			{/*如果权值不为0且权值小于min */
    				min = lowcost[j];	/* 则让当前权值成为最小值*/
    				k = j;		/*将当前最小值的下标存入k */
    			}
    			j++;
    		}
    		printf("%d,%d", adjvex[k], k);/*打印当前顶点边中权值最小边*/
    		lowcost[k] = 0;/*将当前顶点的权值设置为0, 表示此顶点已经完成任务*/
    		for (j = 1; j < G.numVertexes; j++)/*循环所有顶点 */
    		{
    			if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
    			{
    				/*若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值*/
    				lowcost[j] = G.arc[k][j];/*将较小权值存入lowcost*/
    				adjvex[j] = k;			/*将下标为k的顶点存入adjvex */
    			}
    		}
    	}
    }
    

    克鲁斯卡尔算法

    同样的 思路,我们也可以直接就以边为 目标去构建,因为权值是在边上,直接去 找最小权值的边来构建生成树也是很自然的想法,只不过构建时要考虑是否会形成环路而已。此时我们就用到了图的存储结构中的边集数组结构。

    我们将图的邻接矩阵通过程序转化为右图的边集数组,并且对它们按权值从小到大排序。

    使用贪心准则,从剩下的边中选择具有最小权值且不会产生环路的边加入到生成树的边集中。其操作为:

    • 确定权值最小的边
    • 判断一条边所关联的两个顶点是否在一个联通分量中;
    • 如果不是则合并两个顶点所属的连通分量。

    假设N= (V,{E}) 是连通网,则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V,0}, 图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。 依次类推,直至T中所有顶点都在同一连通分量上为止。
     

    /*对边集数组Edge结构的定义*/
    typedef struct
    {
    	int begin;
    	int end;
    	int weight;
    }Edge;
    
    //Kruskal算法生成最小生成树
    void MiniSpanTreeKruskal(MGraph G) /*生成最小生成树*/
    {
    	int i, n, m;
    	Edge edges[MAXEDGE]; /*定义边集数组*/
    	int parent[MAXVEX]; /*定义一数组用 来判断边与边是否形成环路*/
     /*此处省略将邻接矩阵G转化为边集数组edges并按权由小到大排序的代码*/
    	for (i = 0; i < G.numVertexes; i++)
    		parent[i] = 0; /* 初始化数组值为0 */
    	for (i = 0; i < G.numEdges; i++) /*循环每一条边*/
    	{
    		n = Find(parent, edges[i].begin);
    		m = Find(parent, edges[i].end);
    		if (n != m) /*假如n 与m不等,说明此边没有与现有生成树形成环路*/
    		{
    			parent[n] = m;/*将此边的结尾顶点放入下标为起点的parent中*/
    			/*表示此顶点已经在生成树集合中 */
    			printf("(%d,%d) %d", edges[i].begin, edges[i].end, edges[i].weight);
    		}	
    	}
    }
    
    int Find(int parent, int f) /*查找连线顶点的尾部下标 */
    {
    	while (parent[f] > 0)
    		f = parent[f];
    	return f;
    }
    

     

    展开全文
  • 而在连通网上面,我们称这类问题为最小代价生成树(最小生成树)问题。今天我们主要讨论的是用普里姆算法实现最小生成树。 如图所示,a图是一个有权值的连通图。要对其进行最小生成树求解,假设初始点为V1,寻找与1...

    当我们要求解n个连接城市之间的路线问题,就需要我们进行一个计算。

    而在连通网上面,我们称这类问题为最小代价生成树(最小生成树)问题。今天我们主要讨论的是用普里姆算法实现最小生成树。

    如图所示,a图是一个有权值的连通图。要对其进行最小生成树求解,假设初始点为V1,寻找与1有关系而且权值最小的顶点

                                                                      (图源严蔚敏版数据结构)           V2进行访问,再从点V2寻找下一个有关系而且权值最小的顶点,若访问的点将构成闭合回路,将进行回溯,回溯到上一个点,再进行访问。直至走完所以顶点。

    代码实现:

    /**求顶点位置**/
    int Locatvex(ArrayGraph G,char u)
    {
        int i,a;
        for(i=0;i<MAXN;i++)
        {
            if(u==G.vex[i])///循环求得u顶点的位置
            {
                a=i;
                return a;///返回a
            }
        }
        a=-1;
        return a;
    }
    /**返回最小代价边**/
    int minimum(struct node *closedage)
    {
        int MIN=INF;///MIN用于表示最短距离
        int k=-1;
        int i;
        for(i=0;i<MAXN;i++)
        {
            if(closedage[i].lowcost<MIN&&closedage[i].lowcost!=0)///如果两顶点有关系,且权值小于MIN
            {
                MIN=closedage[i].lowcost;///更新MIN,直至找到最近的顶点
                k=i;
            }
        }
        return k;
    }
    /**最小生成树**/
    void primG(ArrayGraph G,char u)///u表示规定的起始点
    {
        int i,j;
        int k;
        k=Locatvex(G,u);///求取顶点位置
        for(i=0;i<MAXN;++i)
        {
            if(i!=k)
            {
                closedage[i].data=u;
                closedage[i].lowcost=G.arcs[k][i];
            }
        }
        closedage[u].lowcost=0;///初始化

        for(i=0;i<MAXN;i++)///循环寻找下一个顶点
        {
            k=minimum(closedage);///k为两顶点最小权值
            printf("%c\t",G.vex[k]);///输出
            closedage[k].lowcost=0;
            for(j=0;j<MAXN;j++)
            {
                if(G.arcs[k][j]<closedage[j].lowcost)
                {
                    closedage[j].data=G.vex[k];
                    closedage[j].lowcost=G.arcs[k][j];
                }
            }
        }
    }

    运行结果:

    时间复杂度:O(n²)

    假设图中共有n个顶点,则进行第一个循环的频度为n,第二个循环的频度为n-1。而重新求取最小代价边的频度为n。因此时间复杂度为O(n²)

    展开全文
  • 所谓最小生成树就是最小代价生成树,其经典算法有普利姆算法和克鲁斯卡尔算法,这篇来看看普利姆算法 废话不多说,先上代码,再慢慢解析: typedef char VertexType; //顶点类型,可根据需要修改 typedef int ...
  • 图的最小生成树-普里姆算法

    千次阅读 2019-02-28 19:48:48
    最小生成树:把构造连通网的最小代价生成树称为最小生成树。(一棵生成树的代价就是树上各边的代价之和)。 二、经典算法 1、普里姆算法(主要针对顶点展开的,对于稠密图,即边数非常多的情况会更好一些) 主要...
  • 若要在n个城市之间建设通信网络,只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网,是一个网...(2)利用普里姆算法和克鲁斯卡尔算法求网的最小生成树; (3)按顺序输出生成树中各条边以及它们的权值。
  • 首先明确下概念,我们把构造连通网的最小代价生成树叫做最小生成树(Minimum Cost Spanning Tree) 给定一个连通网,求最小生成树的方法有:普里姆(Prim)算法 &克鲁斯卡尔(Kruskal)算法 普里姆算法...
  • 最小生成树:构造连通图的最小代价生成树即在上图(网结构)中找到权值之和最小的生成树的路径。实现最小生成树有两种算法普里姆(Prim)算法构造邻接矩阵实现void MiniTree(MGraph G) { int min,i,j,k; int adjvex...
  • 称为该连通网的最小代价生成树,简称最小生成树; 简单点说,就是各个点连通,边权和最小的那棵树 2、先说一下代码的核心思想(不知道核心看代码很费劲的) 首先随便找一个顶点V0,存放在集合U中,我们寻找从...
  • 最小生成树:构造连通网的最小代价生成树 算法 算法思想:假设N=(V, {E})是连通网,TE是N上最小生成树中边集合。算法从U={a}, TE={}开始。重复下述操作:寻找从与a有关联的边中,权重最小的那条边,并且该边的终点b...
  • 最小生成树 用来解决工程中的代价问题。   一:普里姆算法     具体代码用C语言实现如下: typedef int VRType; typedef char InfoType; #define MAX_NAME 3 /* 顶点字符串的最大长度+1 */ #define ...
  • 最小生成树问题的概念—普里姆算法是从点的角度来解决。若在解决问题过程中需要遍历图的所有点,则普里姆算法更好。 基本思想: 普里姆算法更像构建一棵树。联想我们构建二叉树的过程,从根节点出发,构建左右子树,...
  • 普里姆(Prim)算法求解最小生成树

    千次阅读 2013-03-05 18:40:31
    我们把构造连通网的最小代价生成树称为最小生成树。 Prim算法: 假设N=(P,{E})是连通网,TE是N上最小生成树中边的集合。算法从U={u0} (u0∈V),TE={}开始。重复执行下述操作:在所有的u∈V-U的边(u,v)∈E中找一...
  • 利用普里姆算法求网的最小代价生成树。 以文本形式输出生成树中各条边以及他们的权值。
  • 文字描述  用连通网来表示n个城市及n个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两...这个问题就是构造连通网的最小代价生成树(Minimum Cost Spanning Tree: 最小生成树)的问题。一棵生成树的代...
  •  我们把构造连通网的最小代价生成树称为最小生成树。经典的算法有两种,普利姆算法和克鲁斯卡尔算法。 普里姆算法打印最小生成树:  先选择一个点,把该顶点的边加入数组,再按照权值最小的原则选边,选完最小...
  • 最小代价生成树:两种方式普里姆算法和克鲁斯卡尔算法 这两种算法均是针对无向图 最小生成树是唯一的条件:图中所有边的权值不相等,或者有相等的边,但是在构造最小生成树的过程中权值相等的边都被并入生成树的...
  •  最小生成树代价最小生成树。【例】网络G表示n各城市之间的通信线路网线路(其中顶点表示城市,边表示两个城市之间的通信线路,边上的权值表示线路的长度或造价)。可通过求该网络的最小生成树达到求解通信线路...
  • 我们把构造连通网的最小代价生成树称为最小生成树或给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树. (二)什么是最小生成树? 1.是一棵树 1)无回路 2)N个...
  • 一、普里姆算法(Prim)1、条件:图为邻接矩阵结构(AdjacencyList)2、原理:假设WN=(V,{E})是一个含有n个顶点的连通网,TV是WN上最小生成树中顶点的集合,TE是最小生成树中边的集合。显然,在算法执行结束时,TV=V,而...
  • 普里姆(Prim)算法求解最小生成树原理 假设N=(P,E)N=(P,{E})N=(P,E)是连通网,TETETE是NNN上最小生成树中的边集合。算法从U=U0(U0∈V),TE={}U={U_{0}}(U_{0} \in V),TE = \{\}U=U0​(U0​∈V),TE={}开始,重复执行...
  • 最小代价生成树】 无向连通图G:含n个顶点 若G存在由n-1条边连通n个顶点的子图G',则称G'为G的一棵生成树。 若G的每一条边都赋了一个权值,则称此图为网络。 最小代价生成树:在一个网络的各种生成树中,具有...
  • 一、实验名称:最小代价生成树 二、实验目的: 1.掌握贪心算法解决问题的思想和一般过程,2.学会使用普里姆算法解决实际问题。 三、实验内容 完善下列程序,并回答问题。 1 #include<iostream.h> ...
  • /**//*算法概述:假设N=(V,E)是连通图 ,TE是N上的最小生成树中的边集合。算法从定点集合U={u0}(u0属于v),边集合TE开始为空,在u属于集合U,v 属于集合V-U的边(u,v)属于E中找一条代价最小边 */#includestdio....
  • 算法:图解最小生成树普里姆(Prim)算法

    万次阅读 多人点赞 2013-04-30 21:32:02
    我们在图的定义中说过,带有权值的图就是网结构。...综合以上两个概念,我们可以得出:构造连通网的最小代价生成树,即最小生成树(Minimum Cost Spanning Tree)。 找连通图的最小生成树,经典的有两种
  • prim算法最小生成树: /* 题目 1705: 算法7-9:最小生成树 输入 输入的第一行包含一个正整数n,表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数,对于第i行的第j个整数,如果不为0,...
  • 最小生成树-Prim(普里姆)算法 算法定义: 假设 N=( V,{E} )(V为顶点集,E为边集合)是连通网,TE是N上最小生成树中边的集合,U为N上最小生成树的顶点集 算法从U={u0}(u0为选定的起点,u0∈V),TE={}...
  • (2)利用普里姆算法求网的最小生成树; (3)以文本文件形式输出生成树中各条边及它们的权值。 2.程序设计 本程序定义两个文件:一个是存放主函数的文件mcstree.cpp,另一个是存放算法用到的函数声明和

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 168
精华内容 67
关键字:

普里姆算法最小代价生成树