C++ prim算法 最小生成树

img


有这样的一张有向图图，现在要求这张图的最小生成数，返回各边权值之和
当遍历到4点时，并不能便利之前的所有点找到5
代码如下：


// Prim 算法
# include <iostream>
using namespace std;
/*
输入格式:
5 7
1 2 2
1 3 4
1 4 7
2 3 1
3 4 1
2 5 2
3 5 6
*/
int N,M;
int g[101][101];
int minLis[101];
bool vis[101];  // true 代表还没访问


void print_g()
{
    for (int i=1;i<=N;i++)
    {    
        for (int j=1;j<=N;j++)
        {
            cout << g[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

void print_vis()
{
    for (int i=1;i<=N;i++)
    {
        cout << vis[i] << " ";
    }
    cout << endl;
}

void print_minLis()
{
    for (int i=1;i<=N;i++)
    {
        cout << minLis[i] << " ";
    }
    cout << endl;
}

int main()
{
    cin >> N >> M;  // N：点数  M：边数
    memset(g,0x7f,sizeof(g));
    memset(minLis,0x7f,sizeof(minLis));
    memset(vis,true,sizeof(vis));
    int i,j,w;  // 从i到j的权值w
    for (int a=1;a<=M;a++)
    {
        cin >> i >> j >> w;
        g[i][j] = g[j][i] = w;
    }
    print_g();
    minLis[1] = 0;
    vis[1] = false;
    for (i=1;i<=N-1;i++)
    {
        int k=0;
        for (int j=1;j<=N;j++)
        {
            if (vis[j] && g[i][j] < minLis[k])
            {
                k=j;
                minLis[j] = g[i][j];
            }
            cout << k << endl;
            print_vis();
            print_minLis();
        }
        vis[k]=false;        
    }               
    return 0;
}



```c++
#ifndef prim_h
#define prim_h
#include <queue>
#include "Graph.h"
 
const int DefaultSize = 40; // 默认个数
 
template <class T, class E>
struct MSTEdgeNode { // 最小生成树边结点的类声明
    int head, tail; // 两顶点位置
    E weight; // 边上权值
    MSTEdgeNode():tail(-1), head(-1), weight(0){}; // 构造函数
};
 
template <class T, class E>
bool operator<(const MSTEdgeNode<T, E> &a,const MSTEdgeNode<T, E> &b) {
    if(a.weight > b.weight)
        return true;
    return false;
}
 
template <class T, class E>
class MinSpanTree { // 最小生成树的类定义
public:
    MinSpanTree(int sz = DefaultSize-1) { // 构造函数
        maxSize = sz;
        currentSize = 0;
        edgeValue = new MSTEdgeNode<T, E>[sz];
    }
    ~MinSpanTree() { // 析构函数
        delete []edgeValue; // 释放空间
    }
    bool Insert(MSTEdgeNode<T, E> &item); // 插入
    void Prim(Graphlnk<T, E> &G, const T u0); // Prim算法
    void printMST(Graphlnk<T, E> &G); // 打印最小生成树
private:
    int maxSize, currentSize; // 数组的最大元素个数和当前个数
    MSTEdgeNode<T, E> *edgeValue; // 用边值数组表示树
};
 
// 插入
template <class T, class E>
bool MinSpanTree<T, E>::Insert(MSTEdgeNode<T, E> &item) {
    if(currentSize == maxSize-1) {
        cout << "已超出数组的存储范围！" << endl;
        return false;
    }
    
    edgeValue[currentSize] = item;
    currentSize++;
    return true;
}
 
// Prim算法
template <class T, class E>
void MinSpanTree<T, E>::Prim(Graphlnk<T, E> &G, const T u0) {
    MSTEdgeNode<T, E> ed; // 边点辅助单元
    int i, u, v, count;
    int n = G.numberOfVertices(); // 获取图的当前顶点数
    u = G.getVertexPos(u0); // 求起始顶点号u
    priority_queue<MSTEdgeNode<T, E>> H; // 最小堆，关键码类型为E
    bool visit[n]; // 最小生成树顶点集合
    
    for(i = 0; i < n; i++) // 初始化为未访问过
        visit[i] = false;
    visit[u] = true; // u加入生成树，第一顶点
    count = 1;
    do { // n个顶点，要找n-1条边，组成最小生成树
        // 1.先找到与v相关未被访问过的邻接顶点，然后把两者组成的边放到最小堆中
        v = G.getFirstNeighbor(u); // 找u的第一个邻接顶点
        while(v != -1) { // 重复检测u的所有邻接顶点
            if(visit[v] == false) { // 该顶点未被访问过
                ed.tail = u;
                ed.head = v;
                ed.weight = G.getWeight(u, v); // 获取(u,v)边的权值
                H.push(ed);
            }
            v = G.getNextNeighbor(u, v); // 找顶点u的邻接顶点v的下一个邻接顶点
        }
        // 2.找当前顶点u与其他未被访问过的邻接顶点之间最小权值的边
        while(H.empty() == false && count < n) {
            ed = H.top(); // 从最小堆中退出具有最小权值的边ed
            H.pop();
            if(visit[ed.head] == false) { // 未被访问过
                Insert(ed); // 插入到最小生成树中
                u = ed.head;
                visit[u] = true; // 标记为已访问，u加入生成树顶点集合
                count++;
                break;
            }
        }
    }while(count < n);
}
 
// 打印最小生成树
template <class T, class E>
void MinSpanTree<T, E>::printMST(Graphlnk<T, E> &G) {
    int tail, head; // 顶点所在位置
    T e1, e2; // 两顶点
    E weight; //  权值
    
    for(int i = 0; i < currentSize; i++) {
        tail = edgeValue[i].tail; // 顶点所在位置
        head = edgeValue[i].head;
        e1 = G.getValue(tail); // 根据位置，取顶点对应的值
        e2 = G.getValue(head);
        weight = G.getWeight(tail, head); // 取权值
        cout << "(" << e1 << "," << e2 << "," << weight << ")" << endl;
    }
}
#endif /* prim_h */

```

这题我推荐你看看这个问题的回答，和你的很像，希望你能先点一下采纳，谢谢！
问题和回答：(https://ask.csdn.net/questions/7756134)