精华内容
下载资源
问答
  • 用字符文件提供数据建立连通带权网络邻接矩阵存储¬¬结构。编写程序,用Prim算法求一棵最小生成树。要求输出最小生成树的各条边(用顶点无序偶表示)、各条边上的权值、最小生成树所有边上的权值之和。
  • 用文件存储无向图,然后分别使用Kruska和Prim算法求最小生成树。里面是完整的VS的项目,有详细注释,方便理解跟使用。
  • Prim算法计算最小生成树(无向图&邻接矩阵)——C语言实现。
  • Prim算法能够在带权的图中搜索出最小生成树,这也是各大ACM和面试及考研题目中的热点,下面我们就来详细看一下Prim(普里姆)算法求最小生成树的思想及C语言实例讲解
  • Prim算法构造一颗最小生成树 (2) 实验原理: ①从网中任一顶点开始,先把该顶点包含在生成树中,此时生成树只有 一个顶点。 ②找出一个端点在生成树中另一端点在生成树外的所有边,并把权值最 小的边连到同它所...
  • prim算法求最小生成树过程解析

    千次阅读 2020-05-30 12:17:40
    文章目录一、原理二、所需数据结构三、prim代码实现(含思路解析)四、解题完整代码:4.1 题目4.2 AC代码 一、原理 我直接贴我们课件的截图吧: 二、所需数据结构 总结起来就是一个结构体+一个二维数组+3个一维数组...

    一、原理

    我直接贴我们课件的截图吧:
    在这里插入图片描述

    二、所需数据结构

    总结起来就是一个结构体+一个二维数组+3个一维数组
    1.需要一个结构体来存储边的信息,包括边的id和权重:

    typedef struct line{
        int weight;
        int id;
    }line;
    

    2.用二维数组来存储这个图:

    line G[maxver][maxver];
    

    3.一个edges[maxver]数组,存放最小生成树的某个顶点,每个(i,edges[i])代表暂时不在最小生成树中的顶点i到最小生成树的某个顶点的最短弧:

    int edges[maxver];
    

    4.一个minweight[maxver]数组,存放弧的权重,每个minweight[i]代表顶点i到最小生成树的弧的长度,如果取0表示顶点i已经在最小生成树里了

    int minweight[maxver];
    

    5.一个min_tree[maxver]数组,存放最小生成树的弧的id号

    int min_tree[maxver];//存放最小生成树的弧的序号
    

    三、prim代码实现(含思路解析)

    void prim(){
        //1.初始化edges数组和minweight数组
        int i,j,k;
        for(i=1;i<n;i++){
            minweight[i]=G[i][0].weight;
            edges[i]=0;
        }
        //2.把起点加入到最小生成树中
        minweight[0]=0;
        //3.然后开始找弧,需要经过n-1次查找
        for(i=1;i<n;i++){
            //3.1先从那些不在最小生成树里面的顶点开始,找它们到最小生成树之间最短的弧
            int min=inf;
            for(j=0,k=0;j<n;j++){
                if(minweight[j]!=0&&minweight[j]<min){
                    min=minweight[j];
                    k=j;
                }
            }
            //3.2完成上述循环后,就找到了第一条最短弧,先把k加入到最小生成树中
            minweight[k]=0;
            min_tree[i]=G[k][edges[k]].id;
            sum_weight+=G[k][edges[k]].weight;
            //3.3像初始化edges数组和minweight数组那样,更新这两个数组
            for(j=0;j<n;j++){
                if(minweight[j]!=0&&G[j][k].weight<minweight[j]){
                    minweight[j]=G[j][k].weight;
                    edges[j]=k;
                }
            }
        }
    }
    

    四、解题完整代码:

    4.1 题目

    【问题描述】

    学校的主要办公科研楼有新主楼、逸夫楼、如心楼、办公楼、图书馆、主楼、一号楼等等;。北航网络中心计划要给相关建筑物间铺设光缆进行网络连通,请给出用料最少的铺设方案。

    编写程序输入一个办公区域分布图及建筑物之间的距离,计算出用料最少的铺设方案(只有一组最优解,不用考虑多组解)。要求采用Prim或Kruskal算法实现。

    <o:p></o:p>

    【输入形式】

    办公区域分布图的顶点(即建筑物)按照自然数(012n-1)进行编号,从标准输入中首先输入两个正整数,分别表示线路图的顶点的数目和边的数目,然后在接下的行中输入每条边的信息,每条边占一行,具体形式如下:

    <n> <e>

    <id> <vi> <vj> <weight><o:p></o:p>

    即顶点vivj之间边的权重是weight,边的编号是id

    【输出形式】

    输出铺设光缆的最小用料数,然后另起一行输出需要铺设的边的id,并且输出的id值按照升序输出。

    【样例输入】

     6 10

    1 0 1 600

    2 0 2 100

    3 0 3 500

    4 1 2 500

    5 2 3 500

    6 1 4 300

    7 2 4 600

    8 2 5 400

    9 3 5 200

    10 4 5 600

    【样例输出】

    1500

    2 4 6 8 9

    4.2 AC代码

    #include <stdio.h>
    #include <malloc.h>
    #define inf 66535
    #define maxver 1000
    
    int n,e;
    int id,vi,vj,weight;
    
    typedef struct line{
        int weight;
        int id;
    }line;
    
    line G[maxver][maxver];
    int edges[maxver];
    int minweight[maxver];
    int min_tree[maxver];//存放最小生成树的弧的序号
    int sum_weight;
    
    void fill(int id,int vi,int vj,int weight){
        G[vi][vj].weight=weight;
        G[vi][vj].id=id;
        G[vj][vi].weight=weight;
        G[vj][vi].id=id;
    }
    
    void init_graph(int n){
        int i,j;
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                G[i][j].weight=inf;
            }
        }
    }
    
    void prim(){
        //1.初始化edges数组和minweight数组
        int i,j,k;
        for(i=1;i<n;i++){
            minweight[i]=G[i][0].weight;
            edges[i]=0;
        }
        //2.把起点加入到最小生成树中
        minweight[0]=0;
        //3.然后开始找弧,需要经过n-1次查找
        for(i=1;i<n;i++){
            //3.1先从那些不在最小生成树里面的顶点开始,找它们到最小生成树之间最短的弧
            int min=inf;
            for(j=0,k=0;j<n;j++){
                if(minweight[j]!=0&&minweight[j]<min){
                    min=minweight[j];
                    k=j;
                }
            }
            //3.2完成上述循环后,就找到了第一条最短弧,先把k加入到最小生成树中
            minweight[k]=0;
            min_tree[i]=G[k][edges[k]].id;
            sum_weight+=G[k][edges[k]].weight;
            //3.3像初始化edges数组和minweight数组那样,更新这两个数组
            for(j=0;j<n;j++){
                if(minweight[j]!=0&&G[j][k].weight<minweight[j]){
                    minweight[j]=G[j][k].weight;
                    edges[j]=k;
                }
            }
        }
    }
    
    //冒泡排序,让最小生成树的边的序号升序输出
    void bubble(){
        int i,j,tmp;
        for(i=n-1;i>1;i--){
            for(j=1;j<i;j++){
                if(min_tree[j]>min_tree[j+1]){
                    tmp=min_tree[j];
                    min_tree[j]=min_tree[j+1];
                    min_tree[j+1]=tmp;
                }
            }
        }
    }
    
    int main(){
        scanf("%d%d",&n,&e);
        int i=0;
        init_graph(n);
        while(e--){
            scanf("%d%d%d%d",&id,&vi,&vj,&weight);
            fill(id,vi,vj,weight);
        }
        prim();
        printf("%d\n",sum_weight);
        bubble();
        for(i=1;i<n;i++){
            printf("%d ",min_tree[i]);
        }
        puts("");
    }
    
    展开全文
  • Prim算法求最小生成树

    万次阅读 多人点赞 2019-01-18 20:54:53
    无向网的最小生成树的算法有两种:Prim和Kruskal,它们都是利用最小生成树的MST性质得到的。我们先来介绍Prim算法,Kruskal我们后续介绍。 Prim算法思想: 逐渐长成一棵最小生成树。假设G=(V,E)是连通无向网,T...

    求无向网的最小生成树的算法有两种:Prim和Kruskal,它们都是利用最小生成树的MST性质得到的。我们先来介绍Prim算法,Kruskal我们后续介绍。

    Prim算法思想:
    逐渐长成一棵最小生成树。假设G=(V,E)是连通无向网,T=(V,TE)是求得的G的最小生成树中边的集合,U是求得的G的最小生成树所含的顶点集。初态时,任取一个顶点u加入U,使得U={u},TE=Ø。重复下述操作:找出U和V-U之间的一条最小权的边(u,v),将v并入U,即U=U∪{v},边(u,v)并入集合TE,即TE=TE∪{(u,v)}。直到V=U为止。最后得到的T=(V,TE)就是G的一棵最小生成树。也就是说,用Prim求最小生成树是从一个顶点开始,每次加入一条最小权的边和对应的顶点,逐渐扩张生成的。
    我们举一个例子?来模仿一下Prim的操作流程:
    (1)初始化U={v0},TE=Ø
    在这里插入图片描述
    (2)U={v0,v2},TE={(v0,v2)}
    在这里插入图片描述
    (3)U={v0,v2,v5},TE={(v0,v2),(v2,v5)}
    在这里插入图片描述
    (4)U={v0,v2,v5,v3},TE={(v0,v2),(v2,v5),(v5,v3)}
    在这里插入图片描述
    (5)U={v0,v2,v5,v3,v1},TE={(v0,v2),(v2,v5),(v5,v3),(v2,v1)}
    在这里插入图片描述
    (6)U={v0,v2,v5,v3,v1,v4},TE={(v0,v2),(v2,v5),(v5,v3),(v2,v1),(v2,v4)}
    在这里插入图片描述
    代码实现

    #include<iostream>
    #include<cstring>
    #include<string> 
    using namespace std;
    const int MaxSize=100;
    const int MAX=9999;
    
    class MGraph
    {
    	string vertex[MaxSize];   //图的顶点信息 
    	int adj[MaxSize][MaxSize];    //图的邻接矩阵 
    	int vertexNum,edgeNum;
    public:
    	MGraph(int n);
    	int W(int i,int j);
    	void InsertEdge(int i,int j,int p);
    	int VexNum()
    	{
    		return vertexNum;
    	} 
    	friend void Prim(MGraph &g,int u0);
    };
    
    MGraph::MGraph(int n)
    {
    	vertexNum=n;
    	edgeNum=0;
    	memset(adj,0,sizeof(adj));   //将邻接矩阵所有元素赋为0 
    }
    
    
    void MGraph::InsertEdge(int i,int j,int p)   //插入顶点i、j依附的边以及该边的权值 
    {
    	adj[i][j]=adj[j][i]=p;
    	edgeNum++;
    }
    
    int MGraph::W(int i,int j)
    {
    	return adj[i][j];
    }
    
    void Prim(MGraph &g,int u0)
    {
    	int k;
    	int n=g.VexNum();
    	struct node
    	{
    		int adjvex;
    		int lowcost;
    	}closedge[MaxSize];
    	closedge[u0].adjvex=u0;
    	closedge[u0].lowcost=0;
    	for(int v=0;v<n;v++)
    	{
    		if(v!=u0)
    		{
    			closedge[v].adjvex=u0;
    			closedge[v].lowcost=g.W(u0,v);
    		}	
    	}
    	closedge[u0].lowcost=0;
    	for(int i=0;i<=n-2;i++)
    	{
    		k=0;
    		int minw=MAX;
    		for(int v=0;v<=n-1;v++)
    		{
    			if(closedge[v].lowcost>0&&closedge[v].lowcost<minw)
    			{
    				k=v;
    				minw=closedge[v].lowcost;
    			}
    		}
    		cout<<"("<<closedge[k].adjvex<<","<<k<<")"<<":"<<minw<<" "<<endl;
    		closedge[k].lowcost=0;   //顶点k并入U集 
    		for(int v=0;v<=n-1;v++)
    		{
    			if(closedge[v].lowcost!=0&&g.W(k,v)<closedge[v].lowcost)
    			{
    				closedge[v].lowcost=g.W(k,v);
    				closedge[v].adjvex=k;
    			}
    		}
    	}
    }
    
    int main()
    {
    	struct Edge
    	{
    		int from,end,power;
    	};  
    	
    	int n=6;   //6个顶点 
    	int e=10;
    	Edge b[]={{0,1,6},{0,2,1},{0,3,5},{1,2,5},{1,4,3},{2,3,5},{2,4,6},{2,5,4},{3,5,2},{4,5,6}};
    	MGraph m(n);
    	for(int k=0;k<e;k++)m.InsertEdge(b[k].from,b[k].end,b[k].power);  //插入所有边,将邻接矩阵赋值 
    	Prim(m,0);
    	return 0; 
    }
    
    展开全文
  • 题目链接 模板: 模板来自AcWing int n; // n表示点数 int g[N][N]; // 邻接矩阵,存储所有边 int dist[N];...// 如果图不连通,则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和 ...

    题目链接

    模板:
    模板来自AcWing

    int n;      // n表示点数
    int g[N][N];        // 邻接矩阵,存储所有边
    int dist[N];        // 存储其他点到当前最小生成树的距离
    bool st[N];     // 存储每个点是否已经在生成树中
    
    
    // 如果图不连通,则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
    int prim()
    {
        memset(dist, 0x3f, sizeof dist);
    
        int res = 0;
        for (int i = 0; i < n; i ++ )
        {
            int t = -1;
            for (int j = 1; j <= n; j ++ )
                if (!st[j] && (t == -1 || dist[t] > dist[j]))
                    t = j;
    
            if (i && dist[t] == INF) return INF;
    
            if (i) res += dist[t];
            st[t] = true;
    
            for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
        }
    
        return res;
    }
    

    给定一个n个点m条边的无向图,图中可能存在重边和自环,边权可能为负数。

    求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。

    给定一张边带权的无向图G=(V, E),其中V表示图中点的集合,E表示图中边的集合,n=|V|,m=|E|。

    由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树,其中边的权值之和最小的生成树被称为无向图G的最小生成树。

    输入格式
    第一行包含两个整数n和m。

    接下来m行,每行包含三个整数u,v,w,表示点u和点v之间存在一条权值为w的边。

    输出格式
    共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。

    数据范围
    1≤n≤500,
    1≤m≤105,
    图中涉及边的边权的绝对值均不超过10000。

    输入样例:
    4 5
    1 2 1
    1 3 2
    1 4 3
    2 3 2
    3 4 4
    输出样例:
    6

    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int N=510,INF=0x3f3f3f3f;
    int n,m;
    int g[N][N];
    int dist[N];
    bool st[N];
    
    int prim(){
        memset(dist,INF,sizeof(dist));
        int res=0;
        for(int i=0;i<n;i++){
            int t=-1;
            for(int j=1;j<=n;j++)
                if(!st[j]&&(t==-1||dist[t]>dist[j]))
                    t=j;
            if(i&&dist[t]==INF)return INF;
            
            if(i) res+=dist[t];
            st[t]=true;
            for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
        }
        return res;
    }
    
    int main(){
        cin>>n>>m;
        memset(g,INF,sizeof(g));
        while(m--){
            int a,b,c;
            cin>>a>>b>>c;
            g[a][b]=g[b][a]=min(g[a][b],c);
        }
        int t=prim();
        if(t==INF) cout<<"impossible"<<endl;
        else cout<<t<<endl;
        return 0;
    }
    
    展开全文
  • 数据结构教程实验--用Prim算法构造最小生成树
  • 写的最小堆模板套一个边结点老是报错,解决方法![图片说明](https://img-ask.csdn.net/upload/201605/27/1464343934_753216.png)![![图片说明](https://img-ask.csdn.net/upload/201605/27/1464324499_272714.png)...
  • 具体讲解请参考最小生成树算法,大佬写的非常易懂 参考资料:大话数据结构 以下是java代码实现 创建一个关于图的类 import java.util.Scanner; /** 1. @author Aaron 2. @date 2020/3/29 - 17:48 */ public class ...
  • 求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。 给定一张边带权的无向图G=(V,E),其中V表示图中点的集合,E表示图中边的集合,n=|V|,m=|E|。 由V中的全部n个顶点和E中n−1条边构成的无向连通...

    【题目描述】
    给定一个 n n n个点 m m m条边的无向图,图中可能存在重边和自环,边权可能为负数
    求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible
    给定一张边带权的无向图 G = ( V , E ) G=(V,E) G=(V,E),其中 V V V表示图中点的集合, E E E表示图中边的集合, n = ∣ V ∣ , m = ∣ E ∣ n=|V|,m=|E| n=Vm=E
    V V V中的全部 n n n个顶点和 E E E n − 1 n−1 n1条边构成的无向连通子图被称为 G G G的一棵生成树,其中边的权值之和最小的生成树被称为无向图 G G G的最小生成树。

    【输入格式】
    第一行包含两个整数 n n n m m m
    接下来 m m m行,每行包含三个整数 u , v , w u,v,w u,v,w,表示点 u u u和点 v v v之间存在一条权值为 w w w的边。

    【输出格式】
    共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出impossible

    【数据范围】
    1 ≤ n ≤ 500 1≤n≤500 1n500
    1 ≤ m ≤ 1 0 5 1≤m≤10^5 1m105
    图中涉及边的边权的绝对值均不超过 10000 10000 10000

    【输入样例】

    4 5
    1 2 1
    1 3 2
    1 4 3
    2 3 2
    3 4 4
    

    【输出样例】

    6
    
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int INF = 0x3f3f3f3f;
    const int N = 510;
    int g[N][N];
    int vis[N], dis[N];//dis表示每个点到集合的最小值
    int n, m;
    
    int prim()
    {
        memset(dis, 0x3f, sizeof dis);
        int res = 0;
        for(int i = 0; i < n; i++)
        {
            int t = -1;
            for(int j = 1; j <= n; j++)
                if(!vis[j] && (t == -1 || dis[j] < dis[t]))
                    t = j;
            vis[t] = 1;
            if(i && dis[t] == INF) return INF;
            if(i) res += dis[t];//可能存在负的自环更新dis[t],因此需在更新前加入res
            for(int j = 1; j <= n; j++)
                dis[j] = min(dis[j], g[t][j]);
        }
        return res;
    }
    
    int main()
    {
        cin >> n >> m;
        memset(g, 0x3f, sizeof g);
        while(m--)
        {
            int a, b, c;
            cin >> a >> b >> c;
            g[a][b] = g[b][a] = min(g[a][b], c);
        }
        int ans = prim();
        ans == INF ? cout << "impossible\n" : cout << ans << endl;
        return 0;
    }
    
    展开全文
  • 数据结构最小生成树Prim算法

    千次阅读 多人点赞 2019-04-29 12:08:13
    最小生成树问题是实际生产生活中十分重要的一类问题。假设需要在n个城市之间建立通信联络网,则连通n个城市只需要n-1条线路。这时,自然需要考虑这样一个问题,即如何在最节省经费的前提下建立这个通信网。 可以用...
  • 本文介绍了最小生成树的定义,Prim算法的实现步骤,通过简单举例实现了C语言编程。1.什么是最小生成树算法?简言之,就是给定一个具有n个顶点的加权的无相连通图,用n-1条边连接这n个顶点,并且使得连接之后的所有边...
  • 最小生成树Prim,Kruskal)C++代码实现 (可运行,含测试用例,有输出,注释详细) 对于一个带权连通图,生成树不同,树中各边上权值总和也不同,权值总和最小的生成树则称为图的最小生成树
  • watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center...//最小生成树Prim算法//杨鑫#include #include #define n 6#define MaxNum 10000 /*...
  • 时间复杂度:O(n²) #include<iostream> #define n 6 #define INF 999 using namespace std;...void Prim(int arc[n][n],int w) { Element shortEdge[10]; // 存储后端最短边集,假设最多10个顶点.
  • 本题要求采用prim算法求最小生成树,输出其权值之和。 输入格式: 输入为顶点 顶点 权值,以 0 0 0表示结束 输出格式: 输出为最小生成树的权值大小 输入样例: 0 1 5 1 0 5 0 2 30 2 0 30 0 3 14 3 0 14 1 2 24...
  • prim算法图的最小生成树的一种算法,它是根据图中的节点来进行求解,具体思想大概如下: 首先,将图的所有节点(我们假定总共有n个节点)分成两个集合,V和U。其中,集合V保存的是我们已经访问过的节点,集合U...
  • 最小生成树的概念 在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边,而 w(u, v) 代表此的边权重,若存在 T 为 E 的子集(即)且为无循环图,使得的 w(T) 最小,则此 T 为 G 的最小生成树。...
  • win32控制台程序 vs2010以上编译运行通过 在main函数里定义图,然后调用2个封好的函数用2种不同的算法输出最小生成树 大连理工大学软件学院数据结构上机题
  • (1)、实验题目:给定一个地区的n 个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并得到的最小生成树的代价。 (2)、实验要求: 1、城市间的距离网采用的邻接矩阵表示,邻接矩阵的存储结构定义采用...
  • 最小生成树Prim算法  在保证图连通的情况下,去掉边数最多所得到的树叫做最小生成树。也就是说一个图,去掉一些边后,图仍是连接的,而这时图剩下的边数最少就是最小生成树,这时候图一定是树状结构的。可以用反证...
  • 在图论中,最小生成树也是一种常用算法,本文将从一些有趣的例子和来讲诉最小生成树prim算法和kruskal算法。中间也夹杂了马克思主义理论,!
  • 以合适方便的方式输入一个带权值的无向图,采用合适的存储结构存储该无向图。然后根据PRIM算法求该无向图的最小生成树并输出。 课程设计报告,附加完整代码 图形演示算法的步骤
  • 最小生成树(Minimum Spanning Tree, MST)是在一个给定的无向图G(V,E)中一棵树T,使得这棵树拥有图G中的所有顶点,且所有边都是来自图G中的边,并且满足整棵树的边权之和最小。 最小生成树的3个性质: (1)最小...
  • 使用Prim算法编写的最小生成树(C语言),为更好地学习数据结构
  • 实现构造最小生成树Prim算法
  • Prim算法 概念 ...最小生成树 Prim算法 */ #include <iostream> using namespace std; #define MaxVertexNum 10 struct Graph { int edgenum; int vertexnum; int edgeList[MaxVertexNum]
  • Prim算法求解最小生成树的Java实现

    千次阅读 2017-07-06 21:11:15
    上一篇既然提到了Krusal算法,这里就不得不说Prim算法了,这两个算法都是求解最小生成树的经典的贪婪算法。与Krusal算法不同的是,Prim算法在求解过程中始终保持临时结果是一颗联通的树。该算法的伪代码如下 //假设...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,733
精华内容 4,293
关键字:

数据结构prim算法求最小生成树

数据结构 订阅