欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

最小生成树两个经典算法(Prime算法、Kruskal算法) - biaobiao88

程序员文章站 2023-04-04 13:28:58
经典的最小生成树例子,Prime算法,具体的步骤及其注释本人均在代码中附加,请仔细阅读与品味,要求,可以熟练的打出。 1 //Prime算法基础 2 #include 3 using namespace std; 4 5 int main() 6 { 7 int n,m,i,j, ......

 经典的最小生成树例子,prime算法,具体的步骤及其注释本人均在代码中附加,请仔细阅读与品味,要求,可以熟练的打出。

 1 //prime算法基础 
 2 #include<iostream>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int n,m,i,j,k,min,t1,t2,t3;
 8     int e[7][7],dis[7],book[7] = {0};
 9     int inf = 99999999;
10     int count = 0,sum = 0;
11     cin >> n >> m;
12     
13     //初始化 用邻接矩阵存储 
14     for(int i = 1;i <= n;i++)
15         for(int j = 1;j <= n;j++)
16             if(i == j)
17                 e[i][j] = 0;
18             else
19                 e[i][j] = inf;
20     
21     //读入边 无向图来回都得设置权值 
22     for(int i = 1;i <= m;i++)
23     {
24         cin >> t1 >> t2 >> t3;
25         e[t1][t2] = t3;
26         e[t2][t1] = t3;
27     }
28     
29     //初始化dis数组,这里是第一个顶点到各个顶点的初始距离,因为当前生成树中只有一个顶点
30     for(int i = 1;i <= n;i++)
31         dis[i] = e[1][i];
32         
33     //prime核心部分
34     //将第一个顶点(即1号顶点)加入生成树
35     book[1] = 1;//这里用book数组来标记一个顶点是否已经加入生成树 
36     count++;//表示生成树中已加入一个顶点 
37     while(count < n)
38     {
39         min = inf;
40         
41         //扫描找出距离当前根顶点相连接的最小权值的顶点 
42         for(int i = 1;i <= n;i++)
43         {
44             if(book[i] == 0 && min > dis[i])//如果根节点未被标记并且根节点到剩下的n-1个顶点之间有直连线(就是相连着的边) 
45             {
46                 min = dis[i];//就将这条边的权值代替之前初始化时的无穷大 ,更新min的值,min的值更新只在此for循环中有效,此for循环目的是找出连接根节点权值最小的那个顶点j,再把min放入for循环中,一直比较,直至找到最小的权值及连的顶点j 
47                 j = i;//同时将此时的顶点的编号记录在临时变量j中,以便接下来使用 
48             }
49         }
50         book[j] = 1;//将上面for循环中找到的最小权值的顶点j加入到生成树中并标记 
51         count++;//生成树中的顶点加一 
52         sum += dis[j];//将权值最小的边都累加,最终得到最优解 
53         
54         //扫描当前顶点j所有的边,再以j为中心点,更新生成树到每一个非树顶点的距离 
55         for(k = 1;k <= n;k++)
56         {
57             if(book[k] == 0 && dis[k] > e[j][k])//e[k]表示第一个加入的根顶点到顶点k之间的权值(可能直接连接也可能间接连接),e[j][k]表示的是当前根顶点作为j,到与j顶点直接相连的顶点k的权值 
58                 dis[k] = e[j][k];//此循环的目的是找出离j顶点最近的顶点 
59         }
60     }
61     cout << sum;
62     return 0;
63 }
64 /*
65 6 9
66 2 4 11
67 3 5 13
68 4 6 3
69 5 6 4
70 2 3 6
71 4 5 7
72 1 2 1
73 3 4 9
74 1 3 2
75 19
76 */

 运行结果:最小生成树两个经典算法(Prime算法、Kruskal算法) - biaobiao88

 

 kruskal算法,需要用到并查集,具体请看以下代码

  1 //kruskal算法 
  2 #include<iostream>
  3 #include<algorithm>
  4 using namespace std;
  5 struct edge
  6 {
  7     int u;
  8     int v;
  9     int w;
 10 }e[10];//为了方便排序,这里创建了一个结构体数组来存储边的关系,数组大小根据实际情况来设置,要比m的最大值大1 
 11 int n,m;
 12 int f[7],sum = 0,countt = 0;//并查集需要用到的一些变量,f数组大小根据实际情况来设置,要比n的最大值大1 
 13 
 14 ////这个也是快速排序,也可以替代sort函数 
 15 //void quicksort(int left,int right)
 16 //{
 17 //    int i,j;
 18 //    struct edge t;
 19 //    if(left > right)
 20 //        return;
 21 //    i = left;
 22 //    j = right;
 23 //    while(i != j)
 24 //    {
 25 //        //顺序很重要,要先从右边开始找 
 26 //        while(e[j].w >= e[left].w && i < j)
 27 //            j--;
 28 //        //再从左边开始找 
 29 //        while(e[i].w <= e[left].w && i < j)
 30 //            i++;
 31 //        //交换 
 32 //        if(i < j)
 33 //        {
 34 //            t = e[i];
 35 //            e[i] = e[j];
 36 //            e[j] = t;
 37 //        }
 38 //    }
 39 //    //最终将基准数归位,将left和i互换 
 40 //    t = e[left];
 41 //    e[left] = e[i];
 42 //    e[i] = t;
 43 //    
 44 //    quicksort(left,i - 1);//继续处理左边的,这里是一个递归的过程 
 45 //    quicksort(i + 1,right);//继续处理右边的,这里是一个递归的过程 
 46 //    return;
 47 //}
 48 
 49 //并查集寻找祖先的函数 
 50 int getf(int v)
 51 {
 52     if(f[v] == v)
 53         return v;
 54     else
 55     {
 56         //这里是路径压缩 
 57         f[v] = getf(f[v]);
 58         return f[v];
 59     }
 60 }
 61 //并查集合并两个子集合的函数 
 62 int merge(int v,int u)
 63 {
 64     int t1,t2;
 65     t1 = getf(v);
 66     t2 = getf(u);
 67     if(t1 != t2)//判断两个点是否在同一个集合中 
 68     {
 69         f[t2] = t1;
 70         return 1;
 71     }
 72     return 0;
 73 }
 74 
 75 bool cmp(const edge &a,const edge &b)
 76 {
 77     return a.w < b.w;
 78 }
 79 
 80 int main()
 81 {
 82     //读入顶点个数n和边的条数m 
 83     cin >> n >> m;
 84     //读入边,这里用结构体数组来存储边的关系 
 85     for(int i = 1;i <= m;i++)
 86         cin >> e[i].u >> e[i].v >> e[i].w;
 87 //    quicksort(1,m);//按照权值从大到小对边进行快速排序
 88     //快速排序权值 
 89     sort(e + 1,e + m + 1,cmp);
 90     //并查集初始化
 91     for(int i = 1;i <= n;i++)
 92         f[i] = i;
 93     
 94     //kruskal算法核心部分
 95     for(int i = 1;i <= m;i++)
 96     {
 97         //判断一条边的两个顶点是否已经连通,即判断是否已在同一个集合中 
 98         if(merge(e[i].u,e[i].v))//如果目前不连通,则选用这条边 
 99         {
100             countt++;//满足条件将顶点加入生成树 
101             sum += e[i].w;//路径累加和 
102         }
103         if(countt == n - 1)//当顶点均加入到生成树中时,结束循环 
104             break;
105     }
106     cout << sum << endl;
107     return 0;
108 }

