精华内容
下载资源
问答
  • 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算法构造最小生成树
  • 用邻接矩阵的存储方式存储图 该图为无向图 用Prim算法构造最小生成树
  • 举一个实例,画出采用Prim算法构造最小生成树的过程。 2.解析 已知图V = {…} 我们构造一棵最小生成树T 第一步:随意选取起点 第二步:在前一步的基础上寻找最小权值 第三步:继续寻找最小权值,之后以此类推,直到...

    Prim算法
    普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。
    1.问题
    举一个实例,画出采用Prim算法构造最小生成树的过程。
    2.解析
    已知图V = {…} 我们构造一棵最小生成树T
    第一步:随意选取起点
    第二步:在前一步的基础上寻找最小权值
    第三步:继续寻找最小权值,之后以此类推,直到遍历完所有的节点。
    实例:
    图v如图
    在这里插入图片描述

    1.任意选择一个点
    这里我们选择A点
    从A点出发有两条路,一条通向B(权值为3),一条通向D(权值为4)
    我们选择权值较小的点B
    此时被选中的点:A B
    在这里插入图片描述

    2.找剩下中与以被选中点距离最短的点,判断该点是否被选中,未被选中则选上,直到遍历完所有点。
    最终结果如图所示
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述
    3.设计

    void prime(graph g,int s)//最小生成树
    {
        int dst[Len];
        int st;
        int minx;
        int sum=0;
        for (int i=0;i<g->nv;++i){
            dst[i]=g->data[s][i];
        }
        printf("V%c ",zd[s]);
        g->visited[s]=1;
    
        for (int i=1 ;i<g->nv;++i){
            minx=INF;
            for (int j=0;j<g->nv;++j){
                if(minx>dst[j]&&g->visited[j]==0){
                    st=j;
                    minx=dst[j];
                }
            }
            g->visited[st]=1;
            printf("V%c ",zd[st]);
            sum=sum+minx;
            for (int j=0;j<g->nv;++j){
                if(g->visited[j]==0&&dst[j]>g->data[st][j]){
                    dst[j]=g->data[st][j];
                }
    
            }
        }
        printf("\nthe lowest weight=%d\n",sum);
    }
    
    展开全文
  • prim算法构造最小生成树

    千次阅读 2020-05-22 12:12:32
    假设G=(V,E)是连通的,TE是G上最小生成树中边的集合。算法从U={u0}(u0∈V)、TE={}开始。重复执行下列操作: 在所有u∈U,v∈V-U的边(u,v)∈E中找一条权值最小的边(u0,v0)并入集合TE中,同时v0并入U,直到V=...

    假设G=(V,E)是连通的,TE是G上最小生成树中边的集合。算法从U={u0}(u0∈V)、TE={}开始。重复执行下列操作:
    在所有u∈U,v∈V-U的边(u,v)∈E中找一条权值最小的边(u0,v0)并入集合TE中,同时v0并入U,直到V=U为止。
    此时,TE中必有n-1条边,T=(V,TE)为G的最小生成树。
    例:
    在这里插入图片描述
    假设从v1开始,找到最小边v1 v3
    在这里插入图片描述
    在v1和v3的相邻边找到权重最小边v3-v6
    在这里插入图片描述
    在v1和v3和v6的相邻边找到权重最小边v6-v4
    在这里插入图片描述
    继续找找到v2

    在这里插入图片描述
    最后到达v5
    在这里插入图片描述

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    using namespace std;
    const int maxn=1005;
    const int INF=0x3f3f3f3f;
    int p[maxn]; //储存父节点
    int edge[maxn][maxn];//邻接矩阵
    int d[maxn]; //到生成树的最短距离
    int vis[maxn];//是否加入集合中
    int n,m;
    //初始化
    void init()
    {
        memset (vis,0,sizeof(vis));
        memset (p,-1,sizeof(p));
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                 i==j? edge[i][j]==0:edge[i][j]=INF;
    }
    void prim()
    {
        //以1作为根节点
        for (int i=1;i<=n;i++)
        {
            if(edge[1][i]!=INF)
                p[i]=1;
            d[i]=edge[1][i];
        }
        while (1)
        {
            int maxx=INF;
            int u=-1;
            //找到距离生成树最短距离的节点
            for (int i=1;i<=n;i++)
            {
                if(!vis[i]&&d[i]<maxx)
                {
                    maxx=d[i];
                    u=i;
                }
            }
            if(u==-1)
                break;
            //将选出的节点纳入集合
            vis[u]=1;
            //更新该节点影响的节点
            for (int i=1;i<=n;i++)
            {
                if(!vis[i]&&d[i]>edge[u][i])
                {
                    d[i]=edge[u][i];
                    p[i]=u;
                }
            }
        }
        int sum=0;
        for (int i=1;i<=n;i++)
            if(p[i]==-1)
            {
                printf("不存在最小生成树\n");
                return ;
            }
            else
                sum+=d[i];
            printf("最短生成树的长度为%d\n",sum);
            return ;
    }
    void parent ()
    {
        for (int i=1;i<=n;i++)
            if(p[i]!=-1&&p[i]==i)
                  printf("%d为根节点\n",i);
            else if(p[i]!=-1)
                  printf("%d的父节点为%d\n",i,p[i]);
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        init();
        for (int i=1;i<=m;i++)
        {
            int x,y,sp;
            scanf("%d%d%d",&x,&y,&sp);
            edge[x][y]=edge[y][x]=sp;
        }
        prim();
        parent();
        return 0;
    }
    
    
    展开全文
  • 对于一个无向连通图,若是稠密图的话: ...算法:设一个s集合(图的点的集合),初始时集合没有点 步骤:1:从所有点中找距离s集合最近的点:t 2:将t加入这个集合 3:更新:集合外的点到集合的距离 结束标...

    对于一个无向连通图,若是稠密图的话:
    存储:邻接矩阵g[N][N]来存储图,(N为图最大的点的数量)
    dist[N]存储集合外的点到集合的最短距离,
    s[N],即集合s,存储集合的点,若s[i] == true,则该点在集合,否则不在。
    算法:设一个s集合(图的点的集合),初始时集合没有点
    步骤:1:从所有点中找距离s集合最近的点:t
    2:将t加入这个集合
    3:更新:集合外的点到集合的距离
    结束标志:所有点都进入s集合

    代码如下:

    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    #define INF 0x3f3f3f3f
    
    const int N = 110;
    int dist[N];
    int g[N][N];
    int n, m;              //n为图的点数,m为边数
    bool s[N];
    
    int prim()
    {
        memset(dist, 0x3f, sizeof dist);      //将dist数组初始为无穷大
    
        int res = 0;                         //存储最小生成树边的权值和
        for(int i = 1; i <= n; i++)
        {
            int t = -1;
            for(int j = 1; j <= n; j++)
            {
                if(s[j] == false && (t == -1 || dist[j] < dist[t]))     //寻找到达集合最短距离的点,第一次循环将第一个点进入集合
                {
                    t = j;
                }
            }
    
            if(i > 1 && dist[t] == INF) return INF;//判断图是否连通,如果点距离集合所有其他点距离都为INF,则该图为非连通图(只有一个点的图可以认为是连通的)
            if(i > 1) res += dist[t]; //只有一个点的图,没有边
            s[t] = true; //点进入集合s
    
            for(int j = 1; j <= n; j++)
            {
                dist[j] = min(dist[j], g[t][j]);           //点t进入集合,更新其他点到集合的距离,j!=t,避免自回路存在
            }
    
            //cout << "res=" << res << endl;
        }
    
        return res;
    }
    
    int main()
    {
        cin >> n >> m;
    
        memset(g, 0x3f, sizeof(g));        //初始化,将边置为无穷大
    
        while(m--)
        {
            int u, v, w;
            cin >> u >> v >> w;
            g[u][v] = g[v][u] = min(g[u][v], w);         //考虑重边
        }
    
        int res = prim();
        if(res == INF) cout << "impossible" << endl;
        else cout << res << endl;
    
        return 0;
    }
    
    展开全文
  • 某通讯公司在县城设有九个通讯站,他们的位置可以用平面直角坐标系下的坐标表示。现要求把这些通讯站连接成一张网络,而连线费与长度成正比,应该如何联接才能使得总费用最低?a(0,15) b(5,20) c(16,24) d(20,20),e...
  • 构造网的最小生成树必须解决下面两个问题: 1、尽可能选取权值小的边,但不能构成回路; 2、选取n-1条恰当的边以连通n个顶点; MST性质:假设G=(V,E)是一个连通网,U是顶点V的一个非空子集。若(u,v)是一条具有最小...
  • 采用Prim算法构造最小生成树 2.解析 Prim算法基本思想:   假设G=(V,E)是连通的,TE是G上最小生成树中边的集合。算法从U={u0}(u0∈V)、TE={}开始。重复执行下列操作:在所有u∈U,v∈V-U的边(u,v)∈E中找...
  • Prim算法计算最小生成树(无向图&邻接矩阵)——C语言实现。
  • 采用Prim算法构造最小生成树的过程 第一步:选取一个起点 如图,有6个顶点v1-v6,集合表示为:V={v1,…,V6},每条边的权值都在图上;在进行prim算法时,我们先随意选择一个顶点作为起始点(起始点的选取不会影响最...
  • 1分钟解决Prim算法构造最小生成树

    千次阅读 2020-09-26 17:05:18
    前言:Prim 算法构造最小生成树!!!跟着画一遍就会了!!! Kruskal 请移步 kruskal 题目 设有如下图所示的无向连通图,从顶点A出发,使用 Prim 算法构造最小生成树,依次画出每次挑选出的边及权值。 题解 从顶点...
  • 实现构造最小生成树Prim算法
  • 举一个实例,画出采用Prim算法构造最小生成树的过程。 2.解析 已知图V = {…} 我们构造一棵最小生成树T 第一步:随意选取起点 第二步:在前一步的基础上寻找最小权值 第三步:继续寻找最小权值,之后以此类推,直到...
  • Prim算法最小生成树

    万次阅读 多人点赞 2019-06-11 20:41:47
    1. Prim算法也叫做普里姆算法,下面是普里姆算法的基本思想 从图中任意取出一个顶点,把它当成一棵,然后从这棵相接的边中选择一条最短的边(权值最小)的边,并将这条边及其所连接的顶点也一起并入到这棵中...
  • 采用Prim算法构造最小生成树 2.解析 我们已知一个图,对这样一个图通过Prim算法来构造它的最小生成树,我们通常需要进行以下4步操作: 定义两个集合V,E。对其进行初始化操作,其中V集合中随即设置一个初始点,在本...
  • python实现prim 最小生成树算法 源码
  • (1)利用克鲁斯卡尔算法求网的最小生成树,其中,以课本中的等价类表示构造生成树过程中的连通分量; (2)利用普里姆算法求网的最小生成树; (3)以文本文件形式输出生成树中各条边及它们的权值。 2.程序设计 本...
  • 建立一个含任意结点的无向连通网,并用Prim算法构造最小生成树
  • 实用标准文案 用 Prim 算法构造最小生成树 班级 2010 级计算机 1 班 学号 2010131116 姓名杨才 一实验目的 了解最小生成树的概念掌握生成最小生成树的方法 二实验内容 建立一个含任意结点的无向连通网并用 Prim 算法...
  • 用普里姆Prim构造最小生成树 一、最小生成树的概念 一个连通图的生成树是一个极小的连通子图,它含有图中的全部顶点,但只有构成一棵树的n-1条边。 对于一个带权(假定每条边上的权均大于0的数)连通无向图G中的不同...
  • 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。 算法描述 1).输入:一个加权连通图,其中顶点集合为V,边集合为E; 2).初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),...
  • (1)、实验题目:给定一个地区的n 个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并得到的最小生成树的代价。 (2)、实验要求: 1、城市间的距离网采用的邻接矩阵表示,邻接矩阵的存储结构定义采用...
  • Prim算法、Kruskal算法构造最小生成树(C语言) 问题 给定一个边权重的连通图,以点1为起点,构建一个能将图中所有定点连接起来,且边权重和最小的图。 解析 prim算法 prim算法的核心是从起始点开始,每次选择到已...
  • #采用Prim算法构造最小生成树 ##1问题 在一个无向图中,其某个子图中任意两个顶点都互相连通并且是一棵树,称之为生成树;若每个顶点有权值,则其权值和最小的生成树为最小生成树。 ##2.解析 从图中任意取出一个点...
  • 离散大作业 最小生成树算法 一Prim算法 设G=(V,E)是连通带权图V={1,2,n}构造G的最小生成树Prim算法的基本思想是 (1)置S={1} (2)只要S是V的真子集就作如下的贪心选择 选取满足条件i Sj V-S且c[i][j]最小的边将顶点j...
  • 普里姆(Prim)算法构造最小生成树 编译通过版本 可以直接运行使用

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,575
精华内容 3,030
关键字:

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