Johnson算法

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define mvn 1026
#define Infinte 9999
#define TRUE 1
#define FALSE 0

typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
	int w;
}ArcNode;

typedef struct VNode{
	int data;
	int d;
	VNode *parent;
	ArcNode *firstarc;
}VNodeAdjList[mvn];

typedef struct {
	AdjList vex;
	int vexnumarcnum;
}ALGraph;

void CreatG（ALGraph &G）{
	int ijk;
	int v1v2v3;
	struct ArcNode *p;
	printf（“Please input the number of Vertexes.\n“）;
	scanf（“%d“&G.vexnum）;
	printf（“Please input the number of Arcs.\n“）;
	scanf（“%d“&G.arcnum）;
	for（i=1;i<=G.vexnum;++i）{ 
		G.vex[i].data=i;
		G.vex[i].firstarc=NULL;
		G.vex[i].parent=NULL;
	}
	for（k=1;k<=G.arcnum;k++）{
		printf（“Please input Arc No.%d Sample: 12 \n“k）;
		scanf（“%d%d“&v1&v2）;
		printf（“Please input its w\n“）;
		scanf（“%d“&v3）;
		i=v1;
		j=v2;
		p=（ArcNode *） malloc （sizeof （ArcNode））;
		p->adjvex=j;
		p->nextarc=G.vex[i].firstarc;
		p->w=v3;
		G.vex[i].firstarc=p; 
	}
}

int check（ALGraph &Gint iint j）{
	if（i==j） return FALSE;
	ArcNode *p;
	p=G.vex[i].firstarc;
	while（p!=NULL）{
		if（p->adjvex==j） return FALSE;
		p=p->nextarc;
	}
	return TRUE;
}

void CreatG2（ALGraph &Gint nint runtype）{
	int ijkw;
	struct ArcNode *p;
	G.vexnum=n;
	G.arcnum=（int）n*（log（n）/log（2））;
	for（i=1;i<=G.vexnum;i++）{ 
		G.vex[i].data=i;
		G.vex[i].firstarc=NULL;
		G.vex[i].parent=NULL;
	}
	for（k=2;k<=G.vexnum;k++）{
		i=rand（）%（k-1）+1;
		w=rand（）%100;
		j=k;
		p=（ArcNode *） malloc （sizeof （ArcNode））;
		p->adjvex=j;
		p->nextarc=G.vex[i].firstarc;
		p->w=w;
		G.vex[i].firstarc=p;
		p=（ArcNode *） malloc （sizeof （ArcNode））;
		p->adjvex=i;
		p->nextarc=G.vex[j].firstarc;
		p->w=w;
		G.vex[j].firstarc=p;
		if（runtype==1）{
			printf（“Arc No.%d: %d%d\n“（k-1）ij）;
			printf（“Its w: %d\n“w）;
			printf（“\n“）;
		}
	}
	for（;k<=（G.arcnum+1）;k++）{
		do{
			i=rand（）%（G.vexnum）+1;
			j=rand（）%（G.vexnum）+1;
		}while（check（Gij）==FALSE）;
//		printf（“OK\n“）;
		w=rand（）%100;		
		p=（ArcNode *） malloc （sizeof （ArcNode））;
		p->adjvex=j;
		p->nextarc=G.vex[i].firstarc;
		p->w=w;
		G.vex[i].firstarc=p;
		p=（ArcNode *） malloc （sizeof （ArcNode））;
		p->adjvex=i;
		p->nextarc=G.vex[j].firstarc;
		p->w=w;
		G.vex[j].firstarc=p;
		if（runtype==1）{
			printf（“Arc No.%d: %d%d\n“（k-1）ij）;
			printf（“Its w: %d\n“w）;
			printf（“\n“）;
		}
	}
}

void Compute（ALGraph &GALGraph &G2）{
	int ij;
	ArcNode *p;
	for（i=1;i<=G.vexnum;i++）
		G2.vex[i]=G.vex[i];
	G2.vex[i].firstarc=NULL;
	p=（ArcNode *） malloc （sizeof （ArcNode））;
	for（j=1;j<=G.vexnum;j++）{
		p=（ArcNode *） malloc （sizeof （ArcNode））;
		p->adjvex=j;
		p->nextarc=G2.vex[i].firstarc;
		p->w=0;
		G2.vex[i].firstarc=p;
	}
	G2.vex[i].data=i;
	G2.vexnum=G.vexnum+1;
	G2.arcnum=G.arcnum+G.vexnum;

}


void IntializeSingleS