求出最小生成树的示例程序

kj501

这是我在看数据结构时做的练习，今天从硬盘里找出来的。
[php]
// 采用Prim算法
// 在Mandrake Linux 9.1下，gcc version 3.2.2 (Mandrake Linux 9.1 3.2.2-3mdk) 下// 编译通过
// 编译命令：将源程序保存为pro7.cpp，然后在控制台下用g++ pro7.cpp编译

#include<iostream>
using namespace std;

// 用结构表示边
struct  Edge {
        char vexa;                // 边的起点
        char vexb;                // 边的终点
        int weight;                // 边的权植
};

// 初始化图
        Edge e[18] = { {'a','b',2}, {'b','c',1} ,{'c','d',2},{'d','e',9},
                                {'e','f',4},{'f','g',1},{'g','h',9},{'h','a',1},
                                {'a','i',8},{'b','i',6},{'c','j',3},{'d','k',7},                                                        {'e','k',2},{'f','k',1},{'g','j',4},{'h','i',7},
{'i','j',1},{'j','k',6}};

// w函数返回起点序号为x，终点序号为y的边的权植。如果没有这条边就返回无穷大
int w( int x, int y)
{
        char from = x + 97;
        char to = y + 97;

        for (int i = 0; i < 18; i++) {
                if (e.vexa == from && e.vexb == to) {
                        return e.weight;
                }
                if (e.vexa == to && e.vexb == from) {
                        return e.weight;
                }
        }
        return 1000;                        // 用1000代表无穷大，如果图中没有这条边就返回无穷大
}

int main()
{

        Edge e_mst[10];                        // 表示已经加入最小生成树的边

// 表示已经加入最小生成树(mst)的结点, 数组元素从0到10分别对应结点a到j
// 如果vex_mst=0，表示对应结点没有加入到mst
// 如果vex_mst=1，表示对应结点已经加入到mst
int vex_mst[11];                       
                                               
        for (int i = 0; i < 11; i++)        // 初始化
                vex_mst = 0;

        vex_mst[0] = 1;                        // 设置初始结点为a

        // 将10条边加入到最小生成树
        for (int i = 0; i < 10; i++) {
                // 加入一条边。
// 这条边的两个结点一个在mst中，而另一个不在mst中而且具有最小权植
                int add_vex;                                        // 选中的结点
                int min_weight = 1000;                        // 最小权植,初始值为1000
                Edge adde;
                for (int j = 0; j < 11; j++)
                        if (vex_mst[j] == 1) {                        // j是mst中的结点
                                for (int k = 0; k < 11; k++) {
                                        if (vex_mst[k] == 0 && w(j, k) < min_weight ) {
                                                add_vex = k;
                                                min_weight = w(j, k);
                                                adde.vexa = j + 97;
                                                adde.vexb = k + 97;
                                                adde.weight = min_weight;
                                        }
                                }
                        }
                vex_mst[add_vex] = 1;                                //将选择的结点加入mst
                char avex = add_vex + 97;                        // 将选择的边加入mst
                cout<<"addvex:"<<avex<<endl;
                // 输出加入mst的顶点，边，以及边的权植
                cout<<"addedge:"<<adde.vexa<<"-"<<adde.vexb<<" w:"<<adde.weight<<endl;
        }
}
[/php]
下面为程序所引用的图：

baif

2. ACSII-en-ed  :P
4.      b--1-c---2--d
5.     /|    |      |\
6.    2 6    3      7 9
7.   /  |    |      |  \
8. a----i--1-j--6---k---e
9. \   |    |      |  /
10.   1  7    4      1 4
11.    \ |    |      |/
12.      h--9-g--1---f

复制代码