| 注册
请输入搜索内容

热门搜索

Java Linux MySQL PHP JavaScript Hibernate jQuery Nginx
ngmm
10年前发布

普里姆算法求最小生成树

    #include "iostream"        using namespace std;                const int num = 9; //节点个数        #define Infinity 65535;        //本例中以节点0作为生成树的起始节点        void MinSpanTree_Prime(int graphic[num][num]){            int lowcost[num]; //记录从节点num到生成树的最短距离,如果为0则表示该节点已在生成树中            int adjvex[num]; //记录相关节点,如:adjvex[1] = 5表示最小生成树中节点1和5有路径相连            int sum = 0; // 记录最小生成树边权重之和            memset(adjvex, 0, sizeof(adjvex));            //选取0节点作为生成树的起点            for (int i = 0; i < num; i++)                lowcost[i] = graphic[0][i];                    for (int i = 1; i < num; i++){                int min = Infinity;                int index;                for (int j = 1; j < num; j++){                    if (lowcost[j] != 0 && lowcost[j] < min){                        index = j;                        min = lowcost[j];                    }                }                sum += min;                lowcost[index] = 0; //将当前节点放入生成树中                cout << adjvex[index] << " -> " << index << endl;                //修正其他节点到生成树的最短距离                for (int j = 1; j < num; j++){                    if (lowcost[j] != 0 && graphic[index][j] < lowcost[j]){                        lowcost[j] = graphic[index][j];                        adjvex[j] = index;                    }                }            }            cout << "sum = " << sum << endl;        }                int main(){            int graphic[num][num];            for (int i = 0; i < num; i++)            for (int j = 0; j < num; j++){                if (i == j)                    graphic[i][j] = 0;                else                    graphic[i][j] = Infinity;            }            graphic[0][1] = 1;            graphic[0][2] = 5;            graphic[1][0] = 1;            graphic[1][2] = 3;            graphic[1][3] = 7;            graphic[1][4] = 5;            graphic[2][0] = 5;            graphic[2][1] = 3;            graphic[2][4] = 1;            graphic[2][5] = 7;            graphic[3][1] = 7;            graphic[3][4] = 2;            graphic[3][6] = 3;            graphic[4][1] = 5;            graphic[4][2] = 1;            graphic[4][3] = 2;            graphic[4][5] = 3;            graphic[4][6] = 6;            graphic[4][7] = 9;            graphic[5][2] = 7;            graphic[5][4] = 3;            graphic[5][7] = 5;            graphic[6][3] = 3;            graphic[6][4] = 6;            graphic[6][7] = 2;            graphic[6][8] = 7;            graphic[7][4] = 9;            graphic[7][5] = 5;            graphic[7][6] = 2;            graphic[7][8] = 4;            graphic[8][6] = 7;            graphic[8][7] = 4;                    MinSpanTree_Prime(graphic);                    return 0;        }