向図の隣接マトリクス格納構造でprimアルゴリズムを実現

2327 ワード

問題:図の隣接マトリックス格納構造でprimアルゴリズムを実現する
弧の他の情報形式はvi-vj(viは弧の終点であり、vjは弧の終点である)ですので、シンボルビットInfoは1を取り、最小の木を求める時に出力されるのが弧の情報です.
#include
#include
using namespace std;

#define MAX_VER_NUM 10    //      
#define INFINITY INT_MAX  //    
#define MAX_NAME 5        //          

typedef int VRType;       //    
typedef char InfoType;    
typedef char VertexType[MAX_NAME]; 

typedef struct
{
	VRType adj;       //  
	InfoType *info;   //         
}ArcCell,AdjMatrix[MAX_VER_NUM][MAX_VER_NUM];

typedef struct MGraph
{
	int vexnum;      //   
	int arcnum;      //  
	AdjMatrix arcs;  //    
	VertexType vexs[MAX_VER_NUM]; //    
}MGraph;

typedef struct 
{
	VertexType vex;
	VRType lowcost;
}closedge[MAX_VER_NUM];

int LocateVex(MGraph G,VertexType v)
{
	int i;
	for(i=0;i>G.vexnum>>G.arcnum>>Info;
	cout<>G.vexs[i];
	}
	for(i=0;i>vex_t>>vex_h>>w;
		pos_t=LocateVex(G,vex_t);
		pos_h=LocateVex(G,vex_h);
		G.arcs[pos_t][pos_h].adj=w;
		if(Info)
		{
			cout<>s;
			l=s.length();
			G.arcs[pos_t][pos_h].info=new char[l+1];
			strcpy(G.arcs[pos_t][pos_h].info,s.c_str());
		}
	}
	for(i=0;iG.vexnum)
	{
		cout<G.arcs[k][l].adj)
				{
					c[l].lowcost=G.arcs[k][l].adj;
					strcpy(c[l].vex,G.vexs[k]);
				}
			}
		}
	}
	cout<>i;
	Prim(G,i);	
}


------------------------------------------------------
Input:
6 8 1
v 1 v 2 v 3 v 4 v 5 v 6
v 1 v 2
v 1-v 2
v 1 v 3 1
v 1-v 3
v 2 v 5 3
v 2-v 5
v 3 v 6 5
v 3-v 6
v 4 v 1 4
v 4-v 1
v 5 v 3
v 5-v 3
v 5 v 6
v 5-v 6
v 6 v 4 7
v 6-v 4
1
out put:
v 1-v 3   1
v 1-v 2   2
v 2-v 5   3
v 3-v 6   5
v 6-v 4   7
18--------------------------------------------------------
-------------------------------
トムメークプログレス、everyday!------------------------------------