精华内容
下载资源
问答
  • Prim算法是通过每次选择提条代价最小的边辑器相应 的顶点加入到最小生成树中,因此来构造最小生成树。 二.基本步骤 设基本图为G=(V,E),最小生成树Tmst=(Vt,Et)。 ①从图G中的任意顶点Vm(Vm属于V)开始,将Vm加入最小...

    一.构造最小生成树必须满足以下条件
    ①只能使用图中的边;
    ②只能使用图中的n-1条边;
    ③添加的边不能产生回路;
    Prim算法是通过每次选择提条代价最小的边辑器相应 的顶点加入到最小生成树中,因此来构造最小生成树。
    二.基本步骤
    设基本图为G=(V,E),最小生成树Tmst=(Vt,Et)。
    ①从图G中的任意顶点Vm(Vm属于V)开始,将Vm加入最小生成树中;
    ②选择代价最小的边(Vk,Vj)加入最小生成书中,并将顶点Vj加入最小生成树中,要求两个顶点属于不同的集合,Vk属于Vt,Vj属于V-Vt;
    ③重复这个过程,直到Tmst中有n-1条边为止,即Vt=V;
    代码既及注释如下

    #include <stdio.h>
    #include <stdlib.h>
    #define MAX 1000
    typedef struct GRAPHMATRIX_STRU
    {
        int size;
        int **graph;
    }GraphMatrix;
    
    GraphMatrix* InitGraph(int num)
    {
        int i,j;
        GraphMatrix *graphMatrix=(GraphMatrix*)malloc(sizeof(GraphMatrix));
        graphMatrix->size=num;
        graphMatrix->graph=(int**)malloc(sizeof(int*)*graphMatrix->size);
        for(i=0;i<graphMatrix->size;i++)
            graphMatrix->graph[i]=(int*)malloc(sizeof(int)*graphMatrix->size);
        for(i=0;i<graphMatrix->size;i++)
        {
            for(j=0;j<graphMatrix->size;j++)
            graphMatrix->graph[i][j]=MAX;
    
        }
        return graphMatrix;
    }
    void ReadMatrix(GraphMatrix*graphMatrix)
    {
        int vex1,vex2,weight;
        scanf("%d%d%d",&vex1,&vex2,&weight);
        while(vex1!=0||vex2!=0)
        {
            graphMatrix->graph[vex1][vex2]=weight;
            scanf("%d%d%d",&vex1,&vex2,&weight);
        }
    
    }
    void WriteGraph(GraphMatrix*graphMatrix)
    {
        int i,j;
        printf("最小生成树的结构如下,输出方式为点,点,权值\n");
        for(i=0;i<graphMatrix->size;i++)
            for(j=0;j<graphMatrix->size;j++)
            if(graphMatrix->graph[i][j]<MAX)
            printf("%d %d %d\n",i,j,graphMatrix->graph[i][j]);
    }
    GraphMatrix* prim(GraphMatrix *graphMatrix,int source)
    {
        int i,j;
        int *component=(int*)malloc(sizeof(graphMatrix->size));
        int *distance=(int*)malloc(sizeof(graphMatrix->size));
        int*neigbor=(int*)malloc(sizeof(graphMatrix->size));
        GraphMatrix*tree=InitGraph(graphMatrix->size);
        for(j=0;j<graphMatrix->size;j++)
        {
            component[j]=0;
            distance[j]=graphMatrix->graph[source][j];
            neigbor[j]=source;
        }
        component[source]=1;
        for(i=1;i<graphMatrix->size;i++)
        {
            int v;
            int min=MAX;
            for(j=0;j<graphMatrix->size;j++)
            {
                if(!component[j]&&(distance[j]<min))
                {
                    v=j;
                    min=distance[j];
                }
            }
    
            if(min<MAX)
            {
                component[v]=1;
                tree->graph[v][neigbor[v]]=distance[v];
                tree->graph[neigbor[v]][v]=distance[v];
                for(j=0;j<graphMatrix->size;j++)
            {
                if(!component[j]&&(graphMatrix->graph[v][j]<distance[j]))
                {
                    distance[j]=graphMatrix->graph[v][j];
                    neigbor[j]=v;
                }
            }
            }
    
            else
                break;
        }
    
        return tree;
    }
    int main()
    {
       int i,j,k=0,num=6;
       GraphMatrix *graphMatrix=InitGraph(num);
       ReadMatrix(graphMatrix);
       GraphMatrix *tree=prim(graphMatrix,0);
       //WriteGraph(graphMatrix);
       for(i=0;i<graphMatrix->size;i++)
       {
    
        for(j=0;j<graphMatrix->size;j++)
        {
            if(tree->graph[i][j]==MAX)
              tree->graph[i][j]=0;
        }
       }
        for(i=0;i<graphMatrix->size;i++)
       {
        for(j=0;j<graphMatrix->size;j++)
        {
            k=k+tree->graph[i][j];
        }
       }
       printf("%d",k/2);
        return 0;
    }
    
    展开全文
  • prim算法 最小生成树

    2020-02-17 21:11:10
    Prim算法利用了MST的性质:假设N= (V,E)是一个连通图,U是顶点集V的一个非空子集,若(u,v)是一条最小权值的边,其中u属于U,v属于V-U,则必存在一颗包含(u,v)的最小生成树Prim算法的实现 普里姆算法的实现...

    Prim算法

    • Prim算法的由来

      Prim算法利用了MST的性质:假设N= (V,E)是一个连通图,U是顶点集V的一个非空子集,若(u,v)是一条最小权值的边,其中u属于U,v属于V-U,则必存在一颗包含(u,v)的最小生成树。

    • Prim算法的实现
      普里姆算法的实现假设一个无向网G以邻接矩阵形式存储,从顶点u出发构造G的最小生成树T,要求输出T的各条边。为实现这个算法需附设一个辅助数组closedge,以记录从U到V-U具有最小权值的边。。对每个顶点v∈V-U,在辅助数组中存在一个相应分量closedge[i-1],它包括两个域:lowcost和adjvex,其中lowcost存储最小边上的权值,adjvex存储最小边在U中的那个顶点。显然,closedge[i-1].-lowcost=min{cost(u,vi)lu∈U}其中cost(u,v)表示赋于边(u,v)的权。
      图例:在这里插入图片描述

    	//辅助数组结构
    	typedef struct
    	{
    		string adjvex;//最小边在U的那个顶点
    		int lowcost;//最小边的权值
    	}closedge[MVNum];
    	//辅助数组结构
    
    • Prim算法步骤
      ①首先将初始顶点u加入U中,对其余的每一个顶点,将closedge均初始化为到u的边信息。
      ②循环n-1次,做如下处理:
      ● 从各组边closedge中选出最小边closedge[k],输出此边;
      ●将k加入U中;
      ●更新剩余的每组最小边信息closedgel,对于V-U中的边,新增加了一条从k到j的边,如果新边的权值比closedge.lowcost小,则将closedgelowcost更新为新边的权值。

    • 运行结果
      在这里插入图片描述

    • 实现代码
      邻接矩阵和邻接表分别实现

    
    /*邻接矩阵实现
    	若要邻接表实现,初始化V时,只需将生成树的顶点的邻接边的权值赋给辅助数组,其余的全部辅为maxint
    	更新最小边时同样如此
    */
    	#include<iostream>
    	#include<string>
    	using namespace std;
    	
    	#define OK 1
    	#define ERROR 0
    	#define MAXint 32767 //表示无穷大
    	#define MVNum 100	//最大顶点数
    	
    	//邻接矩阵的结构
    	typedef struct
    	{
    		string vexs[MVNum];//顶点表
    		int arcs[MVNum][MVNum];//邻接矩阵,也就是表示边的权值
    		int vexnum, arcnum;//图的顶点数和边的个数
    	}AMGraph;
    	//邻接矩阵的结构
    	
    	//邻接表的结构
    	typedef struct ArcNode {//边结点
    		int adjvex;//该边所指向的顶点的位置
    		struct  ArcNode* nextarc;//指向下一条边的指针
    		int info;//和边相关的信息
    	}ArcNode;
    	
    	typedef struct {//顶点信息
    		string data;
    		ArcNode* firstarc;//指向第一条依附该顶点的边的指针
    	}VNode, AdjList[MVNum];
    	
    	typedef struct//邻接表
    	{
    		AdjList vertices;//顶点信息
    		int vexnum, arcnum;//图的当前顶点数和边数
    	}ALGraph;
    	//邻接表的结构
    	
    	//查询结点位置
    	int Locate(AMGraph G, string v)
    	{
    		for (int i = 0; i < G.vexnum; i++)
    		{
    			if (G.vexs[i] == v)
    			{
    				return i;
    			}
    		}
    		return -1;
    	}
    	//查询结点位置
    	
    	int Locate(ALGraph G, string v)//Locate重载
    	{
    		for (int i = 0; i < G.vexnum; i++)
    		{
    			if (G.vertices[i].data == v)
    			{
    				return i;
    			}
    		}
    		return -1;
    	}
    	
    	//辅助数组结构
    	typedef struct
    	{
    		string adjvex;//最小边在U的那个顶点
    		int lowcost;//最小边的权值
    	}closedge[MVNum];
    	//辅助数组结构
    	
    	
    	//创建邻接矩阵
    	int CreateUDN(AMGraph& G)//无向图的构造
    	{
    		cout << "请输入图的顶点数和边数:";
    		cin >> G.vexnum >> G.arcnum;
    		cout << "请输入各点的信息:";
    		for (int i = 0; i < G.vexnum; i++)
    		{
    			cin >> G.vexs[i];
    		}
    		for (int i = 0; i < G.vexnum; i++)//初始化边的权值为MAXINT
    		{
    			for (int j = 0; j < G.vexnum; j++)
    			{
    				G.arcs[i][j] = MAXint;
    			}
    		}
    		cout << "各边的顶点信息和权值:";
    		for (int k = 0; k < G.arcnum; k++)//构造邻接矩阵
    		{
    			string v1, v2;
    			int w;//边的两个顶点以及权值
    			cin >> v1 >> v2 >> w;
    			int i = Locate(G, v1);//找到点的位置
    			int j = Locate(G, v2);
    			G.arcs[i][j] = w;//赋予权值
    			G.arcs[j][i] = G.arcs[i][j];
    		}
    		return OK;
    	}
    	//创建邻接矩阵
    	
    	//创建邻接表
    	int CreateUDG(ALGraph& G)
    	{
    		cout << "请输入图的顶点数和边数:";
    		cin >> G.vexnum >> G.arcnum;//输入顶点数和边数
    		cout << "请输入各个顶点的信息:";
    		for (int i = 0; i < G.vexnum; i++)//初始化顶点信息
    		{
    			cin >> G.vertices[i].data;//输入顶点的信息
    			G.vertices[i].firstarc = NULL;//firstarc置空
    		}
    		cout << "请输入各边的顶点信息和权值:";
    		for (int k = 0; k < G.arcnum; k++)
    		{
    			string v1, v2;
    			int weight;//权值
    			cin >> v1 >> v2 >> weight;//输入一条边依附的两个顶点
    			int i = Locate(G, v1);
    			int j = Locate(G, v2);
    			ArcNode* p1 = new ArcNode;
    			p1->info = weight;
    			p1->adjvex = j;
    			p1->nextarc = G.vertices[i].firstarc;
    			G.vertices[i].firstarc = p1;
    			ArcNode* p2 = new ArcNode;
    			p2->info = weight;
    			p2->adjvex = i;
    			p2->nextarc = G.vertices[j].firstarc;
    			G.vertices[j].firstarc = p2;
    		}
    		return OK;
    	}
    	//创建邻接表
    	
    	//找到权值最小的边
    	int Min(closedge s,int len)
    	{
    		int min = MAXint;
    		int k = -1;
    		for (int i = 0; i < len; i++)
    		{
    			if (s[i].lowcost < min && s[i].lowcost != 0)
    			{
    				min = s[i].lowcost;
    				k = i;
    			}
    		}
    		return k;
    	}
    	//找到权值最小的边
    	
    	//prim最小生成树算法
    	void MiniSpanTree_Prim(AMGraph G, string u)
    	{
    		closedge close;
    		int k = Locate(G, u);//k为顶点u的下标
    		for (int i = 0; i < G.vexnum; i++)//对V-U的每一个顶点vj,初始化close;
    		{
    			if (k != i)
    			{
    				close[i] = { u,G.arcs[k][i] };
    			}
    		}
    		close[k].lowcost = 0;//初始化U,此时U中只有u一个顶点
    		for (int i = 1; i < G.vexnum; i++)
    		{
    			k = Min(close,G.vexnum);//找到与u权值最小的边
    			string u0 = close[k].adjvex;//最小边的一个顶点
    			string v0 = G.vexs[k];//最小边的另一个顶点
    			cout << u0 <<"-"<< v0 << endl;//输出最小边
    			close[k].lowcost = 0;//把此顶点并入U集
    			for (int i = 0; i < G.vexnum; i++)//新节点并入U后重新选择最小边
    			{
    				if (G.arcs[k][i] < close[i].lowcost)
    				{
    					close[i] = {G.vexs[k],G.arcs[k][i]};
    				}
    			}
    		}
    	}
    	//prim最小生成树算法
    	
    	//prim最小生成树算法
    	void MiniSpanTree_Prim(ALGraph G, string u)
    	{
    		closedge close;
    		int k = Locate(G, u);//k为顶点u的下标
    		for (int i = 0; i < G.vexnum; i++)
    		{
    			close[i] = { u,MAXint };
    		}
    		ArcNode* p = new ArcNode;
    		p = G.vertices[k].firstarc;
    		while (p)
    		{
    			close[p->adjvex] = { u,p->info };
    			p = p->nextarc;
    		}
    		close[k].lowcost = 0;//初始化U,此时U中只有u一个顶点
    		for (int i = 1; i < G.vexnum; i++)
    		{
    			k = Min(close, G.vexnum);//找到与u权值最小的边
    			string u0 = close[k].adjvex;//最小边的一个顶点
    			string v0 = G.vertices[k].data;//最小边的另一个顶点
    			cout << u0 << "-" << v0 << endl;//输出最小边
    			close[k].lowcost = 0;//把此顶点并入U集
    			ArcNode* arc = G.vertices[k].firstarc;
    			while (arc)
    			{
    				if (arc->info < close[arc->adjvex].lowcost)
    				{
    					close[arc->adjvex] = {G.vertices[k].data,arc->info};
    				}
    				arc = arc->nextarc;
    			}
    		}
    	}
    	//prim最小生成树算法
    	
    	/*v1 v2 v3 v4 v5 v6
    	v1 v2 6 v1 v3 1 v1 v4 5 v3 v2 5 v3 v4 5 v3 v5 6 v3 v6 4 v2 v5 3 v5 v6 6 v4 v6 2
    	v1*/
    	
    	int main()
    	{
    		ALGraph G;
    		CreateUDG(G);
    		cout << "您要构造的最小生成树的起点:";
    		string v;
    		cin >> v;
    		MiniSpanTree_Prim(G, v);
    		return 0;
    }
    
    展开全文
  • ,Kruskal 算法通过寻找边最优的方式来构造最小生成树,本篇图文介绍如何利用 C# 实现 Prim 最小生成树算法Prim 算法通过寻找顶点最优的方式来构造最小生成树。 在继续介绍 Prim 算法之前,我整理了以前发布的有关...

    背景

    我们上一篇图文介绍了 如何利用 C# 实现 Kruskal 最小生成树算法?Kruskal 算法通过寻找边最优的方式来构造最小生成树,本篇图文介绍如何利用 C# 实现 Prim 最小生成树算法,Prim 算法通过寻找顶点最优的方式来构造最小生成树。

    在继续介绍 Prim 算法之前,我整理了以前发布的有关数据结构与算法的图文,建个索引以方便大家的复习啊。

    线性结构

    树形结构

    排序相关

    搜索相关

    LeetCode 实战


    技术分析

    Prim 算法:

    Prim算法

    例子:

    例子

    该例子演示了一个含有6个结点,10条边的联通网,通过 Prim 算法从 V0 点开始逐步演化为含有6个结点,5条边的连通子网的过程,即构造最小生成树的过程。


    代码实现

    我们利用邻接表的方式来存储图的结构。有关于边表 EdgeNode、顶点表 VertexNode 和图 AdGraph 的结构,参见 如何利用 C# 实现 Kruskal 最小生成树算法? 中的 Step1、Step2 和 Step3。

    上面例子,在内存中的邻接表结构为:

    邻接表

    最小生成树的节点结构 SpanTreeNode,参见 如何利用 C# 实现 Kruskal 最小生成树算法? 中的 Step4。

    有了以上的基础,我们就可以写 Prim 算法了。

    public SpanTreeNode[] MiniSpanTree(string vName)
    {
        int i = GetIndex(vName);
        if (i == -1)
            return null;
    
        SpanTreeNode[] spanTree = new SpanTreeNode[VertexCount];
        
        //首先加入根节点
        spanTree[0] = new SpanTreeNode(_vertexList[i].VertexName,
            "NULL", 0.0);
    
        //U中结点到各结点最小权值那个结点在VertexList中的索引号
        int[] vertexIndex = new int[VertexCount];
        
        //U中结点到各个结点的最小权值
        double[] lowCost = new double[VertexCount];
        
        for (int j = 0; j < VertexCount; j++)
        {
            lowCost[j] = double.MaxValue;
            vertexIndex[j] = i;
        }
    
        EdgeNode p1 = _vertexList[i].FirstNode;
        while (p1 != null)
        {
            lowCost[p1.Index] = p1.Weight;
            p1 = p1.Next;
        }
        vertexIndex[i] = -1;
    
        for (int count = 1; count < VertexCount; count++)
        {
            double min = double.MaxValue;
            int v = i;
            for (int k = 0; k < VertexCount; k++)
            {
                if (vertexIndex[k] != -1 && lowCost[k] < min)
                {
                    min = lowCost[k];
                    v = k;
                }
            }
            spanTree[count] = new SpanTreeNode(_vertexList[v].VertexName,
                _vertexList[vertexIndex[v]].VertexName, min);
            vertexIndex[v] = -1;
    
            EdgeNode p2 = _vertexList[v].FirstNode;
            while (p2 != null)
            {
                if (vertexIndex[p2.Index] != -1 &&
                    p2.Weight < lowCost[p2.Index])
                {
                    lowCost[p2.Index] = p2.Weight;
                    vertexIndex[p2.Index] = v;
                }
                p2 = p2.Next;
            }
        }
        return spanTree;
    }
    

    总结

    到此为止代码部分就全部介绍完了,我们来看一下上面例子的应用。

    利用邻接表存储图的结构。

    static AdGraph CreateGraph()
    {
        AdGraph result = new AdGraph(6);
        result[0] = "V0";
        result[1] = "V1";
        result[2] = "V2";
        result[3] = "V3";
        result[4] = "V4";
        result[5] = "V5";
        result.AddEdge("V0", "V1", 6);
        result.AddEdge("V0", "V2", 1);
        result.AddEdge("V0", "V3", 5);
        result.AddEdge("V1", "V0", 6);
        result.AddEdge("V1", "V2", 5);
        result.AddEdge("V1", "V4", 3);
        result.AddEdge("V2", "V0", 1);
        result.AddEdge("V2", "V1", 5);
        result.AddEdge("V2", "V3", 7);
        result.AddEdge("V2", "V4", 5);
        result.AddEdge("V2", "V5", 4);
        result.AddEdge("V3", "V0", 5);
        result.AddEdge("V3", "V2", 7);
        result.AddEdge("V3", "V5", 2);
        result.AddEdge("V4", "V1", 3);
        result.AddEdge("V4", "V2", 5);
        result.AddEdge("V4", "V5", 6);
        result.AddEdge("V5", "V2", 4);
        result.AddEdge("V5", "V3", 2);
        result.AddEdge("V5", "V4", 6);
        return result;
    }
    

    从 V2 点开始构建最小生成树。

    static void Main(string[] args)
    {
        AdGraph alg = CreateGraph();
        SpanTreeNode[] tree = alg.MiniSpanTree("V2");
        double sum = 0;
        for (int i = 0; i < tree.Length; i++)
        {
            string str = "(" + tree[i].ParentName + ","
                            + tree[i].SelfName + ") Weight:"
                            + tree[i].Weight;
            Console.WriteLine(str);
            sum += tree[i].Weight;
        }
        Console.WriteLine(sum);
    }
    

    结果如下:

    输出结果

    我们再通过一个例子来演示如何应用:

    地图

    上面是一幅纽约市附近的地图,对应的数据存储在 graph.txt 文件中。

    数据

    读入该文件,构造好 AdGraph 结构后,调用我们写好的 Prim 算法,得到的结果如下:

    输出结果

    是不是很有趣,今天就到这里吧!马上要放假了,我们的招新活动也即将开启,希望大家关注呦!

    See You!


    相关图文

    展开全文
  • 最小生成树-Prim算法

    2017-03-04 22:46:32
    题目链接...我们采用Prim算法构造最小生成树。 这道题目中首先利用一个数组来表示节点之间的距离,其中同一节点用无穷大来进行表示。然后调用Prim算法来构造最小生成树

    题目链接http://acm.whu.edu.cn/learn/problem/detail?problem_id=1038

    这是woj里面的一道题目,已知了所有点的坐标,求一条长l的线是否可以将所有的点连接起来。
    其主要思路就是采用最小生成树。我们采用Prim算法构造最小生成树。
    这道题目中首先利用一个数组来表示节点之间的距离,其中同一节点用无穷大来进行表示。然后调用Prim算法来构造最小生成树

    下面看具体代码以及注释,来了解Prim算法

    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #define MAXV 103
    #define MAXCOST 0x7fffffff
    float quan[MAXV][MAXV];  //存放节点之间的权值
    struct{
        int x;
        int y;
    }jiedian[MAXV];  //存放每个节点的横纵坐标 
    
    float Prim(float graph[][MAXV],int n){
        float lowcost[MAXV];   //表示以i为终点的权值。当lowcost[i]=0时,表示已经加入最小生成树
        int mst[MAXV];   //存放lowcost[i]对应的节点
        //首先假设第0个节点已经处于最小生成树里面
        lowcost[0]=0;
        mst[0]=0;
        //则lowcost里面存放从第一个节点到最后一个节点到第0个节点的距离
        for(int i=1;i<n;i++){
            lowcost[i]=quan[0][i];
            mst[i]=1;
        } 
        float sum=0;
        for(int i=1;i<n;i++){
            //从第一个节点开始遍历
            float min=MAXCOST;
            int minid=0;
            for(int j=1;j<n;j++){ //求与该节点最近的点 
                if(lowcost[j]<min && lowcost[i]!=0){
                    min=lowcost[i];
                    mst[i]=j;       
                } 
            }
            sum+=min;
            //更新lowcost
            lowcost[minid]=0;
            for(int j=1;j<n;j++){
                if(lowcost[j]>graph[minid][j]){
                    lowcost[j]=graph[minid][j];
                    mst[j]=minid;
                }
            } 
    
        }
        return sum;
    
    } 
    int main(){
        int n,l;
        while(scanf("%d",&n) && n!=0){
            scanf("%d",&l);
            for(int i=0;i<n;i++){
                scanf("%d %d",&jiedian[i].x,&jiedian[i].y);
            }
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                float xx=pow((float)(jiedian[i].x-jiedian[j].x),2)+pow((float)(jiedian[i].y-jiedian[j].y),2); //计算节点之间距离 
                quan[i][j]=sqrt(xx);
                quan[i][i]=MAXCOST;   //相同节点之间距离为无穷大 
                }
            }
            float cost=Prim(quan,n);   //求出最小生成树 
            if(cost<=l) printf("Success!\n");
            else printf("Poor magicpig!\n");
        }
        return 0;
    } 

    总的来说Prim算法主要用到三个数组,其中有一个表示节点直接的权值,一个数组表示目前最小生成树到未加入节点的最短距离,另外一个数组对应这些未加入数组离已加入的节点最近的节点标记。
    Prim算法的流程主要是初始化,判断最近节点,更新剩余节点三个步骤一般来说,代码片段中的Prim算法可以直接进行调用。

    之后会不断补充有关最小生成树的相关OJ题目来进一步巩固最小生成树

    展开全文
  • ,Kruskal 算法通过寻找边最优的方式来构造最小生成树,本篇图文介绍如何利用 C# 实现 Prim 最小生成树算法Prim 算法通过寻找顶点最优的方式来构造最小生成树。在继续介绍 Prim 算法之前,我整理了以前发布的有关...
  • 最小生成树prim算法(贪心)

    千次阅读 2014-10-09 19:27:49
    一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树的n-1条边。所谓的最小成本,就是n个顶点,用n-1条边把一个...Prim算法也是利用贪心算法来解决最小生成树最小生成树MST性
  • 最小生成树prim算法和kruskal算法

    千次阅读 2015-05-14 18:57:03
    一个连通图的生成树是图的极小连通子图。它包含图中的所有顶点,并且只含尽可能少的边。若砍去它的一条边,就会使生成树变成非连通图;若给它增加一条边,则会形成一条回路。...其中多数算法利用最小生成树的下列一种
  • prim算法利用最小生产树的MST性质来一点一点的构造最小生成树的。 假设N={V,{E}}是一个带权值的无向图(即为一个网),U是顶点集V的一个非空子集,  若(u,v)是一个具有最小权值的边,其中u属于U,v属于V-U,则必然...
  • 最小生成树prim算法

    2015-12-06 17:12:53
    利用 普里姆算法 要解决如上问题,首先我们构造图的邻接矩阵。如下图所示: 注意:实际中我们用65535来代表无穷大。 关于普里姆算法以及讲解如下图:
  • [本文是自己学习所做笔记。欢迎转载。... 算法描写叙述  假设连通图是一个网,则称该网中全部...利用Prim算法构造最小生成树方法思想:  如果G=(V,E)是一个具有n个顶点的连通网,顶点集V={v1,v2,...,vn}.设所求...
  • 主要为大家详细介绍了C语言实现最小生成树构造算法,利用Prim算法或kruskal算法求解,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 算法最小生成树

    2018-05-22 19:31:02
    1. 问题描述:利用贪心算法设计策略构造一个无向连通带权图的最小生成树最小生成树:设G=(V,E)是无向连通带权图,即一个网络。E中每条边(v,w)的权为c[v][w]。包含G所有顶点的树且该生成树各边权的总和最小...
  • 构造最小生成树有许多算法,但大多数算法利用最小生成树的下列性质: 假设G=(V,E)是一个带权连通无向图,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边,其中u€U,v€V-U,则B存在一棵包含边(u,v)...
  • 最小生成树算法

    2015-07-24 16:50:06
    定义由带权的连通图生成的数的各边加起来称为生成树...下面介绍两种用于构造最小生成树的算法,其中第一种算法称为Prim算法,第二种算法称为Kruskal算法。\qquadPrim算法中,每次循环选择一个顶点(和一条边)加入到最
  • Prim算法利用了MST的性质:假设N= (V,E)是一个连通图,U是顶点集V的一个非空子集,若(u,v)是一条最小权值的边,其中u属于U,v属于V-U,则必存在一颗包含(u,v)的最小生成树。 Kruskal算法的实现 克鲁斯卡尔算法...
  • 贪心-最小生成树

    2016-10-16 14:23:38
    这里介绍的构造最小生成树Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方式不同,它们都利用了下面的最小生成树性质:  设G=(V,E)是连通带权图,U是V的真子集。...
  • 最小生成树

    2021-01-29 03:23:52
    构造最小生成树有很多算法,但是都是利用最小生成树的同一种性质:MST性质(假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集,如果(u,v)是一条具有最小权值的边,其中u属于U,v属于V-U,则必定存在一颗...
  • 构造最小生成树算法中,大多利用了最小生成树的一个简称MST的性质:假设N=(V,E)是一个联通网,U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边,其中u属于U,v属于V-U,则必存在一棵包含(u,v)的最小...
  • 我们把构造连通网的最小...普里姆(Prim算法对下图利用普里姆算法求其最小生成树。步骤如下:代码如下:#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #defin
  • 其中多数算法利用最小生成树的下列一种简称为MST的性质:假设N=(V,{E}) 是一个连通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值边的边,其中u属于U,v属于V-U,则必存在一颗包含(u,v)的最小生成...
  • 最小生成树在城市建设道路中...本文中,解决该问题应用的是图论中的最小生成树中的prim(普里姆)算法。 本文通过构造连通图进而解决问题,图中的节点是海平面上升后所有幸存的城市ID(为简单起见,城市从1到n),...
  • 关于图的几个算法

    2012-09-25 11:24:05
    在数据结构中,会涉及到图的几个算法: 最小生成树,拓扑排序,关键路径,从某点到其余点的最短距离。...在构造最小生成树时,利用了其性质:  假设 N=(V, {E})是一个连通网, U是顶点集V的一个非
  • 有关图的几个经典算法

    千次阅读 2018-01-06 16:09:02
    ·在构造最小生成树过程中,取最小堆的根结点,若该边两个顶点不属于同一个连通分量,则取该边,否则拿掉该根结点继续然后接 着取最小堆的根结点进行判断。 2、prim算法 · 从连通网络 N = { V, E }中的某一顶点 u...
  • 图的应用 一、最小生成树 针对带权值的无向图,即网结构,使用n-1条边连接n个顶点,...输入以上的邻接矩阵,利用prim算法生成最小数 const int MAXVEX = 9; //顶点最大数,设为9 const int INFINITY = 65535; /...
  • 例如:在求最小生成树Prim 算法中,挑选的顶点是候选边中权值最小的边的一个端点。在 Kruskal 算法中,每次选取权值最小的边加入集合。在构造霍夫曼树的过程中也是每次选择最小权值的节点构.
  • 3.2 生成最小生成树prim算法 . 3.3 单源最短路径问题 3.4 二路归并问题 3.5 用贪心法解决最小圈基问题 3.6 用贪心法解决2终端一对多问题 3.7 用贪心法解决1螺旋多边形最小合作 警卫问题 3.8 实验结果 3.9...
  • /*在这个代码里面,我主要实现的利用邻接表来存储图论,定义了一个类,里面有一个私有的node **a;...主要实现算法:深度宽度遍历,拓扑排序,单源最短路径dijkstra,最小生成树prim)等等#include #include using na

空空如也

空空如也

1 2
收藏数 40
精华内容 16
关键字:

利用prim算法构造最小生成树