数据结构

开发平台：

Visual C++

最小生成树的示例程序.txt：源码内容

							#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[i].vexa == from && e[i].vexb == to) { 
            return e[i].weight; 
        } 
        if (e[i].vexa == to && e[i].vexb == from) { 
            return e[i].weight; 
        } 
    } 
    return 1000;            // 用1000代表无穷大，如果图中没有这条边就返回无穷大 
} 
int main() 
{ 
    Edge e_mst[10];            // 表示已经加入最小生成树的边 
// 表示已经加入最小生成树(mst)的结点, 数组元素从0到10分别对应结点a到j 
// 如果vex_mst[i]=0，表示对应结点没有加入到mst 
// 如果vex_mst[i]=1，表示对应结点已经加入到mst 
int vex_mst[11];             
                         
    for (int i = 0; i < 11; i++)    // 初始化 
        vex_mst[i] = 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; 
    } 
}

						