最小生成树-Prim算法

最小生成树minimal-spanning-tree(概念就不具体介绍了)有两种基于不同贪心选择的算法，一个为Prim算法，一个为Kruskal算法。

Prim和Dijkstra算法很像，只是少了些东西。它将结点分为两类，一类是已经选择了的确定的，构建好了的mst的结点，另一类是还没确定的未选择的结点。

流程是这样的：（括号内为权值），U集合：MST的点集合，V-U：未选择的点集合

1.首先初始化开始结点U，然后把所有能够与U相连的边为候选边

这里就是数组初始化操作了;

1      int sum=0;
2     for(int i=1;i)
3     {
4         dis[i]=map[1][i];//初始化所有点到结点1的距离
5         vis[i]=false;//所有点开始都未被访问
6     }
7     vis[1]=true;//结点1标志为true

开始时U是结点1,然后找到所有与1相连的边(dist[i][j]!=0)，分别是1-6(10),1-2(28)，所以找出最小的(6

 1 for(int i=2;i)
 2     {
 3         int MIN=INF;//从当前节点u到与u联通的子节点的最小权值
 4         int k=-1;
 5         for(int j=1;j)//遍历每个点
 6         {
 7             if(!vis[j]&&dis[j]<MIN)//未被访问且距离还小，那就待定选你了，看看还有没有距离更短的
 8             {
 9                 MIN=dis[j];//更新最小值，这个dis表式这个点到已知mst中一点的最小值
10                 k=j;//标记结点号
11             }
12         }
13         vis[k]=true;//u->a->b  k->b //置已经访问
14         sum+=MIN;//u->k求生成树的路径和
15         ...

16         ...

17        ...

18 }

然后我们发现，左部分和右部分只有两条边相连了，那么继续找最短边就行6-5(25)

再比较1-2(28),5-7(24),5-4(22)，取出最小边是5-4(22),更新图

继续比较选出最短边，这时有4个边要比较了，1-2(28),5-7(24),4-7(18),4-3(12),找出最短边4-3(12),更新图

继续比较4个个边，1-2(28),5-7(24),4-7(18),3-2(16)，找出最短的16,更新图

好了，最后已给点7,应该很容易看出来它是2连接的，因为14是最短的。

所以MST图是这样

后半段的代码是这样的

1 for(int j=1;j//带已经找到点k的情况下，找结点j
2         {
3             if(!vis[j]&&dis[j]>map[k][j])
4             {//j未访问且 j到mst中点的最小值还大于从k到j的距离，那么就
5 //要更新这段距离
6                 dis[j]=map[k][j];//clost[j] = k;
7             }
8         }

看这个图

比如说开始先初始化，dist[6] =10;dist[4]=1,即结点6和4到结点1的最短距离为dist数组，然后我找到了最短路1-4,并且发现原来的1-6(10)大于6-4(5)，所以更新dist[6]=4,他表示结点6到已知MST的某个点的最短的那个距离，也可以将那个点记录在clost数组中，以便需要。

完整代码，其实很简单的

邻接矩阵：

 1 #include
 2 #include
 3 #include
 4 using namespace std;
 5 const int INF=0x3f3f3f3f;
 6 const int MAXN=1005;
 7 int map[MAXN][MAXN];   //map[i][j]   ----  i->j =v
 8 int dis[MAXN];     //
 9 bool vis[MAXN];
10 int n;
11 void init()
12 {
13     for(int i=0;i<=n;i++)
14     {
15         for(int j=0;j<=n;j++)
16         {
17             if(i!=j)map[i][j]=INF;
18             else map[i][j]=0;
19         }
20     }
21 }
22 int Prim()
23 {
24     int sum=0;
25     for(int i=1;i<=n;i++)
26     {
27         dis[i]=map[1][i];
28         vis[i]=false;
29     }
30     vis[1]=true;
31     for(int i=2;i<=n;i++)
32     {
33         int MIN=INF;//从当前节点u到与u联通的子节点的最小权值
34         int k=-1;//u->v k=v;
35         for(int j=1;j<=n;j++)
36         {
37             if(!vis[j]&&dis[j]<MIN)
38             {
39                 MIN=dis[j];
40                 k=j;
41             }
42         }
43         vis[k]=true;//u->a->b  k->b
44         sum+=MIN;//u->k
45         for(int j=1;j<=n;j++)
46         {
47             if(!vis[j]&&dis[j]>map[k][j])
48             {
49                 dis[j]=map[k][j];
50             }
51         }
52     }
53     return sum;
54 }
55 int main()
56 {
57     cin>>n;
58     init();
59     for(int i=1;i<=n;i++)
60     {
61         for(int j=1;j<=n;j++)
62         {
63             int v;
64             cin>>v;
65             if(map[i][j]>v)
66             {
67                 map[i][j]=map[j][i]=v;
68             }
69         }
70     }
71     int c;
72     cin>>c;
73     for(int i=1;i<=c;i++)
74     {
75         int a,b;
76         cin>>a>>b;
77         map[a][b]=map[b][a]=0;
78     }
79     /for(int i=1;i<=n;i++)>80     {
81         int a,b,v;
82         cin>>a>>b>>v;
83         /if(map[a][b]>v)
84         {
85             map[a][b]=map[b][a]=v;
86         }
87         map[a][b]=v;
88     }*/
89     cout<<prim()<<endl;
</prim()<<90     return 0;
91 }

View Code

邻接表：

  1 /**********
  2     > File Name: p3366.cpp
  3     > Author: YeGuoSheng
  4     > Description:
  5 最小生成树模板 、如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz
  6 输入格式
  7 第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，m<=200000）>  8
  9 接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi
 10
 11 输出格式
 12 输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz
 13 输入输出样例
 14 输入 #1 复制
 15 4 5
 16 1 2 2
 17 1 3 2
 18 1 4 3
 19 2 3 4
 20 3 4 3
 21 输出 #1 复制
 22 7
 23     > Created Time: 2019年08月02日 星期五 10时26分54秒
 24  ***********/
 25
 26 #include
 27 #include
 28 #include
 29 #include
 30 #include
 31 #include
 32 #include 68     { 69 70         cin>>x>>y>>w; 71         Add(x,y,w);//添加双向边 72         Add(y,x,w); 73     } 74 } 75 76 void Prim() 77 { 78     int total = 0; 79     int ans = 0; 80     int now = 1; 81     for(int i = 2;i <=>) 82     { 83         dis[i] = INF; 84     } 85 86     for(int i = head[1];i;i=edges[i].next) 87     { 88         dis[edges[i].v] = min(dis[edges[i].v],edges[i].w); 89     }//更新所有与起点1相连的边并找到最小值 90 91     while(++total < n)//加入mst顶点数<图的顶点数即没找完，循环<> 92     { 93         int minn = INF; 94         vis[now] = 1; 95         for(int i = 1;i <=>)

 96         { 97             if (! vis[i] && minn > dis[i])//找到一条最短边 98             { 99                 minn = dis[i];100                 now = i;101             }102         }103         ans += minn;//当前找到的最短距离加入结果距离变量中104         for(int i = head[now]; i ; i =edges[i].next)//松弛操作105         {106             int v = edges[i].v;107             if(  ! vis[v]&& dis[v] > edges[i].w )108             {109                 dis[v] = edges[i].w;110             }111         }112     }113     if(ans < INF)//找到解114     {115        cout<<ans<<endl;116     }117     else118     {119         cout<<"orz"<<endl;120     }121122 }123 int main()124 {125     Init();126     Prim();127     return 0;128 }</ans<<

View Code

传送门：Agri-Net

Original: https://www.cnblogs.com/ygsworld/p/11229055.html
Author: 回忆酿的甜
Title: 最小生成树-Prim算法