QeuroIzoのBlog

hello world

0%

56. 最小生成树

发表于

  • 普里姆（Prim）算法

1. 构造邻接矩阵

  1. 结构体
    1
    2
    3
    4
    5
    6
    7
    8
    9
    typedef char VertexType;
    typedef int EdgeType;
    #define MAXVEX 100
    #define INFINITY 0x3f3f3f3f // 在程序设计中，将无穷大设为0x3f3f3f3f
    typedef struct {
        VertexType vexs[MAXVEX];
        EdgeType arc[MAXVEX][MAXVEX];
        int numVertexes, numEdges;
    }MGraph;
  2. 实例化邻接矩阵
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    MGraph G;
    memset(G.arc, 0x3f, sizeof(G.arc));
    int N;
    cout << "请输入有多少条边：";
    cin >> N;
    for (int i = 0; i < N; i++) {
        int ti, tj, va;
        cin >> ti >> tj >> va;
        G.arc[ti][tj] = va;
        G.arc[tj][ti] = va;
    }

    2. 生成最小生成树

    1. 步骤：

  3. 随机将一个点作为生成树的顶点，这里以$V_0$为顶点；
  4. 将各点与$V_0$的距离保存到 lowcost 数组中；
  5. adjvex 用来存储各个顶点的值，用来看是哪个点与接下来的哪个点相连的；
  6. lowcost 存储各个顶点是否为生成树顶点；
  7. 遍历数组 lowcost ，找到与顶点 $V_0$最短的边，并将对应的顶点，添加到生成树中；
  8. 接着，将下一个顶点与$V_0$看成整体 O，更新 lowcost 的值（更新其他顶点与 O 的更短的距离）;
  9. 直到数组 lowcost 全部为0。

    2. 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
  * Prim算法生成最小生成树 
  */
void MiniSpanTree_Prim(MGraph G)
{
    int min, lowcost[MAXVEX], adjvex[MAXVEX];
    lowcost[0] = 0; // 以v0作为生成树的顶点
    for (int i = 1; i < G.numVertexes; i++) {
        lowcost[i] = G.arc[0][i]; // [0][i]  是因为v0为生成树的顶点
        adjvex[i] = 0; //这里为0，是因为以V0作为生成树的顶点
    }

    for (int i = 1; i < G.numVertexes; i++) {
        int j = 1, k = 0;
        min = 0x3f3f3f3f;
        while (j < G.numVertexes) {
            if (lowcost[j] != 0 && min > lowcost[j]) {
                min = lowcost[j];
                k = j;
            }
            j++;
        }
        printf("(%d, %d), %d", adjvex[k], k, min);
        
        lowcost[k] = 0;
        // 更新lowcost
        for (int j = 1; j < G.numVertexes; j++) {
            if (lowcost[j] != 0 && lowcost[j] > G.arc[k][j]) {
                adjvex[j] = k;
                lowcost[j] = G.arc[k][j];
            }
        }
    }   
}

  • 克鲁斯卡尔（Kruskal）算法

    1. 步骤：

  1. 判断该边添加上之后是否会使生成树生成回路，由于该边是与其两端点有关系，因此，判断该点是否在生成树中即可；
  2. 用一个数组标明