데이터 구조 -- 최소 생 성 트 리 (Prim 알고리즘)

    Graph.h
//        
#pragma once

#include 
#include 
using namespace std;

#define        INFINITY        INT_MAX
#define        NAX_VERTEX_NUM    20
#define        VRtype            int
//#define        InfoType        char*
#define        VertexType        char*

#define   TRUE             1
#define   FALSE            0
#define   OK               1
#define   ERROR            0
#define   OVERFLOW          -2
#define   INFEASIBLE      -1

bool visited[NAX_VERTEX_NUM];
void(*VisitFunc)(VertexType);

typedef enum
{
    DG,DN,UDG,UDN//   ，   ，   ，   
}GraphKind;

typedef struct ArcCell
{
    VRtype        adj;//   ， 0 1；   ，   
    //InfoType    *info;    
}ArcCell, AdjMatrix[NAX_VERTEX_NUM][NAX_VERTEX_NUM];

typedef struct //      
{
    VertexType    vexs[NAX_VERTEX_NUM];//    
    AdjMatrix    arcs;                 //    
    int            vexnum,arcnum;         //   ， （ ） 
    GraphKind    kind;                 //      
}MGraph;

int CreateDG(MGraph &G);//     
int CreateDN(MGraph &G);//     
int CreateUDG(MGraph &G);//     
int CreateUDN(MGraph &G);//     

int CreateGraph(MGraph &G)//    （    ）   ，   G
{
    int n;
    cout<>n;
    switch(n)
    {
    case DG:
        G.kind = DG;
        return CreateDG(G);//   
    case DN:
        G.kind = DN;
        return CreateDN(G);//   
    case UDG:
        G.kind = UDG;
        return CreateUDG(G);//   
    case UDN:
        G.kind = UDN;
        return CreateUDN(G);//   
    default:
        return ERROR;
    }
}

int LocateVex(MGraph G, VertexType V)//  V      
{
    int i;
    for(i=0; i>G.vexnum>>G.arcnum;
    int i,j,k;
    for(i=0; i>G.vexs[i];
    }
    for(i=0; i>v1>>v2;
        i = LocateVex(G,v1);//    v1 v2      
        j = LocateVex(G,v2);
        G.arcs[i][j].adj = 1;//  
        G.arcs[j][i] = G.arcs[i][j];//    ，      
    }
    G.kind = UDG;//   
    return OK;
}

int CreateDG(MGraph &G)//     
{
    cout<>G.vexnum>>G.arcnum;
    int i,j,k;
    for(i=0; i>G.vexs[i];
    }
    for(i=0; i>v1>>v2;
        i = LocateVex(G,v1);//    v1 v2      
        j = LocateVex(G,v2);
        G.arcs[i][j].adj = 1;//  
    }
    G.kind = DG;//   
    return OK;
}

int CreateUDN(MGraph &G)//    （    ）   ，     
{
    //int IncInfo;
    cout<>G.vexnum>>G.arcnum;
    int i,j,k;
    for(i=0; i>G.vexs[i];
    }
    for(i=0; i>v1>>v2>>w;
        i = LocateVex(G,v1);//    v1 v2      
        j = LocateVex(G,v2);
        G.arcs[i][j].adj = w;//  
        G.arcs[j][i] = G.arcs[i][j];//    ，      
    }
    G.kind = UDN;//   
    return OK;
}

int CreateDN(MGraph &G)//    （    ）   ，     
{
    //int IncInfo;
    cout<>G.vexnum>>G.arcnum;
    int i,j,k;
    for(i=0; i>G.vexs[i];
    }
    for(i=0; i>v1>>v2>>w;
        i = LocateVex(G,v1);//    v1 v2      
        j = LocateVex(G,v2);
        G.arcs[i][j].adj = w;//  
    }
    G.kind = DN;//   
    return OK;
}

VertexType GetVex(MGraph G, int v)//     V   
{
    if(v<1 || v>G.vexnum)
        return NULL;
    else
        return G.vexs[v-1];//       0  
}

int PutVex(MGraph &G, VertexType v, VertexType value)//      v    value
{
    int i = LocateVex(G,v);
    if(i<0)
        return ERROR;
    else
        strcpy(G.vexs[i],value);
    return OK;
}

VertexType FirstAdjVex(MGraph G, VertexType v)//    V       
{
    int i,j,k;
    k = LocateVex(G,v);//    v      
    if(k<0)
        return NULL;
    if(G.kind % 2 == 1)// 
        j = INFINITY;
    else
        j = 0;// 
    for(i=0; i>weight;
    }
    else
        weight = 1;
    if(G.kind < 2)//  
        G.arcs[i][j].adj = weight;
    else//  
        G.arcs[j][i].adj= G.arcs[i][j].adj=weight;
    return OK;
}

int DeleteArc(MGraph &G, VertexType v, VertexType w)//     
{
    int i,j,weight;
    i = LocateVex(G,v);// 
    j = LocateVex(G,w);// 
    if(i<0 || j<0)
        return ERROR;
    G.arcnum--;
    if(G.kind % 2 == 1)// 
        weight = INFINITY;
    else// 
        weight = 1;
    if(G.kind < 2)//  
        G.arcs[i][j].adj = weight;
    else
        G.arcs[i][j].adj = G.arcs[j][i].adj = weight;
    return OK;
}

void Display(MGraph G)//      
{
    int i,j;
    for(i=0; i"< Q;            //       
    for(i=0; i 0)
        {
            min = closed_array[i].lowcost;
            flag = i;
        }
    }
    return flag;
}

void MiniSpanTree_PRIM(MGraph G, VertexType u)//          u        G      T，  T    
{

    int k;
    k = LocateVex(G,u);//  u      
    int i,j;
    closedge closed_array;//      
    for(j=0; j0}
        cout<"<