• 最小生成树算法的相关变形题

    由于吉大近几年的考试中，算法大题里频繁地出现最小生成树算法的变形题，因此在此整理一下。

    PS：prim算法不管是画图还是代码题真的难用，kruskal算法才是永远滴神

    以下大部分代码的思想参考自：生成树相关问题一网打尽！（最小生成树变形，次小生成树，最小度限度生成树，极差最小生成树）_哔哩哔哩_bilibili

    目录

    最小生成树

    最大生成树

    加入一条新边，求新的最小生成树

    次小生成树

    判断最小生成树是否唯一

    极差最小的生成树

    最小生成树

    1. #define maxsize 100
    2.  
    3. //并查集
    4. int father[maxsize] = { 0 };
    5. int Find(int x)
    6. {
    7.     if (father[x] <= 0) return x;
    8.     return father[x] = Find(father[x]);
    9. }
    10. void Union(int x, int y)
    11. {
    12.     int fx = Find(x);
    13.     int fy = Find(y);
    14.     if (fx == fy) return;
    15.     if (father[fx] < father[fy])
    16.     {
    17.         father[fy] = fx;
    18.     }
    19.     else
    20.     {
    21.         if (father[fx] == father[fy])
    22.         {
    23.             father[fy]--;
    24.         }
    25.         father[fx] = fy;
    26.     }
    27. }
    28. //对边进行排序，并存入edge数组中
    29. int sort_edge(int graph[][6], int n, int edge[][3])
    30. {
    31.     int edgenum = 0;  //k为边的数量
    32.     for (int i = 1; i <= n; i++)
    33.     {
    34.         for (int j = i + 1; j <= n; j++)
    35.         {
    36.             if (graph[i][j])
    37.             {
    38.                 edgenum++;
    39.                 edge[edgenum][0] = i;
    40.                 edge[edgenum][1] = j;
    41.                 edge[edgenum][2] = graph[i][j];
    42.             }
    43.         }
    44.     }
    45.     for (int i = edgenum; i > 1; i--)
    46.     {
    47.         int flag = 0;
    48.         for (int j = 1; j < i; j++)
    49.         {
    50.             if (edge[j][2] > edge[j + 1][2])
    51.             {
    52.                 flag = 1;
    53.  
    54.                 int tmp[3];
    55.                 memcpy(tmp, edge[j], sizeof(int) * 3);
    56.                 memcpy(edge[j], edge[j + 1], sizeof(int) * 3);
    57.                 memcpy(edge[j + 1], tmp, sizeof(int) * 3);
    58.             }
    59.         }
    60.         if (!flag) break;
    61.     }
    62.     printf("排序后的边为：");
    63.     for (int i = 1; i <= edgenum; i++)
    64.     {
    65.         printf("%d--%d:%d  ", edge[i][0], edge[i][1], edge[i][2]);
    66.     }printf("\n\n");
    67.     return edgenum;
    68. }
    69. //kruskal算法
    70. void kruskal(int graph[][6], int n)
    71. {
    72.     int edge[maxsize][3];
    73.     int edgenum = sort_edge(graph, n, edge);
    74.     int T = n;    //集合的个数
    75.     int k = 1;
    76.     int ans = 0;
    77.     printf("最小生成树：");
    78.     while (T > 1)
    79.     {
    80.         int a = edge[k][0];
    81.         int b = edge[k][1];
    82.         int w = edge[k][2];
    83.         k++;
    84.  
    85.         if (Find(a) == Find(b)) continue;
    86.         Union(a, b);
    87.         T--;
    88.         ans += w;
    89.         printf("%d--%d:%d  ", a, b, w);
    90.     }printf("\n\n");
    91.     printf("最小生成树的权值为：%d\n", ans);
    92. }
    93.  
    94. int main()
    95. {
    96.     int graph[6][6] = { 0 };
    97.     int n = 5;
    98.     graph[1][4] = 1;    graph[4][1] = 1;
    99.     graph[1][3] = 2;    graph[3][1] = 2;
    100.     graph[1][2] = 3;    graph[2][1] = 3;
    101.     graph[3][4] = 4;    graph[4][3] = 4;
    102.     graph[4][5] = 5;    graph[5][4] = 5;
    103.     graph[2][5] = 6;    graph[5][2] = 6;
    104.     for (int i = 1; i <= n; i++)
    105.     {
    106.         for (int j = 1; j <= n; j++)
    107.         {
    108.             printf("%d ", graph[i][j]);
    109.         }printf("\n");
    110.     }printf("\n");
    111.  
    112.     kruskal(graph, n);
    113.     return 0;
    114. }

    对于下图来说：

                                    

    其最小生成树为：

                                          

    上述代码的结果为：

    最大生成树

    最简单的一个，就是把一开始的边排序改为降序排序而已，和上面的代码相比就是改了个大于号，其他的都一样

    1. #define maxsize 100
    2.  
    3. int father[maxsize] = { 0 };
    4. int Find(int x)
    5. {
    6.     if (father[x] <= 0) return x;
    7.     return father[x] = Find(father[x]);
    8. }
    9. void Union(int x, int y)
    10. {
    11.     int fx = Find(x);
    12.     int fy = Find(y);
    13.     if (fx == fy) return;
    14.     if (father[fx] < father[fy])
    15.     {
    16.         father[fy] = fx;
    17.     }
    18.     else
    19.     {
    20.         if (father[fx] == father[fy])
    21.         {
    22.             father[fy]--;
    23.         }
    24.         father[fx] = fy;
    25.     }
    26. }
    27. //对边进行排序，并存入edge数组中
    28. int sort_edge(int graph[][6], int n, int edge[][3])
    29. {
    30.     int edgenum = 0;  //k为边的数量
    31.     for (int i = 1; i <= n; i++)
    32.     {
    33.         for (int j = i + 1; j <= n; j++)
    34.         {
    35.             if (graph[i][j])
    36.             {
    37.                 edgenum++;
    38.                 edge[edgenum][0] = i;
    39.                 edge[edgenum][1] = j;
    40.                 edge[edgenum][2] = graph[i][j];
    41.             }
    42.         }
    43.     }
    44.     for (int i = edgenum; i > 1; i--)
    45.     {
    46.         int flag = 0;
    47.         for (int j = 1; j < i; j++)
    48.         {
    49.             if (edge[j][2] < edge[j + 1][2])    //这里改为降序排序
    50.             {
    51.                 flag = 1;
    52.  
    53.                 int tmp[3];
    54.                 memcpy(tmp, edge[j], sizeof(int) * 3);
    55.                 memcpy(edge[j], edge[j + 1], sizeof(int) * 3);
    56.                 memcpy(edge[j + 1], tmp, sizeof(int) * 3);
    57.             }
    58.         }
    59.         if (!flag) break;
    60.     }
    61.     printf("排序后的边为：");
    62.     for (int i = 1; i <= edgenum; i++)
    63.     {
    64.         printf("%d--%d:%d  ", edge[i][0], edge[i][1], edge[i][2]);
    65.     }printf("\n\n");
    66.     return edgenum;
    67. }
    68.  
    69.  
    70. void kruskal(int graph[][6], int n)
    71. {
    72.     int edge[maxsize][3];
    73.     int edgenum = sort_edge(graph, n, edge);
    74.     int T = n;    //集合的个数
    75.     int k = 1;
    76.     int ans = 0;
    77.     printf("最小生成树：");
    78.     while (T > 1)
    79.     {
    80.         int a = edge[k][0];
    81.         int b = edge[k][1];
    82.         int w = edge[k][2];
    83.         k++;
    84.  
    85.         if (Find(a) == Find(b)) continue;
    86.         Union(a, b);
    87.         T--;
    88.         ans += w;
    89.         printf("%d--%d:%d  ", a, b, w);
    90.     }printf("\n\n");
    91.     printf("最小生成树的权值为：%d\n", ans);
    92. }
    93.  
    94. int main()
    95. {
    96.     int graph[6][6] = { 0 };
    97.     int n = 5;
    98.     graph[1][4] = 1;    graph[4][1] = 1;
    99.     graph[1][3] = 2;    graph[3][1] = 2;
    100.     graph[1][2] = 3;    graph[2][1] = 3;
    101.     graph[3][4] = 4;    graph[4][3] = 4;
    102.     graph[4][5] = 5;    graph[5][4] = 5;
    103.     graph[2][5] = 6;    graph[5][2] = 6;
    104.     for (int i = 1; i <= n; i++)
    105.     {
    106.         for (int j = 1; j <= n; j++)
    107.         {
    108.             printf("%d ", graph[i][j]);
    109.         }printf("\n");
    110.     }printf("\n");
    111.  
    112.     kruskal(graph, n);
    113.     return 0;
    114. }

     对于下图来说：

                                    

    其最大生成树为：

                            ​​​​​​​        ​​​​​​​      

    代码的结果为：

    加入一条新边，求新的最小生成树

    假设图G的最小生成树T已知，现给定一条加入G的新边e（G的点集不变），给出寻找G+e新图的最小生成树算法，时间复杂度O(n)，n为G的顶点数，G/T采用邻接表/矩阵存储即可。

    大致思路：在最小生成树中加入一条新边 newa -- newb（权值为neww），肯定会构成一个环，然后找到环中除了新边 newa -- newb 之外最长的一条边的权值，也就是在原先的最小生成树中从节点newa到节点newb的路径上最长的一条边的权值maxw，如果新边的权值neww < maxw，那么我们就可以用这条新边代替原先的最长边，新的最小生成树的权值自然也会变小；如果neww >= maxw，那么不用替代，原先的最小生成树依旧是新的最小生成树。

    实际上就是在原先的kruskal算法的基础上增加了两个函数：

    1. int mintree[maxsize][maxsize] = { 0 };        //用邻接矩阵的方式存储最小生成树
    2. int n = 5;
    3. //用dfs找到形成的环中，除新加入的边 a-b 外，最长的一条边的权值
    4. //即在原先的生成树中，从节点a到节点b的路径上最长的一条边的权值
    5. void dfs(int v, int b, int visited[], int curw, int* maxw)      //curw是从节点a到当前节点v的路径上最长的一条边的权值
    6. {
    7.     visited[v] = 1;
    8.     if (v == b)     //如果找到了b节点
    9.     {
    10.         //为什么这个代码需要curw，而不是直接用一个maxw记录所遇到的最大的边的权值呢？
    11.         //原因就在这里，只有在遇到终点b时才能确定max的值就是a到b的路径上最大的边的权值
    12.         //如果按照前者的思路只用一个maxw的话，那记录的不就是生成树中最大的边的权值了？显然不合理
    13.         *maxw = curw;
    14.         return;
    15.     }
    16.     for (int i = 1; i <= n; i++)
    17.     {
    18.         if (mintree[v][i] != 0 && !visited[i])
    19.         {
    20.             int temp = curw;    //记录一下原先curw的值，用于回溯
    21.             if (mintree[v][i] > curw) curw = mintree[v][i];
    22.             dfs(i, b, visited, curw, maxw);
    23.             curw = temp;        //回溯
    24.         }
    25.     }
    26. }
    27. //向图中加入一条新边后，求最小生成树
    28. void Add_newedge(int newa, int newb, int neww, int ans)
    29. {
    30.     int visited[maxsize] = { 0 };
    31.     int maxw;    //存储最长边的权值
    32.     dfs(newa, newb, visited, 0, &maxw);
    33.     printf("在原先的最小生成树中，节点%d到节点%d的路径上的最长边的权值为：%d\n\n", newa, newb, maxw);
    34.     if (neww < maxw)    //如果新加入的这条边的权值小于最长边的权值，那么就能够用这题新边代替原来的最长边
    35.     {
    36.         ans = ans - maxw + neww;
    37.     }
    38.     printf("加入边 %d--%d 后，新的最小生成树的权值为：%d\n",newa, newb, ans);
    39. }

    完整的代码如下：

    1. #define maxsize 100
    2.  
    3. int father[maxsize] = { 0 };
    4. int Find(int x)
    5. {
    6.     if (father[x] <= 0) return x;
    7.     return father[x] = Find(father[x]);
    8. }
    9. void Union(int x, int y)
    10. {
    11.     int fx = Find(x);
    12.     int fy = Find(y);
    13.     if (fx == fy) return;
    14.     if (father[fx] < father[fy])
    15.     {
    16.         father[fy] = fx;
    17.     }
    18.     else
    19.     {
    20.         if (father[fx] == father[fy])
    21.         {
    22.             father[fy]--;
    23.         }
    24.         father[fx] = fy;
    25.     }
    26. }
    27. //对边进行排序，并存入edge数组中
    28. int sort_edge(int graph[][6], int n, int edge[][3])
    29. {
    30.     int edgenum = 0;  //k为边的数量
    31.     for (int i = 1; i <= n; i++)
    32.     {
    33.         for (int j = i + 1; j <= n; j++)
    34.         {
    35.             if (graph[i][j])
    36.             {
    37.                 edgenum++;
    38.                 edge[edgenum][0] = i;
    39.                 edge[edgenum][1] = j;
    40.                 edge[edgenum][2] = graph[i][j];
    41.             }
    42.         }
    43.     }
    44.     for (int i = edgenum; i > 1; i--)
    45.     {
    46.         int flag = 0;
    47.         for (int j = 1; j < i; j++)
    48.         {
    49.             if (edge[j][2] > edge[j + 1][2])
    50.             {
    51.                 flag = 1;
    52.  
    53.                 int tmp[3];
    54.                 memcpy(tmp, edge[j], sizeof(int) * 3);
    55.                 memcpy(edge[j], edge[j + 1], sizeof(int) * 3);
    56.                 memcpy(edge[j + 1], tmp, sizeof(int) * 3);
    57.             }
    58.         }
    59.         if (!flag) break;
    60.     }
    61.     printf("排序后的边为：");
    62.     for (int i = 1; i <= edgenum; i++)
    63.     {
    64.         printf("%d--%d:%d  ", edge[i][0], edge[i][1], edge[i][2]);
    65.     }printf("\n\n");
    66.     return edgenum;
    67. }
    68.  
    69. int mintree[maxsize][maxsize] = { 0 };        //用邻接矩阵的方式存储最小生成树
    70. int n = 5;
    71. //找到形成的环中，除新加入的边 a-b 外，最长的一条边的权值
    72. //即在原先的生成树中，从节点a到节点b的路径上最长的一条边的权值
    73. void dfs(int v, int b, int visited[], int curw, int* maxw)      //curw是从节点a到当前节点v的路径上最长的一条边的权值
    74. {
    75.     visited[v] = 1;
    76.     if (v == b)     //如果找到了b节点
    77.     {
    78.         //为什么这个代码需要curw，而不是直接用一个maxw记录所遇到的最大的边的权值呢？
    79.         //原因就在这里，只有在遇到终点b时才能确定max的值就是a到b的路径上最大的边的权值
    80.         //如果按照前者的思路只用一个maxw的话，那记录的不就是生成树中最大的边的权值了？显然不合理
    81.         *maxw = curw;
    82.         return;
    83.     }
    84.     for (int i = 1; i <= n; i++)
    85.     {
    86.         if (mintree[v][i] != 0 && !visited[i])
    87.         {
    88.             int temp = curw;    //记录一下原先curw的值，用于回溯
    89.             if (mintree[v][i] > curw) curw = mintree[v][i];
    90.             dfs(i, b, visited, curw, maxw);
    91.             curw = temp;        //回溯
    92.         }
    93.     }
    94. }
    95. //向图中加入一条新边后，求最小生成树
    96. void Add_newedge(int newa, int newb, int neww, int ans)
    97. {
    98.     int visited[maxsize] = { 0 };
    99.     int maxw;    //存储最长边的权值
    100.     dfs(newa, newb, visited, 0, &maxw);
    101.     printf("在原先的最小生成树中，节点%d到节点%d的路径上的最长边的权值为：%d\n\n", newa, newb, maxw);
    102.     if (neww < maxw)    //如果新加入的这条边的权值小于最长边的权值，那么就能够用这题新边代替原来的最长边
    103.     {
    104.         ans = ans - maxw + neww;
    105.     }
    106.     printf("加入边 %d--%d 后，新的最小生成树的权值为：%d\n",newa, newb, ans);
    107. }
    108.  
    109. int kruskal(int graph[][6], int n)
    110. {
    111.     int edge[maxsize][3];
    112.     int edgenum = sort_edge(graph, n, edge);
    113.     int T = n;    //集合的个数
    114.     int k = 1;
    115.     int ans = 0;
    116.     printf("最小生成树：");
    117.     while (T > 1)
    118.     {
    119.         int a = edge[k][0];
    120.         int b = edge[k][1];
    121.         int w = edge[k][2];
    122.         k++;
    123.  
    124.         if (Find(a) == Find(b)) continue;
    125.         Union(a, b);
    126.         T--;
    127.         ans += w;
    128.         mintree[a][b] = mintree[b][a] = w;
    129.         printf("%d--%d:%d  ", a, b, w);
    130.     }printf("\n\n");
    131.     printf("最小生成树的权值为：%d\n\n", ans);
    132.     return ans;
    133. }
    134.  
    135. int main()
    136. {
    137.     int graph[6][6] = { 0 };
    138.     int n = 5;
    139.     graph[1][4] = 1;    graph[4][1] = 1;
    140.     graph[1][3] = 2;    graph[3][1] = 2;
    141.     graph[1][2] = 3;    graph[2][1] = 3;
    142.     graph[3][4] = 4;    graph[4][3] = 4;
    143.     graph[4][5] = 5;    graph[5][4] = 5;
    144.     graph[2][5] = 6;    graph[5][2] = 6;
    145.     printf("原图：\n");
    146.     for (int i = 1; i <= n; i++)
    147.     {
    148.         for (int j = 1; j <= n; j++)
    149.         {
    150.             printf("%d ", graph[i][j]);
    151.         }printf("\n");
    152.     }printf("\n");
    153.  
    154.     int ans = kruskal(graph, n);
    155.  
    156.     printf("--------------------------------------------------------------------------\n\n");
    157.     printf("最小生成树的邻接矩阵表示：\n");
    158.     for (int i = 1; i <= n; i++)
    159.     {
    160.         for (int j = 1; j <= n; j++)
    161.         {
    162.             printf("%d ", mintree[i][j]);
    163.         }printf("\n");
    164.     }printf("\n");
    165.  
    166.     printf("加入一条新边 2--4，权值为1\n\n");
    167.     //加入一条新边 2-4 ，权值为1
    168.     Add_newedge(2, 4, 1, ans);
    169.     return 0; 
    170. }

    对于下图来说：

    加入一条新边后：

     上述代码的打印结果为：

    次小生成树

    只要会了 “加入一条新边，求新的最小生成树” 这题的话，求次小生成树就不难了，思路基本一致，只是稍微改动一些地方。

    大致思路：先求得最小生成树，然后枚举图中未加入最小生成树的各条边， 在最小生成树中加入一条新边 newa -- newb（权值为neww），肯定会构成一个环，然后找到环中除了新边 newa -- newb 之外最长的一条边的权值，也就是在原先的最小生成树中从节点newa到节点newb的路径上最长的一条边的权值maxw，我们就可以直接用这条新边代替原先的最长边（注意，如果求的是严格次小的话，需要比较neww和maxw的大小，只有neww ≠ maxw时才用新边代替原先的最长边），得到一棵新的生成树；在所有的新生成树中最小的那棵，就是次小生成树。

    在main函数中枚举未加入最小生成树的边，调用Add_edge函数：

    1.     int newans = 999;
    2.     for (int i = 1; i <= edgenum; i++)
    3.     {
    4.         if (!isuse[i])    //枚举未加入最小生成树的边
    5.         {
    6.             int tmp = Add_newedge(edge[i][0], edge[i][1], edge[i][2], ans);
    7.             if (newans > tmp) newans = tmp;
    8.         }
    9.     }
    10.     printf("次小生成树的权值为：%d\n", newans);

    完整的代码如下：

    1. #define maxsize 100
    2.  
    3. int father[maxsize] = { 0 };
    4. int Find(int x)
    5. {
    6.     if (father[x] <= 0) return x;
    7.     return father[x] = Find(father[x]);
    8. }
    9. void Union(int x, int y)
    10. {
    11.     int fx = Find(x);
    12.     int fy = Find(y);
    13.     if (fx == fy) return;
    14.     if (father[fx] < father[fy])
    15.     {
    16.         father[fy] = fx;
    17.     }
    18.     else
    19.     {
    20.         if (father[fx] == father[fy])
    21.         {
    22.             father[fy]--;
    23.         }
    24.         father[fx] = fy;
    25.     }
    26. }
    27. //对边进行排序，并存入edge数组中
    28. int sort_edge(int graph[][6], int n, int edge[][3])
    29. {
    30.     int edgenum = 0;  //k为边的数量
    31.     for (int i = 1; i <= n; i++)
    32.     {
    33.         for (int j = i + 1; j <= n; j++)
    34.         {
    35.             if (graph[i][j])
    36.             {
    37.                 edgenum++;
    38.                 edge[edgenum][0] = i;
    39.                 edge[edgenum][1] = j;
    40.                 edge[edgenum][2] = graph[i][j];
    41.             }
    42.         }
    43.     }
    44.     for (int i = edgenum; i > 1; i--)
    45.     {
    46.         int flag = 0;
    47.         for (int j = 1; j < i; j++)
    48.         {
    49.             if (edge[j][2] > edge[j + 1][2])
    50.             {
    51.                 flag = 1;
    52.  
    53.                 int tmp[3];
    54.                 memcpy(tmp, edge[j], sizeof(int) * 3);
    55.                 memcpy(edge[j], edge[j + 1], sizeof(int) * 3);
    56.                 memcpy(edge[j + 1], tmp, sizeof(int) * 3);
    57.             }
    58.         }
    59.         if (!flag) break;
    60.     }
    61.     printf("排序后的边为：");
    62.     for (int i = 1; i <= edgenum; i++)
    63.     {
    64.         printf("%d--%d:%d  ", edge[i][0], edge[i][1], edge[i][2]);
    65.     }printf("\n\n");
    66.     return edgenum;
    67. }
    68.  
    69. int mintree[maxsize][maxsize] = { 0 };        //用邻接矩阵的方式存储最小生成树
    70. int n = 5;
    71. //找到形成的环中，除新加入的边 a-b 外，最长的一条边的权值
    72. //即在原先的生成树中，从节点a到节点b的路径上最长的一条边的权值
    73. void dfs(int v, int b, int visited[], int curw, int* maxw)      //curw是从节点a到当前节点v的路径上最长的一条边的权值
    74. {
    75.     visited[v] = 1;
    76.     if (v == b)     //如果找到了b节点
    77.     {
    78.         //为什么这个代码需要curw，而不是直接用一个maxw记录所遇到的最大的边的权值呢？
    79.         //原因就在这里，只有在遇到终点b时才能确定max的值就是a到b的路径上最大的边的权值
    80.         //如果按照前者的思路只用一个maxw的话，那记录的不就是生成树中最大的边的权值了？显然不合理
    81.         *maxw = curw;
    82.         return;
    83.     }
    84.     for (int i = 1; i <= n; i++)
    85.     {
    86.         if (mintree[v][i] != 0 && !visited[i])
    87.         {
    88.             int temp = curw;    //记录一下原先curw的值，用于回溯
    89.             if (mintree[v][i] > curw) curw = mintree[v][i];
    90.             dfs(i, b, visited, curw, maxw);
    91.             curw = temp;        //回溯
    92.         }
    93.     }
    94. }
    95. //向图中加入一条新边后，求最小生成树
    96. int Add_newedge(int newa, int newb, int neww, int ans)
    97. {
    98.     int visited[maxsize] = { 0 };
    99.     int maxw;    //存储最长边的权值
    100.     dfs(newa, newb, visited, 0, &maxw);
    101.     printf("在原先的最小生成树中，节点%d到节点%d的路径上的最长边的权值为：%d\n", newa, newb, maxw);
    102.     ans = ans - maxw + neww;
    103.     printf("加入边 %d--%d 后，新的最小生成树的权值为：%d\n\n", newa, newb, ans);
    104.     return ans;
    105. }
    106.  
    107. int edge[maxsize][3];       //存储边的数组
    108. int edgenum;                //边数
    109. int isuse[maxsize] = { 0 }; //标记某个边是否被用来加入最小生成树
    110. int kruskal(int graph[][6], int n)
    111. {
    112.     edgenum = sort_edge(graph, n, edge);
    113.     int T = n;    //集合的个数
    114.     int k = 1;
    115.     int ans = 0;
    116.     printf("最小生成树：");
    117.     while (T > 1)
    118.     {
    119.         int a = edge[k][0];
    120.         int b = edge[k][1];
    121.         int w = edge[k][2];
    122.         k++;
    123.  
    124.         if (Find(a) == Find(b)) continue;
    125.         Union(a, b);
    126.         T--;
    127.         ans += w;
    128.         mintree[a][b] = mintree[b][a] = w;
    129.         isuse[k - 1] = 1;
    130.         printf("%d--%d:%d  ", a, b, w);
    131.     }printf("\n\n");
    132.     printf("最小生成树的权值为：%d\n\n", ans);
    133.     return ans;
    134. }
    135.  
    136. int main()
    137. {
    138.     int graph[6][6] = { 0 };
    139.     int n = 5;
    140.     graph[1][4] = 1;    graph[4][1] = 1;
    141.     graph[1][3] = 2;    graph[3][1] = 2;
    142.     graph[1][2] = 3;    graph[2][1] = 3;
    143.     graph[3][4] = 4;    graph[4][3] = 4;
    144.     graph[4][5] = 5;    graph[5][4] = 5;
    145.     graph[2][5] = 6;    graph[5][2] = 6;
    146.     printf("原图：\n");
    147.     for (int i = 1; i <= n; i++)
    148.     {
    149.         for (int j = 1; j <= n; j++)
    150.         {
    151.             printf("%d ", graph[i][j]);
    152.         }printf("\n");
    153.     }printf("\n");
    154.  
    155.     int ans = kruskal(graph, n);
    156.  
    157.     printf("--------------------------------------------------------------------------\n\n");
    158.     printf("最小生成树的邻接矩阵表示：\n");
    159.     for (int i = 1; i <= n; i++)
    160.     {
    161.         for (int j = 1; j <= n; j++)
    162.         {
    163.             printf("%d ", mintree[i][j]);
    164.         }printf("\n");
    165.     }printf("\n");
    166.  
    167.     int newans = 999;
    168.     for (int i = 1; i <= edgenum; i++)
    169.     {
    170.         if (!isuse[i])    //枚举未加入最小生成树的边
    171.         {
    172.             int tmp = Add_newedge(edge[i][0], edge[i][1], edge[i][2], ans);
    173.             if (newans > tmp) newans = tmp;
    174.         }
    175.     }
    176.     printf("次小生成树的权值为：%d\n", newans);
    177.  
    178.     return 0;
    179. }

    对于下图来说：

    其次小生成树为：

     ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        

    上述的代码的打印结果为：

    判断最小生成树是否唯一

    可以用求次小生成树的办法，如果次小生成树的权值与最小生成树的权值相同，就说明最小生成树不唯一，但是这题倒不用这么复杂。

    原理： 如果无向图中各边的权值各不相同，那么用Kruskal算法构造的最小生成树是惟一的，因此在无向图中存在相同权值的边是最小生成树不唯一的必要非充分条件。

    大致思路：在使用Kruskal算法时，如果有两条边的权值相同，并且都能将两个相同的连通块合并，那么这两条边选择哪个都行，于是最小生成树就不唯一了。

    只要在kruskal算法的基础上，改一下kruskal函数即可：

    1. //kruskal算法
    2. void kruskal(int graph[][6], int n)
    3. {
    4.     int edge[maxsize][3];
    5.     int edgenum = sort_edge(graph, n, edge);
    6.     int T = n;    //集合的个数
    7.     int k = 1;
    8.     int ans = 0;
    9.     //printf("最小生成树：");
    10.     while (T > 1)
    11.     {
    12.         int a = edge[k][0];
    13.         int b = edge[k][1];
    14.         int w = edge[k][2];
    15.         k++;
    16.  
    17.         if (Find(a) == Find(b)) continue;
    18.         //由于边是降序排序的，因此可以往后查找与当前的边权值相同的边
    19.         for (int i = k; i <= edgenum; i++)
    20.         {
    21.             if (edge[i][2] == w)    //如果 a--b 和 newa--newb 这两边权值相同
    22.             {
    23.                 int newa = edge[i][0];
    24.                 int newb = edge[i][1];
    25.                 //并且两边所处的两个连通块都一样，就说明最小生成树不唯一（注意，这里有两种情况，都要判断）
    26.                 if (Find(a) == Find(newa) && Find(b) == Find(newb) || Find(a) == Find(newb) && Find(b) == Find(newa))
    27.                 {
    28.                     printf("边 %d--%d 与边 %d-- %d 可任意选，最小生成树不唯一\n", a, b, newa, newb);
    29.                     return;
    30.                 }
    31.             }
    32.         }
    33.         Union(a, b);
    34.         T--;
    35.         ans += w;
    36.         //printf("%d--%d:%d  ", a, b, w);
    37.     }printf("\n\n");
    38.     printf("最小生成树的权值为：%d\n", ans);
    39. }

    完整的代码如下：

    1. #define maxsize 100
    2.  
    3. //并查集
    4. int father[maxsize] = { 0 };
    5. int Find(int x)
    6. {
    7.     if (father[x] <= 0) return x;
    8.     return father[x] = Find(father[x]);
    9. }
    10. void Union(int x, int y)
    11. {
    12.     int fx = Find(x);
    13.     int fy = Find(y);
    14.     if (fx == fy) return;
    15.     if (father[fx] < father[fy])
    16.     {
    17.         father[fy] = fx;
    18.     }
    19.     else
    20.     {
    21.         if (father[fx] == father[fy])
    22.         {
    23.             father[fy]--;
    24.         }
    25.         father[fx] = fy;
    26.     }
    27. }
    28. //对边进行排序，并存入edge数组中
    29. int sort_edge(int graph[][6], int n, int edge[][3])
    30. {
    31.     int edgenum = 0;  //k为边的数量
    32.     for (int i = 1; i <= n; i++)
    33.     {
    34.         for (int j = i + 1; j <= n; j++)
    35.         {
    36.             if (graph[i][j])
    37.             {
    38.                 edgenum++;
    39.                 edge[edgenum][0] = i;
    40.                 edge[edgenum][1] = j;
    41.                 edge[edgenum][2] = graph[i][j];
    42.             }
    43.         }
    44.     }
    45.     for (int i = edgenum; i > 1; i--)
    46.     {
    47.         int flag = 0;
    48.         for (int j = 1; j < i; j++)
    49.         {
    50.             if (edge[j][2] > edge[j + 1][2])
    51.             {
    52.                 flag = 1;
    53.  
    54.                 int tmp[3];
    55.                 memcpy(tmp, edge[j], sizeof(int) * 3);
    56.                 memcpy(edge[j], edge[j + 1], sizeof(int) * 3);
    57.                 memcpy(edge[j + 1], tmp, sizeof(int) * 3);
    58.             }
    59.         }
    60.         if (!flag) break;
    61.     }
    62.     printf("排序后的边为：");
    63.     for (int i = 1; i <= edgenum; i++)
    64.     {
    65.         printf("%d--%d:%d  ", edge[i][0], edge[i][1], edge[i][2]);
    66.     }printf("\n\n");
    67.     return edgenum;
    68. }
    69. //kruskal算法
    70. void kruskal(int graph[][6], int n)
    71. {
    72.     int edge[maxsize][3];
    73.     int edgenum = sort_edge(graph, n, edge);
    74.     int T = n;    //集合的个数
    75.     int k = 1;
    76.     int ans = 0;
    77.     //printf("最小生成树：");
    78.     while (T > 1)
    79.     {
    80.         int a = edge[k][0];
    81.         int b = edge[k][1];
    82.         int w = edge[k][2];
    83.         k++;
    84.  
    85.         if (Find(a) == Find(b)) continue;
    86.         //由于边是降序排序的，因此可以往后查找与当前的边权值相同的边
    87.         for (int i = k; i <= edgenum; i++)
    88.         {
    89.             if (edge[i][2] == w)    //如果 a--b 和 newa--newb 这两边权值相同
    90.             {
    91.                 int newa = edge[i][0];
    92.                 int newb = edge[i][1];
    93.                 //并且两边所处的两个连通块都一样，就说明最小生成树不唯一（注意，这里有两种情况，都要判断）
    94.                 if (Find(a) == Find(newa) && Find(b) == Find(newb) || Find(a) == Find(newb) && Find(b) == Find(newa))
    95.                 {
    96.                     printf("边 %d--%d 与边 %d-- %d 可任意选，最小生成树不唯一\n", a, b, newa, newb);
    97.                     return;
    98.                 }
    99.             }
    100.         }
    101.         Union(a, b);
    102.         T--;
    103.         ans += w;
    104.         //printf("%d--%d:%d  ", a, b, w);
    105.     }printf("\n\n");
    106.     printf("最小生成树的权值为：%d\n", ans);
    107. }
    108.  
    109. int main()
    110. {
    111.     int graph[6][6] = { 0 };
    112.     int n = 5;
    113.     graph[1][4] = 1;    graph[4][1] = 1;
    114.     graph[1][3] = 2;    graph[3][1] = 2;
    115.     graph[1][2] = 3;    graph[2][1] = 3;
    116.     graph[3][4] = 4;    graph[4][3] = 4;
    117.     graph[4][5] = 5;    graph[5][4] = 5;
    118.     graph[2][5] = 6;    graph[5][2] = 6;
    119.     graph[2][4] = 3;    graph[4][2] = 3;
    120.     for (int i = 1; i <= n; i++)
    121.     {
    122.         for (int j = 1; j <= n; j++)
    123.         {
    124.             printf("%d ", graph[i][j]);
    125.         }printf("\n");
    126.     }printf("\n");
    127.  
    128.     kruskal(graph, n);
    129.     return 0;
    130. }

    对于下图来说：

            ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        

     上述代码的打印结果为：

    极差最小的生成树

    题意及分析：

    为什么要用最小生成树的方法来做呢？根据kruskal算法的思想，我们可以知道以第 i 条边为最小边所构造出来的最小生成树，它的最大边一定是相对于第 i 条边来说“最小”的最大边，所以极差也是相对于第 i 条边来说“最小”的极差。 

    这里的第一点我不知道如何证明是否正确，因此没有实现。

    第二点可用反证法：假设后续以第 i+1 条边为最小边能够构造一棵最小生成树，那么我们可以采用前面写“次小生成树”的思想，将第i条边加入并去掉环中其余的一条边，就得到了一棵以第 i 条边为最小边的最小生成树，这与前面的假设相矛盾，该假设不成立。因此用第 i 条边以后的边都无法构造出最小生成树。

    只要改一下kruskal算法即可：

    1. //用kruskal算法计算极差
    2. void mingap_kruskal(int graph[][6], int n)
    3. {
    4.     int edge[maxsize][3];
    5.     int edgenum = sort_edge(graph, n, edge);
    6.     int T = n;    //集合的个数
    7.     int k;
    8.     int mingap = 999;   //记录最小的极差
    9.     int ans = 0;
    10.     //枚举，依次构造以edge[i]为最小边的最小生成树，计算他们各自的极差，得到最小的极差
    11.     for (int i = 1; i < edgenum; i++)
    12.     {
    13.         printf("以 %d--%d 为最小边的最小生成树：", edge[i][0], edge[i][1]);
    14.         k = i;
    15.         T = n;
    16.         ans = 0;
    17.         int gap = 0;    //记录当前这棵最小生成树的极差
    18.         for (int j = 1; j <= n; j++) father[j] = 0;     //每次枚举之前，记得将并查集回溯
    19.         int flag = 1;
    20.         while (T > 1)
    21.         {
    22.             //如果以edge[i]为最小边的情况下，不能构成最小生成树，那么说明后续也无法构成最小生成树了，退出while循环和for循环
    23.             if (k > edgenum && T > 1)
    24.             {
    25.                 flag = 0;
    26.                 break;
    27.             }
    28.             int a = edge[k][0];
    29.             int b = edge[k][1];
    30.             int w = edge[k][2];
    31.             k++;
    32.  
    33.             if (Find(a) == Find(b)) continue;
    34.             Union(a, b);
    35.             T--;
    36.             if (T == 1) //如果构成了一棵最小生成树，就计算这棵最小生成树的极差
    37.             {
    38.                 gap = w - edge[i][2];   //最小边是edge[i]，而最大边肯定是当前这条边
    39.                 if (gap < mingap) mingap = gap;
    40.             }
    41.             ans += w;
    42.             printf("%d--%d:%d  ", a, b, w);
    43.         }printf("\n");
    44.         if (!flag)
    45.         {
    46.             printf("构造失败\n");
    47.             break;
    48.         }
    49.         printf("这棵最小生成树的权值为：%d，极差为：%d\n\n", ans, gap);
    50.     }printf("\n");
    51.     printf("最小的极差为：%d\n", mingap);
    52. }

    完整的代码如下：

    1. #define maxsize 100
    2.  
    3. //并查集
    4. int father[maxsize] = { 0 };
    5. int Find(int x)
    6. {
    7.     if (father[x] <= 0) return x;
    8.     return father[x] = Find(father[x]);
    9. }
    10. void Union(int x, int y)
    11. {
    12.     int fx = Find(x);
    13.     int fy = Find(y);
    14.     if (fx == fy) return;
    15.     if (father[fx] < father[fy])
    16.     {
    17.         father[fy] = fx;
    18.     }
    19.     else
    20.     {
    21.         if (father[fx] == father[fy])
    22.         {
    23.             father[fy]--;
    24.         }
    25.         father[fx] = fy;
    26.     }
    27. }
    28. //对边进行排序，并存入edge数组中
    29. int sort_edge(int graph[][6], int n, int edge[][3])
    30. {
    31.     int edgenum = 0;  //k为边的数量
    32.     for (int i = 1; i <= n; i++)
    33.     {
    34.         for (int j = i + 1; j <= n; j++)
    35.         {
    36.             if (graph[i][j])
    37.             {
    38.                 edgenum++;
    39.                 edge[edgenum][0] = i;
    40.                 edge[edgenum][1] = j;
    41.                 edge[edgenum][2] = graph[i][j];
    42.             }
    43.         }
    44.     }
    45.     for (int i = edgenum; i > 1; i--)
    46.     {
    47.         int flag = 0;
    48.         for (int j = 1; j < i; j++)
    49.         {
    50.             if (edge[j][2] > edge[j + 1][2])
    51.             {
    52.                 flag = 1;
    53.  
    54.                 int tmp[3];
    55.                 memcpy(tmp, edge[j], sizeof(int) * 3);
    56.                 memcpy(edge[j], edge[j + 1], sizeof(int) * 3);
    57.                 memcpy(edge[j + 1], tmp, sizeof(int) * 3);
    58.             }
    59.         }
    60.         if (!flag) break;
    61.     }
    62.     printf("排序后的边为：");
    63.     for (int i = 1; i <= edgenum; i++)
    64.     {
    65.         printf("%d--%d:%d  ", edge[i][0], edge[i][1], edge[i][2]);
    66.     }printf("\n\n");
    67.     return edgenum;
    68. }
    69. //用kruskal算法计算极差
    70. void mingap_kruskal(int graph[][6], int n)
    71. {
    72.     int edge[maxsize][3];
    73.     int edgenum = sort_edge(graph, n, edge);
    74.     int T = n;    //集合的个数
    75.     int k;
    76.     int mingap = 999;   //记录最小的极差
    77.     int ans = 0;
    78.     //枚举，依次构造以edge[i]为最小边的最小生成树，计算他们各自的极差，得到最小的极差
    79.     for (int i = 1; i < edgenum; i++)
    80.     {
    81.         printf("以 %d--%d 为最小边的最小生成树：", edge[i][0], edge[i][1]);
    82.         k = i;
    83.         T = n;
    84.         ans = 0;
    85.         int gap = 0;    //记录当前这棵最小生成树的极差
    86.         for (int j = 1; j <= n; j++) father[j] = 0;     //每次枚举之前，记得将并查集回溯
    87.         int flag = 1;
    88.         while (T > 1)
    89.         {
    90.             //如果以edge[i]为最小边的情况下，不能构成最小生成树，那么说明后续也无法构成最小生成树了，退出while循环和for循环
    91.             if (k > edgenum && T > 1)
    92.             {
    93.                 flag = 0;
    94.                 break;
    95.             }
    96.             int a = edge[k][0];
    97.             int b = edge[k][1];
    98.             int w = edge[k][2];
    99.             k++;
    100.  
    101.             if (Find(a) == Find(b)) continue;
    102.             Union(a, b);
    103.             T--;
    104.             if (T == 1) //如果构成了一棵最小生成树，就计算这棵最小生成树的极差
    105.             {
    106.                 gap = w - edge[i][2];   //最小边是edge[i]，而最大边肯定是当前这条边
    107.                 if (gap < mingap) mingap = gap;
    108.             }
    109.             ans += w;
    110.             printf("%d--%d:%d  ", a, b, w);
    111.         }printf("\n");
    112.         if (!flag)
    113.         {
    114.             printf("构造失败\n");
    115.             break;
    116.         }
    117.         printf("这棵最小生成树的权值为：%d，极差为：%d\n\n", ans, gap);
    118.     }printf("\n");
    119.     printf("最小的极差为：%d\n", mingap);
    120. }
    121.  
    122. int main()
    123. {
    124.     int graph[6][6] = { 0 };
    125.     int n = 5;
    126.     graph[1][4] = 1;    graph[4][1] = 1;
    127.     graph[1][3] = 2;    graph[3][1] = 2;
    128.     graph[1][2] = 3;    graph[2][1] = 3;
    129.     graph[3][4] = 4;    graph[4][3] = 4;
    130.     graph[4][5] = 5;    graph[5][4] = 5;
    131.     graph[2][5] = 6;    graph[5][2] = 6;
    132.     for (int i = 1; i <= n; i++)
    133.     {
    134.         for (int j = 1; j <= n; j++)
    135.         {
    136.             printf("%d ", graph[i][j]);
    137.         }printf("\n");
    138.     }printf("\n");
    139.  
    140.     mingap_kruskal(graph, n);
    141.     return 0;
    142. }

    对于下图来说：

            ​​​​​​​        ​​​​​​​        ​​​​​​​        

    上述代码的打印结果为：

  • 相关阅读:
    智能文档控制——文档的智能归档、捕获、索引、访问和协作
    2023-2024 计算机信息安全专业毕设题目推荐
    vue3 自动导入composition-apiI和组件
    EasyRecovery16免费版使用人数很多的数据恢复软件
    端侧需要向量数据库吗
    pytest自动化测试数据驱动yaml/excel/csv/json
    DSPE-PEG-iRGD,iRGD-PEG-DSPE,磷脂-聚乙二醇-靶向肽iRGD,一种磷脂PEG肽
    【Docker】docker网络
    搜索引擎项目
    Python 中的鸭子类型和猴子补丁
  • 原文地址：https://blog.csdn.net/weixin_52629904/article/details/126593251