文档章节

最小生成树 Kruskual和Prim算法

YYQ_ZJL
 YYQ_ZJL
发布于 2016/07/03 10:34
字数 381
阅读 6
收藏 0

最小生成树就是一个连通图的最小连通子集。

Kruskual算法:

hdu1223 code:

#include <iostream>
#include <cstdio>
#include<set>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#define maxn 105
typedef long long ll;
using namespace std;
typedef struct roads{
    int s,e,dis;
}Roads;
int father[maxn];
int find(int x){
    if(x!=father[x])
        father[x]=find(father[x]);
    return father[x];
}
bool compare(Roads a,Roads b){
    return a.dis < b.dis;
}
Roads w[maxn*maxn];
int ans;
bool vis[maxn];
int main()
{
    int n;
    while(scanf("%d",&n)&&n!=0)
    {
        ans = 0;
        for(int i=0;i<=n;i++){
             father[i]=i;
         }
        for(int i = 0;i < (n*(n-1))/2 ;i ++)
        {
            scanf("%d %d %d",&w[i].s,&w[i].e,&w[i].dis);
        }
        sort(w,w+(n*(n-1))/2,compare);
        memset(vis,0,sizeof(vis));
        int cnt = 0;
        for(int i = 0;i < (n*(n-1))/2;i ++)
        {
            int x=find(w[i].s);
            int y=find(w[i].e);
            if(x!=y){
                ans+=w[i].dis;
                father[x]=y;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

prim算法:

hdu1102code:

#include <iostream>
#include <algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
#include<list>
#define maxn 103
using namespace std;
typedef long long ll;
int dis[maxn];
int n;
vector<int> q;
int roads[maxn][maxn];
ll ans;
void prime(){
    for(int i = 1;i <= n;i ++)
    {
        q.push_back(i);
        dis[i] = roads[1][i];
    }
    while(q.size())
    {
        int t = 0;
        for(int i = 0;i < q.size();i ++){
            if(dis[q[t]] > dis[q[i]])
            {
                t = i;
            }
        }
        ans += dis[q[t]];
        for(int i = 0;i < q.size();i ++)
        {
            if(roads[q[t]][q[i]] < dis[q[i]]){
                dis[q[i]] = roads[q[t]][q[i]];
            }
        }
        int temp = q[t];
        q[t] = q[q.size() - 1];
        q[q.size()-1] = temp;
        q.pop_back();
    }
}
int main()
{
    int m,a,b,q1;

    while(scanf("%d",&n)!=EOF){
        q.clear();
        ans = 0;
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= n;j ++){
                scanf("%d",&roads[i][j]);
            }
        }
        cin >> m;
        for(int i = 1;i <= m;i ++){
            scanf("%d %d",&a,&b);
            roads[a][b] = roads[b][a] = 0;
        }
        prime();
        printf("%d\n",ans);
    }
    return 0;
}

 

本文转载自:http://www.cnblogs.com/zhangjialu2015/p/5557889.html

YYQ_ZJL
粉丝 0
博文 30
码字总数 206
作品 0
杭州
其他
私信 提问
加权无向图问题--最小代价生成树(Prim算法、kruskal算法)

加权无向图的实现 加权无向图的实现最简单的方法是扩展无向图的表示方法:在邻接表的表示中,可以在链表的结点中增加一个权重域。但这里用另一个方法来实现:我们实现两个类,权重边类和无向...

SuperHeroes
2017/12/20
503
0
加权无向图----Prim算法实现最小生成树

上一篇:加权无向图的实现 加权无向图----Kruskal算法实现最小生成树 图的生成树是它的一棵含有其所有顶点的无环连通子图,加权图的最小生成树(MST)是它的一棵权值最小的生成树。 切分:图...

Superheros
2017/12/20
10
0
最小生成树——Prim算法、Kruskal算法和Boruvka算法

最小生成树 概述 实际上是最小权重生成树的简称。在一给定的加权无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边,而 w(u, v) 代表此边的权重,若存在 T 中的顶点是所有V,T的边是...

bigfatsheep
2017/11/09
0
0
算法设计与分析之最小生成树问题

生成树 1.一个连通图的生成树是一个极小连通子图,它含有原图中全部顶点,并且有保持图连通的最少的边。 2.生成树不唯一。 最小生成树 设 贪心策略 在最小生成树问题中,至少有两种合理地贪心...

learning_tortosie
2018/05/02
0
0
最小生成树寻路(prim)

接着上一次的kruskal算法,这次讲更高级的prim算法 Prim Algorithm prim算法和经典的Dijkstra最短路径寻路算法惊人的相似,都是采用层层扩散的方式收敛出树。同时又与kruskal算法分享着类似的...

失败人士
2018/03/08
81
0

没有更多内容

加载失败,请刷新页面

加载更多

大厂面试经:高频率JVM面试问题整理!

JVM(Java虚拟机)简单来说就是运行Java代码的解释器,作为螺丝钉程序员JVM其实了解下就差不多啦,不懂JVM内部细节照样能写出优质的代码!但是一到造火箭、飞机的场景(面试)不懂JVM的你,会...

架构文摘
21分钟前
7
0
thinkphp5.1学习过程五——request

<?phpnamespace app\index\controller;//use \think\facade\Request;use \think\Request;/** * Class Demo3 * @package app\index\controller * 正常情况下,控制器不依赖......

大海yht
31分钟前
6
0
DB2 sequence 操作

操作DB2 下 sequence seqName db2数据库一般seq还是比较大的,但是程序在调用的时候还是不可避免的有一些bug, 下面是对于seq一些简单的操作,也作为工作的一些记录 1、命令行取sequence se...

飞雪无痕
今天
7
0
《吊打面试官》系列-秒杀系统设计

你知道的越多,你不知道的越多 点赞再看,养成习惯 GitHub上已经开源 https://github.com/JavaFamily 有一线大厂面试点脑图和个人联系方式,欢迎Star和指教 絮叨 之前写了很多Redis相关的知识...

敖丙
今天
15
0
Qt编写气体安全管理系统11-数据打印

一、前言 在各种软件系统中,数据打印也是常用的功能之一,一般来说会对查询的数据结果导出到excel,还会对查询的数据结果直接打印,在Qt中提供了打印机类QPrinter,在printsupport组件中,可...

飞扬青云
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部