[HTML_REMOVED] 首先先了解一些概念:[HTML_REMOVED]
连通图: 在无向图中,若任意两个顶点 i 与 j 都有路径相通,则称该无向图为连通图。
强连通图: 在有向图中,若任意两个顶点 i 与 j 都有路径相通,则称该有向图为强连通图
树: 如果一个无向连通图不包含回路(连通图中不存在环),那么就是一个树。
最小生成树:
一个有N个点的图,边一定是大于等于N-1条的。图的最小生成树,就是在这些边中选择N-1条出来,连接所有的N个点。
这N-1条边的边权之和是所有方案中最小的。
通俗易懂的来说: 最小生成树,就是求用( n-1 ) 条边 将n个点连接起来的最小权重之和。
样例中的最小生成树就如上所示,如何得来的,我们来分析一下。
[HTML_REMOVED] 通过例子来进一步的分析:[HTML_REMOVED]
Prim()本质的来说就是一个加点法,给一个空的集合挨个的加,离集合最近的点,直到点都加完。
步骤大致分为如下:
+ 初始化:每一个点到集合的距离初始为无穷大
+ 进行n次迭代,将没有在集合中且离集合最近的点进入到集合。
+ 用刚进入集合的点,更新所有点的距离。
初始化
刚开始集合为空,每一个点到集合的距离为无穷。
第一次迭代:1进入集合
因为首次迭代它进入集合的距离,我们不用加,res=0 。
实现的代码如下:
if(i) res+=dist[t];
第二次迭代:距离集合最近的点时2,故2进入集合
第三次迭代:距离集合最近的点是3,故3进入集合
可能有人不懂,究竟何为距离集合的距离 ?
其实距离集合的距离是这样的,以当前为例此时我们已经确定了两个点( 1, 2)。
那么3 距离集合是3,因为3 要和 1 或 2 两个点其中的任意一个点相连才可以进入这个集合。
由图可以知道 (1,3) (2,3) 的权值都为3 故3 距离集合的距离就为3.
==通俗易懂的话:就是当前点距离集合内的所有点中的最小距离就是 此点到集合的距离。==
第四次迭代:距离集合最近的点是4,故4进入集合
代码如下:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510;
const int INF=0x3f3f3f3f;
int g[N][N],dist[N];
bool st[N];
int n,m;
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[j] < dist[t] )) t=j;
st[t]=true;//标记此点进入集合过了
if(i) res+=dist[t]; //首次迭代不用加
if(i&&dist[t]==INF) return INF; //如果不是首次迭代且最近的点到集合的距离为 INF 说明不可连通
for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]); //更新
}
return res;
}
int main(void)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
if(i==j) g[i][j]=0;
else g[i][j]=INF;
}
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";
else cout<<t<<endl;
return 0;
}
Dijkstra() 算法 和 prim()算法 的dist[n] 有本质的区别
+ Dijkstra() 算法中 dist[ i ] 的含义是 i 到源点的距离。每一次的更新,也是更新,每一个点到源点的距离。
+ prim()算法算法中 dist[ i ] 的含义是 i 到集合的距离。每一次的更新,也是更新,每一个点到集合的距离。
一定要区分开来。