运行结果:最小生成树两个经典算法(Prime算法、Kruskal算法) - biaobiao88

 

 并查集例题

最小生成树两个经典算法(Prime算法、Kruskal算法) - biaobiao88

下面是对并查集使用的代码,并查集不太理解的可以看看下面的代码

 1 //并查集的使用 
 2 #include<iostream>
 3 using namespace std;
 4 int f[1000],n,m,k,sum;
 5 
 6 //这是找爹的递归函数,不停的去找爹,直到找到祖宗为止,即找到根节点,这个函数的目的是判断两个顶点是否属于同一个集合 
 7 int getf(int v)
 8 {
 9     if(f[v] == v)
10         return v;
11     else
12     {
13         /*这里是路径压缩,每次在函数返回的时候,顺带把同一个集合里面的元素都改为根节点的祖先编号,这样可以提高今后找到树的祖先的速度*/
14         f[v] = getf(f[v]);
15         return f[v];
16     }
17 }
18 //这里是合并两子集合的函数,在合并函数中调用getf函数,看两个顶点是否是属于同一个集合,然后再决定是否执行合并操作 
19 void merge(int v,int u)
20 {
21     int t1,t2;
22     t1 = getf(v);
23     t2 = getf(u);
24     if(t1 != t2)//根据调用getf的函数,判断两个顶点是否在同一个集合中,即是否为同一个祖先 
25     {
26         f[t2] = t1;
27     }
28 }
29 
30 int main()
31 {
32     int x,y;
33     cin >> n >> m;
34     //这里是初始化,非常的重要,数组里面存的是自己数组下标的编号就好了
35     for(int i = 1;i <= n;i++)
36         f[i] = i;
37     for(int i = 1;i <= m;i++)
38     {
39         cin >> x >> y;
40         merge(x,y);//将两个顶点传入合并集合函数中进行操作 
41     }
42     for(int i = 1;i <= n;i++)
43     {
44         if(f[i] == i)//根节点的值依旧是原先的值,即判断有几个顶点的值不变即有几个不同的集合 
45             sum++;
46     }
47     cout << sum << endl;
48     return 0;
49 }
50 /*
51 10 9
52 1 2
53 3 4
54 5 2
55 4 6
56 2 6
57 8 7
58 9 7
59 1 6
60 2 4
61 3
62 */

运行结果:最小生成树两个经典算法(Prime算法、Kruskal算法) - biaobiao88