7.6 最小生成树

7.6 最小生成树

什么是最小生成树呢?

什么是最小生成树呢?

即构造连通图的最小代价生成树,就是能够到达每个点,花费最少的路径

7.6.1 Prim算法

Kw73hd.jpg

1.代码:

邻接矩阵结构:

#define MAXVER 10
typedef char VertexType;

typedef struct 
{
    VertexType vexs[MAXVER];
    int arc[MAXVER][MAXVER];
    int numVertexes, numEdges;
}MGraph;
/* Prim 算法生成最小生成树 */
void MiniSpanTree_Prim(MGraph G)
{
    int min, i, j, k;  // min 为当前权值最小值
    int lowcost[MAXVEX];  /* 保存顶点间边的权值 */
    int adjvex[MAXVEX];   /* 保存相关顶点的下标,即下标与其值所连边为当前最小权值边 */
    lowcost[0] = 0;  /* 选取第一个顶点为起始点, 即 v0 加入树, lowcost的值为0,在这里就是此下标的顶点已经加入生成树 */
    adjvex[0] = 0;   /* 初始化第一个顶点下标为0 */
    for(i = 1; i < G.numVertexes; i++)  /* 循环除下标为 0 外的全部顶点 */
    {
        lowcost[i] = G.arc[0][i];  /* 将与 v0 顶点有边的权值存入数组 */
        adjvex[i] = 0;  /* 将其他所有顶点的值初始化为 v0 的下标 */
    }
    for(i = 1; i < G.numVertexes; i++)
    {
        min = INF;   /* 初始化最小权值为 无穷大 */
        j = 1, k = 0;
        while(j < G.numVertexes)  /* 循环全部顶点,寻找当前最小生成树顶点集合中最小权值的边 */
        {
            if(lowcost[j] != 0 && lowcost[j] < min)  /* 如果权值不为 0(即不在树中), 且权值小于 min */
            {
                min = lowcost[j];  /* 则让当前权值成为最小值 */
                k = j;             /* 将当前最小值的下标存入k */
            }
            j++;
        }
        lowcost[k] = 0;  /* 将当前顶点的权值设置为0, 表示此顶点已加入树的顶点集合 */
        printf("(%d, %d)", adjvex[k], k);  /* 打印当前顶点边中权值最小的边 */
        for(j = 1; j < G.numVertexes; j++)  /* 循环所有顶点 */
        {
            /* 如果下标为 k 的顶点边集中权值小于已存在的权值, 比如 (v0, v6)权值为INF, 而(v1, v6)权值为 16, 更新*/
            if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
            {
                lowcost[j] = G.arc[k][j];  /* 将较小的权值存入 lowcost 相应位置 */
                adjvex[j] = k;   /* 将下标为 k 的顶点存入 adjvex */
            }
        }
    }
}

lowcost其实存着最小的权,当lowcost==0的时候,说明该结点已经放入最小生成树中了

adjvex其实存在点,

2.复杂度

时间复杂度是O(n2)

7.6.2 Kruskal算法

1.什么是克鲁斯卡尔算法

按照权值从小到大的顺序选择n - 1条边,并保证这n - 1条边不构成回路

2.思路是怎样的?

  1. 将邻接矩阵转化为边集数组
  2. 构造一个只含n个顶点的森林,
  3. 然后依权值从小到大从连通网中选择边加入到森林中,并使森林不产生回路,直至森林变成过一棵树为止

KwbbTO.jpg

3.具体算法

边集数组结构

typedef struct
{
    int begin;
    int end;
    int weight;
}Edge;

算法

/* 生成最小生成树 */
void MiniSpanTree_Kruskal(MGraph G)
{
    int i, j, n, m;
    int k = 0;
    int parent[MAXVEX];  /* 定义一数组用来判断边与边是否形成环路 */
    Edge edges[MAXEDGE];  /* 定义边集数组,edge的结构为begin,end,weight,均为整型 */

    /* 用来构建边集数组并排序********************* */
    for(i = 0; i < G.numVertexes - 1; i++)
    {
        for(j = i + 1; j < G.numVertexes; j++)
        {
            if(G.arc[i][j] < INF)
            {
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = G.arc[i][j];
                k++;
            }
        }
    }
    sort(edges, &G);
    /* ******************************************* */

    printf("打印最小生成树:\n");

    for(i = 0; i < G.numVertexes; i++)
        parent[i] = 0;  /* 初始化数组值为0 */

    for(i = 0; i < G.numEdges; i++)  /* 循环每一条边 */
    {
        n = Find(parent, edges[i].begin);
        m = Find(parent, edges[i].end);
        if(n != m)  /* 假如n与m不等,说明此边没有与现有的生成树形成环路 */
        {
            parent[n] = m;  /* 将此边的结尾顶点放入下标为起点的parent中。 表示此顶点已经在生成树集合中*/
            printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
        }
    }

}

//Kruskal(克鲁斯卡尔算法)生成最小生成树
int Find(int *parent, int f)
{
   while(parent[f]>0)
   {
       f = parent[f];
   }
   return f;
}

其中,如果已经加入的话,parent[5]=8表示(5,8)在边集合里面


  目录