首页 > 代码库 > 【图论】畅通道路 prim Kruskal
【图论】畅通道路 prim Kruskal
最近在整理图论的算法。并且做了一些基础的题来练习，现在做一个总结，然后准备进入下一类算法的复习。
算法这个东西，就是不要害怕去编，哪怕自己只是有一点点理解，有好多点的模糊， 找一道基础的题， 对应着有一种思路解答的，去学习代码，学习里面的思路，并且自己动手跟着敲一敲，慢慢的就会理解了。 不用想着一开始就能够很彻底的理解算法的细节上思想。 理解的时候，从它所要达到的目的去思考， 知道它是要做一个什么事情，这是第一步。后面慢慢的多去练，就会更加深刻的理解里面的思想了，包括细节部分， 也会一点一点也清晰了。
感觉最近也总是提不起劲来做事情，果然是之前的大项目让自己疲惫了么，让自己消耗了太多脑细胞了咩。
噢哟哟， 想来这种情况在未来也可能是常态的， 我也得平时留心注意找一个能够让自己放松休息的方法， 劳逸结合， 这句话越来越觉得不错了。
古语真是古语，越品越有味道。
现在连最喜欢追的动漫，看起来都打不起精神来了。 学习底层的干劲也不是很强。 不过也是正常吧， 大脑在过度的使用之后，开始疲于思考， 或者说懒于思考了。
总之，这个月， 好好休息吧。
=================================================================================================================================
扯了一堆题外话，只在抒发一下自己的心情，很多事情要说出来才好。
首先总结两个图论算法，都是最小生成树算法。
prim算法：看一张图，简单明了。
prim算法的核心思想，就是以集合为中心，向外扩散。
分为两个集合, set1{}正在处理的最小生成树点 ,set2{}待处理的最小生成树点
每次从set2{}中寻找一个与该集合相邻接的，权值最小的点，加入set1{}， 直到set2{}中的点找完了。
下面是一个模板算法：算法是参考牙签大哥的。
模板使用说明：MAXN为定义的顶点最大可达数，n为图的大小，图以邻接表的形式存放在map中，调用prim函数后，最小需要花费的值为ret。
#define MAXN 101
int n, ret;
int map[MAXN][MAXN];
void prim()
{
int closet[MAXN];//set1{}集合的标记，标记为1的，表示加入到set1{}集合中
int dist[MAXN];//set2{}集合中的点到set1{}集合的最小距离，随着点的加入，要逐步更新
int i, j;
for ( i=0; i<n; i++)
{
closet[i] = 0;//将点都初始化为在set2{}集合中
dist[i] = map[0][i];//将以0号点v1为初始点，最小距离，设置为到v1的距离
}
closet[0] = 1;
int u, min;
for ( i=1; i<n; i++)//寻找剩下的n-2个点的最小距离的边
{
min = 100001;
for ( j=1; j<n; j++)//寻找一个set2{}集合的，到set1{}集合距离最小的点。
{
if ( ! closet[j] && dist[j] < min && dist[j] > 0)
{
u = j;
min = dist[j];
}
}
closet[u] = 1;//找到的点设置为set1{}集合
ret += min;//权值对应的增加
for ( j=1; j<n; j++)//依次更新各个点到set1{}集合的最小距离
{
if (! closet[j] && map[u][j] < dist[j] )
dist[j] = map[u][j];
}
}
}
Kruskal算法：依旧是一张图，简单明了。
Kruskal算法的核心，是以边的权值为出发点，从最小的权值边开始寻找，依次寻找边所依赖的两个点在不同的联通分量的点，直到最后构成n-1条边组成的最小生成树。
再上一个算法模板，
模板使用方法：vn表示图中结点个数，dis用邻接表的形式表示一幅图，dis[i][j]为0时表示i点和j点不连通，最后所需耗费的最小值存于sum中。
#include <stdio.h>
#include <queue>
using namespace std;
#define Maxv 100+5
typedef struct
{
int v1,v2,len;
}Node;//节点的结构体，边的两个点，和边的权值
bool operator > (Node a,Node b)//设置优先队列的排列条件
{
if( a.len > b.len )
return true;
return false;
}
int dis[Maxv][Maxv];//图的邻接表
int fa[Maxv];//对应点的父亲
int Getfa(int i)//寻找点i的父亲节点， 并且更新点i的父亲节点
{
if( fa[i] == i ) return i;
fa[i] = Getfa(fa[i]);
return fa[i];
}
int main()
{
int sum;
priority_queue< Node,vector<Node>,greater<Node> > Q; //返回最小数
int vn,i,j;
while( scanf( "%d" , &vn ) != EOF )
{
//输入图部分
for( i = 1 ; i <= vn ; i++ )
for( j = 1 ; j <= vn ; j++ )
scanf( "%d" , &dis[i][j] );
for( i = 1 ; i <= vn ; i++ ) fa[i] = i;
while( !Q.empty() ) Q.pop();//清空队列的点
//把每条边压入堆中
for( i = 1 ; i < vn ; i++ )
for( j = i+1 ; j <= vn ; j++ )
if( dis[i][j] )
{
Node e;
e.v1 = i , e.v2 = j , e.len = dis[i][j];
Q.push(e);
}
sum = 0;
while( Q.size() != 0 )//从最小边权值开始出发寻找，满足条件的边
{
Node e;
e = Q.top();//去除最小值
Q.pop();
if( Getfa(e.v1) != Getfa(e.v2) )//如果边的两个点的父亲不同，即属于不同的联通分量，就连接这两个点
{
sum += e.len;
fa[Getfa(e.v2)] = Getfa(e.v1);//v2的父亲的父亲 等于 v1的父亲，将v1,v2 连接起来了
}
}
printf( "%d\n" , sum ); //所需的最小值
}
return 0;
}
这里比较巧妙的是使用了Getfa这个函数，能够高效的判断两个点的联通分量，并且更新点所在的联通分量。还使用了STL里面的一个非常方便的priority_queue。这里有它的详细使用方法，很好用的。
http://www.cnblogs.com/flyoung2008/articles/2136485.html
==================================================================================================================================
接下来，就是我练习的题目的总结，解答仅供参考。
stage1:
畅通工程（http://acm.hdu.edu.cn/showproblem.php?pid=1232）
这道题目我在开始的时候考虑少了一种情况。
我在开始是这样考虑的。
设置两个集合set1（满足联通的点）, set2(待分析的点)。
对于每对输入的点，如果两个点，有一个以上的点在set1中，则不用增加边将它们联通；
如果两个点都不在set1中，则需要增加一个边将它们联通。
这个逻辑表面上看起来没有错，其实有一个错误：后面扫描边的时候，有两个点都在set1中，但是这两个点是在处理上述第二种情况的时候我自己加进去的，那么就会多出一条边。就是因为这个原因，我总是无法AC。后来多块CSDN的朋友，才得以解决。感谢CSDN的朋友！
下面上代码：
#include <stdio.h>
int city[1005];//用来记录点所在的集合，或者说联通分量
int main()
{
int n,m;
int count=0;
while(1)
{
scanf("%d",&n);
if( n == 0)
{
break;
}
scanf("%d",&m);
int i,a,b,temp,j;
int unionIndex = 0;
int unionNum = 0;
for ( i=1; i<=n; i++ ) city[i] = -1;//2、城市编号从1开始
for ( i=0; i<m; i++ )
{
scanf("%d%d",&a,&b);
if ( a == b ) continue;
if ( (city[a] == -1) && ( city[b] == -1 ) )
{
city[a] = unionIndex;
city[b] = unionIndex++;
unionNum++;
}
else if ( (city[a] != -1) && ( city[b] == -1 ) )
{
city[b] = city[a];
}
else if ( (city[a] == -1) && ( city[b] != -1 ) )
{
city[a] = city[b];
}
//缺少对后期连接了两个集合的判断， 可以减少独立集合数
//1、缺少对 输入的两个数本身就是一个集合的判断，这时不需要减少独立集合数
else if ( (city[a] != city[b]) && (city[a] != -1) && ( city[b] != -1 ) )
{
//对所有等于a集合标志的元素，归并成b集合标志的元素
temp = city[a];
for ( j=1; j<=n; j++ )//this range !!
if ( city[j] == temp ) city[j] = city[b];
unionNum--;
}
}
for ( i=1; i<=n; i++ )
{
if ( city[i] == -1 ) unionNum++;
}
//
//到目录为止一共有unionNum个联通集，则至少需要再添unionNum-1条路
printf( "%d\n", unionNum-1 );
}
return 0;
}这个方法比较笨，但是也比较有效，也比较直接。我在自己处理的时候，也会先考虑从自己解决问题的角度去设计解决方法，而不是直接就套用算法之类的。但随着到后期，相信很多算法，会内化成为我自然而然使用的设计方法。
stage2:
还是畅通工程（http://acm.hdu.edu.cn/showproblem.php?pid=1233）这里我依旧是从自己的考虑出发，凭借脑海中模糊的prim算法思想，构造出的代码，一次就ac成功了。仅供参考。
#include <stdio.h>
int map[102][102];//city start from 1
int rea_len=0;
int city[102];
int main()
{
int n,j,i;
while(scanf("%d",&n) && n)
{
int x,y,dis;
//init the map
for(i=1 ; i < 102 ; i++)
for(j=1 ; j<102 ; j++)
{
map[i][j] = 9999;
}
for(i=1 ; i<102 ;i++)
{
city[i]= 0;
}
rea_len=n;
city[1] = 1;
//input the city distance data
for(i=0 ; i< n*(n-1)/2 ; i++)
{
scanf("%d%d%d",&x,&y,&dis);
map[x][y] = dis;
map[y][x] = dis;
}
int k;
int sum=0;
while( --rea_len )
{
int min=9999;
for(i=1 ; i<=n; i++)
{
if( city[i] == 1)
for(j=1 ; j<=n ;j++)
{
if(i!=j && city[j] == 0 && (map[i][j] < min || map[j][i] < min) )
{
min = map[i][j];
k = j;
}
}
}
city[k] = 1;
sum += min;
}
printf("%d\n",sum);
}
return 0;
}stage3:
畅通工程（http://acm.hdu.edu.cn/showproblem.php?pid=1863）后面的解题，主要依靠Getfa函数，并且随着解题的深入，对于Getfa函数的理解也越来越深刻了。靠着Getfa函数，后面解题势如破竹。这个东西真是好用。
#include <stdio.h>
#include <queue>
using namespace std;
#define MAX 102
typedef struct
{
int x,y,cost;
}NODE;
bool operator > (NODE a, NODE b)
{
if( a.cost > b.cost ) return true;
return false;
}
//记录i点的父亲的值
int fa[MAX];
//寻找并且更新i点的最终父亲
int getfa(int i)
{
if( fa[i] == i) return i;
fa[i] = getfa( fa[i] );
return fa[i];
}
int main()
{
int n,m,i,j,sum;
priority_queue< NODE , vector<NODE>, greater<NODE> > Q;
while( scanf("%d",&n) && n)
{
while( !Q.empty() ) Q.pop();
sum=0;
scanf("%d",&m);
int x,y,cost;
NODE e;
while( n-- )
{
scanf("%d%d%d",&x,&y,&cost);
e.x = x;
e.y= y;
e.cost = cost;
Q.push(e);
}
for(i=1 ; i<=m ;i++) fa[i] = i;
while( Q.size() )
{
e = Q.top();
Q.pop();
if( getfa(e.x) != getfa(e.y) )
{
sum += e.cost;
fa[getfa(e.x)] = getfa(e.y);
}
}
for(i=1 ; i<m ;i++)
{
if( getfa(i) != getfa(i+1) )
{
printf("?\n");
break;
}
}
if( i == m)
{
printf("%d\n",sum);
}
}
return 0;
}stage4:
欧拉回路（http://acm.hdu.edu.cn/showproblem.php?pid=1878）
这道基础题关键就是要分析出欧拉回路的特点：
判断一个图是否存在欧拉回路的充要条件是：1）每个点的度数为偶数，2）图是连通的
#include <stdio.h>
int fa[1003];
int count[1003];
int getfa(int i)
{
if(fa[i] == i) return i;
fa[i] = getfa( fa[i] );
return fa[i];
}
bool isOK(int n)//判断联通，以及节点度数是否为偶数
{
int i;
for(i=1 ;i<n ; i++)
{
if( getfa(i) != getfa(i+1) || count[i] %2 != 0)
return false;
}
if( count[i]%2 != 0) return false;
return true;
}
int main()
{
int n,m,i;
while( scanf("%d",&n) && n)
{
scanf("%d",&m);
int x,y;
for(i=1 ; i<=n ; i++)
{
fa[i] = i;
count[i] = 0;
}
while(m--)
{
scanf("%d%d",&x,&y);
count[x]++;
count[y]++;
// 将x父亲的父亲指定为 y 的父亲。从根源处将两点联通。
// x--x1--x2 y--y1--y2 , x2--y2
fa[ getfa(x)] = getfa(y);
}
if( isOK(n) )
printf("1\n");
else
printf("0\n");
}
return 0;
}stage5:继续畅通工程（http://acm.hdu.edu.cn/showproblem.php?pid=1879）
//1.operator 操作数的使用方法
//2.priority_queue 的定义方法
#include <stdio.h>
#include <queue>
using namespace std;
typedef struct
{
int x,y,cost;
}NODE;
int fa[103];
int getfa(int i)
{
if( fa[i] == i) return i;
fa[i] = getfa( fa[i]);
return fa[i];
}
bool operator > (NODE a, NODE b)
{
if(a.cost > b.cost ) return true;
return false;
}
int main()
{
int n,i,sum;
priority_queue< NODE, vector<NODE>, greater<NODE> > Q;
while( scanf("%d", &n) && n)
{
while( !Q.empty() ) Q.pop();
for(i=1 ;i<=n; i++)
{
fa[i] = i;
}
sum=0;
int x,y,cost,isbuild;
NODE e;
for(i=1 ;i<= n*(n-1)/2 ; i++)
{
scanf("%d%d%d%d",&x ,&y, &cost, &isbuild);
if( isbuild == 1)
{
fa[ getfa(x)] = getfa(y);
continue;
}
e.x = x;
e.y = y;
e.cost = cost;
Q.push(e);
}
//由于没有一个比较有效的实时判断图是否已经连通的函数
//因此，将队列中所有的点都判断一遍，以做到在连通的情况下
//计算出最小成本
while( Q.size() )
{
e = Q.top();
Q.pop();
if( getfa(e.x) != getfa(e.y) )
{
fa[ getfa(e.x)] = getfa(e.y);
sum += e.cost;
}
}
printf("%d\n",sum);
}
return 0;
}感谢牙签，感谢wxspll。如果有什么问题，欢迎讨论。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。