• prim算法用于生成最小生成树

• 代码

#include<iostream>
#include<string.h>
using namespace std;

#define len 100
#define INF 999999

class Graph{
    // 内部类
    private:
        // 邻接表中表对应的链表的顶点
        class ENode{
            public:
                int vex;         // 顶点
                int weight;      // 权重 
                ENode *nextEdge; // 指向下一条弧
        };

        // 邻接表中表的顶点
        class VNode{
            public:
                char data; // 顶点信息
                ENode *firstEdge; // 指向第一条依付该顶点的弧
        };

    // 私有成员
    private:
        int n;              // 节点个数 
        int e;              // 边的个数
        VNode mVexs[len];
    
    public:
        Graph(){
            ENode *node1, *node2;
            n = 7; 
            e = 12;

            // 设置节点为默认数值
            string nodes = "ABCDEFG";
            // 输入节点
            for(int i=0; i < n; i++){
                mVexs[i].data = nodes[i];
                mVexs[i].firstEdge = NULL;
            }

            // 设置边为默认值
            char edges[][2] = {
                {'A', 'B'}, 
                {'A', 'F'}, 
                {'A', 'G'}, 
                {'B', 'C'}, 
                {'B', 'F'}, 
                {'C', 'D'}, 
                {'C', 'E'},
                {'C', 'F'}, 
                {'D', 'E'},
                {'E', 'F'}, 
                {'E', 'G'},
                {'F', 'G'}
            };
            
            // 边的权重
            int weights[len] = {12, 16, 14, 10, 7, 3, 5, 6, 4, 2, 8, 9};
            
            //　初始化邻接表的边
            for(int i=0; i < e; i++){
                int start = get_Node_Index(edges[i][0]);
                int end = get_Node_Index(edges[i][1]);

                // 初始化 node1
                node1 = new ENode();
                node1->vex = end;
                node1->weight = weights[i];
                node1->nextEdge = NULL;
                // 将 node 添加到 start 所在链表的末尾
                if(mVexs[start].firstEdge == NULL){
                    mVexs[start].firstEdge = node1;
                }
                else{
                    linkLast(mVexs[start].firstEdge, node1);
                }

                // 初始化 node2
                node2 = new ENode();
                node2->vex = start;
                node2->weight = weights[i];
                node2->nextEdge = NULL;
                // 将 node 添加到 end 所在链表的末尾
                if(mVexs[end].firstEdge == NULL){
                    mVexs[end].firstEdge = node2;
                }
                else{
                    linkLast(mVexs[end].firstEdge, node2);
                }
            }
        }

        void linkLast(ENode*p1, ENode*p2){
            ENode*p = p1;
            while(p->nextEdge){
                p = p->nextEdge;
            }
            p->nextEdge = p2;
        }
        
        // 返回顶点下标
        int get_Node_Index(char number){
            for(int i=0; i < n; i++){
                if(number == mVexs[i].data){
                    return i;
                }
            }
            return -1; //这句话永远不会执行的
        }

        // 输出邻接表
        void print(){
            for(int i=0; i < n; i ++){
                cout<<mVexs[i].data;
                ENode *temp = mVexs[i].firstEdge;
                while(temp){
                    cout<<" -> "<<temp->vex;
                    temp = temp->nextEdge;
                }
                cout<<endl;
            }
            cout<<endl;
        }

        int getWeight(int m, int n){
            ENode *enode = mVexs[m].firstEdge;
            while(enode){
                if(enode->vex == n){
                    return enode->weight;
                }
                enode = enode->nextEdge;
            }

            return INF;
        }

        // prim 算法生成最小生成树
        void prim(int start){
            int j=0, k=0, min=INF;
            int index = 0;
            char prim[n];   // prim　最小树的结果数组

            int weight[n];

            // prim 最小生成树的第一个数是 start
            prim[index++] = mVexs[start].data;

            for(int i=0; i < n; i++){
                weight[i] = getWeight(start, i);
            }
            // 自身到自身距离为 0
            weight[start] = 0;

            for(int i=1; i < n; i++){
                min = INF;
                j = 0;
                k = 0;

                for(j = 0; j < n; j++){
                    if(weight[j]!= 0 && weight[j] < min){
                        min = weight[j];
                        k = j;
                    }
                }

                prim[index++] = mVexs[k].data;
                weight[k] = 0;
                for(j = 0; j < n; j++){
                    if(weight[j]!= 0 && getWeight(k,j)<weight[j]){
                        weight[j] = getWeight(k, j);
                    }
                }
            }

            // 计算最小生成树的权值
            int sum = 0;
            for(int i=1; i < n; i++){
                min = INF;
                int n = get_Node_Index(prim[i]);
                for(j=0; j < i; j++){
                    int m = get_Node_Index(prim[j]);
                    if(getWeight(m, n) < min){
                        min = getWeight(m, n);
                    }
                }
                sum += min;
            }

            //　打印最小生成树
            cout<<"最小生成树权值为: "<<sum<<endl;
            for(int i=0; i < n; i++){
                cout<<prim[i]<<" ";
            }
            cout<<endl;
        }
};

int main(){
    Graph g;
    // 输出邻接表
    // g.print();

    g.prim(0);
    return 0;
}

• Prim算法(二)之 C++详解