向図の隣接マトリクス格納構造でprimアルゴリズムを実現
2327 ワード
問題:図の隣接マトリックス格納構造でprimアルゴリズムを実現する
弧の他の情報形式はvi-vj(viは弧の終点であり、vjは弧の終点である)ですので、シンボルビットInfoは1を取り、最小の木を求める時に出力されるのが弧の情報です.
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!------------------------------------
弧の他の情報形式は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!------------------------------------