最小生成树-Prim算法（参考 清华大学 《数据结构》 严蔚敏版）_最小生成树算法优化版

最小生成树

1. 最小生成树算法
   假定图的顶点构成集合V, 如果要生成最小生成树，那么就需要建立另外建立两个集合U 和 V-U, 不断更新V-U集合中的顶点到集合U之间的最小权值，直至V=U.
2. 在清华大学《数据结构》一书中，采用边数组进行跟踪的方式进行贪婪搜索，边采用结构体数据结构，包含两个分量adjvex和lowcost, 其中adjvex表示在U集合中的顶点，此顶点到序列为i的顶点是当前权值最小的边，closedge[i]元素包含边（closedge[i].adjvex , i) 和 边的权值closedge[i].lowcost. 在过程中，如果V-U集合中的某个顶点需要转移到U集合中，只需要把closedge[i].lowcost赋值为0即可。

typedef struct closedge_node
{
    VertexType adjvex;
    VRType     lowcost;
}closedge_node,close_edges[MAX_VERTEX_NUM];

close_edges closedge;
1
2
3
4
5
6
7

3. 从如下程序可知，普利姆算法的时间复杂度O(n2)，与网中边数无关，因此适用于求稠密的网的最小生成树。

/**
*@param G 		   -Matrix Graph
*@param s 		   -Start point as specified
*@param total_cost -Sum up the weight from minimum spanning tree
*@param visit      -Function pointer to print the vertex name
*/
void MST_Prim(MGraph G, int s, VRType *total_cost, void (*visit)(VertexType e))
{
    int i;
    int j;
    int k;
    close_edges closedge;
    *total_cost=0;

    k=LocateVex(G,G.vexs[s]);

    //j∈V-U, Intialize the closedge array starting from U={k}
    for(j=0;j<G.vexnum;j++)
    {
        if(j!=k) //j∈V-U
        {
            closedge[j].adjvex=G.vexs[s];
            closedge[j].lowcost=G.arcs[k][j].adj;
        }
    }

    closedge[k].lowcost=0; //Move k into the U set

    for(i=1;i<G.vexnum;i++)
    {
        //k∈V-U
        k=Minimum(G,closedge);

        visit(closedge[k].adjvex);
        printf("--");
        visit(G.vexs[k]);
        printf("\n");
        *total_cost+=closedge[k].lowcost;

        closedge[k].lowcost=0;

        // j∈V-U
        for(j=0;j<G.vexnum;j++)
        {
            //Greedy for searching the lower cost/weight
            if(G.arcs[k][j].adj<closedge[j].lowcost)
            {
                closedge[j].adjvex=G.vexs[k];
                closedge[j].lowcost=G.arcs[k][j].adj;
            }
        }
    }
}

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

int Minimum(MGraph G, close_edges closedge)
{
    int index;
    int min;
    int i;
    index=-1;
    min=INT_MAX; //INT_MAX defined in <limits.h> header file
    
    for(i=0;i<G.vexnum;i++)
    {
        if(closedge[i].lowcost!=0) //i∈V-U
        {
            if(min>closedge[i].lowcost)
            {
                min = closedge[i].lowcost;
                index=i;
            }
        }
    }
    return index;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void visit(VertexType e);

int main(void)
{
    MGraph G;
    FILE *fp;
    int s;
    VRType total_cost;

    fp=fopen("UDN.txt","r");
    s=0;
    total_cost=0;
	
	//Create the matrix graph on the basis of file
	//Reference book, <<data structure>>, Yan&Wu, TsingHua University
    CreateGraph(&G,fp);
    MST_Prim(G,s,&total_cost,visit);
    printf("\nThe total cost is %d\n",total_cost);
    PressEnter;
    return EXIT_SUCCESS;
}

void visit(VertexType e)
{
    printf("-%c-",e);
}

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

以上，谢谢！