普里姆算法求最小生成树

    #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;  
    }  

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。