最小生成树 - Prim

#include<bits/stdc++.h>
#define INF 99999999 
using namespace std;
/*
    最小生成树：
        某个图的最小生成树包含如下要求：
            1)是一颗树：无回路、V个顶点的图有V-1条边
            2)生成树：图的所有顶点都包含在树中、树的所以边都是图中的边
            3)边的权重和最小
        最小生成树存在 <==> 图是连通图 

    Prim算法：让一颗小树慢慢长大 
        概述：先选定一个初始点最为一棵树，然后每次循环时把距树最近的点加入树中，
              直至顶点全部加入。若中途出现无法加入的情况，说明图不连通。

        伪码（设s为原点）：
            while(true)
            {
                v = 距离树最小的点;
                if(v不存在)
                    break;
                v加入树中; 
                for(v的每个邻接点)
                    更新到树的距离
            }
            if(未全部加入树中)
                生成树不存在; 
*/

class MGraph                //矩阵图 
{
    public:
        int n;
        int **matrix;
        MGraph(){ matrix = NULL; }
};
class Node              //链式图 
{
    public:
        int n;
        int ew;
        Node(int tn, int tw){ n = tn; ew = tw; }
};
class LGraph
{
    public:
        vector<Node> *vs;
        int n;
        LGraph(){ vs = NULL; }
};
MGraph* create_mGraph()
{
    int i, from, to, w, vn, en;     //点数、边数、边权 
    MGraph *g = new MGraph();
    scanf("%d%d", &vn, &en);
    g->n = vn;
    g->matrix = new int*[vn];
    for(i = 0; i < vn; i++)
    {
        g->matrix[i] = new int[vn];
        fill(g->matrix[i], g->matrix[i] + vn, INF);
        g->matrix[i][i] = 0; 
    }
    for(i = 0; i < en; i++)
    {
        cin >> from >> to >> w;
        g->matrix[from][to] = g->matrix[to][from] = w;
    }
    return g;
}
LGraph *create_lGraph()
{
    int i, from, to, w, vn, en;     //点数、边数、边权 
    LGraph *g = new LGraph();
    scanf("%d%d", &vn, &en);
    g->n = vn;
    g->vs = new vector<Node>[vn];
    for(i = 0; i < en; i++)
    {
        cin >> from >> to >> w;
        Node *temp1 = new Node(to, w), *temp2 = new Node(from, w);
        g->vs[from].push_back(*temp1);
        g->vs[to].push_back(*temp2);
    }
    return g;
}

class Record
{
    public:
        int parent, dist, visit;
        Record(){ parent = -1; dist = visit = 0; }
};

Record *lGraphPrim(LGraph *g, int s)
{
    int i, j, n = g->n;
    Record *recs = new Record[n];
    recs[s].visit = 1;
    for(i = 0; i < n; i++)
    {
        recs[i].dist = INF;
        recs[i].parent = s;
    }
    for(i = 0; i < g->vs[s].size(); i++)
        recs[g->vs[s][i].n].dist = g->vs[s][i].ew;
    for(j = 1; j < n; j++)
    {
        int v = -1, min = INF;
        for(i = 0; i < n; i++)
            if(!recs[i].visit && recs[i].dist < min)
                min = recs[v = i].dist;
        if(v == -1)
            return NULL;
        recs[v].visit = 1;
        for(i = 0; i < g->vs[v].size(); i++)
            if(!recs[g->vs[v][i].n].visit && recs[g->vs[v][i].n].dist > g->vs[v][i].ew)
            {
                recs[g->vs[v][i].n].dist = g->vs[v][i].ew;
                recs[g->vs[v][i].n].parent = v;
            }
    }
    return recs;
}


Record *mGraphPrim(MGraph *g, int s)
{
    int i, j, n = g->n;
    Record *recs = new Record[n];
    recs[s].visit = 1;
    for(i = 0; i < n; i++)
    {
        recs[i].dist = g->matrix[s][i];
        recs[i].parent = s;
    }
    for(j = 1; j < n; j++)
    {
        int v = -1, min = INF;
        for(i = 0; i < n; i++)
            if(!recs[i].visit && recs[i].dist < min)
                min = recs[v = i].dist;
        if(v == -1)
            return NULL;
        recs[v].visit = 1;
        for(i = 0; i < n; i++)
            if(!recs[i].visit && recs[i].dist > g->matrix[v][i])
            {
                recs[i].dist = g->matrix[v][i];
                recs[i].parent = v;
            }
    }
    return recs;
}
int main()
{
    LGraph *lg = create_lGraph();
    MGraph *mg = create_mGraph();
    int s;
    cin >> s;
    Record *rl = lGraphPrim(lg, s);
    Record *rm = mGraphPrim(mg, s);
    for(int i = 0; i < lg->n; i++)
        cout << rl[i].parent << " " << i << " " << rl[i].dist << endl;
    cout << "-------------" << endl;
    for(int i = 0; i < mg->n; i++)
        cout << rm[i].parent << " " << i << " " << rm[i].dist <<endl;
    return 0;
}
/*
    input：
        7 12
        0 1 2
        0 2 4
        0 3 1
        1 3 3
        1 4 10
        2 3 2
        2 5 5
        3 4 7
        3 5 8
        3 6 4
        4 6 6
        5 6 1
        7 12
        0 1 2
        0 2 4
        0 3 1
        1 3 3
        1 4 10
        2 3 2
        2 5 5
        3 4 7
        3 5 8
        3 6 4
        4 6 6
        5 6 1
        0
    output:
        0 0 99999999
        0 1 2
        3 2 2
        0 3 1
        6 4 6
        6 5 1
        3 6 4
        -------------
        0 0 0
        0 1 2
        3 2 2
        0 3 1
        6 4 6
        6 5 1
        3 6 4
*/