//圖的鄰接矩陣表示法(數(shù)組存儲)//圖的十字鏈表存儲
//
#include"stdio.h"
#include "stdlib.h"
//#include"iomanip.h"//setw(10)
  #define TRUE 1
  #define FALSE 0
  #define OK   1
  #define ERROR  0 
  #define INFEASIBLE -1
  #define OVERFLOW -2
  #define NULL 0
  typedef int Status;//函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼
  
#define MAX_VERTEX_NUM 20//最大頂點數(shù)
#define INFINITY 32768//無窮大

typedef int  GraphKind;//有向圖，有向網(wǎng)，無向圖，無向網(wǎng)
typedef char VertexType;
typedef int VRType;
typedef int InforType;
//typedef bool final ;//當(dāng)其為TRUE時 表明已求得最短路徑
//typedef int **PathMatrix;//頂點的最短路徑數(shù)組
//typedef int *ShortPathTable;//頂點的最短路徑的帶權(quán)長度數(shù)組
typedef struct ArcCell{
	VRType adj;//VRType是頂點關(guān)系類型，對無權(quán)圖，用1或0表示相鄰否；對帶權(quán)圖，則為權(quán)值類型
	InforType *info;//改弧相關(guān)信息的指針
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
	VertexType vexs[MAX_VERTEX_NUM];//頂點向量
	AdjMatrix arcs;//鄰接矩陣
	int vexnum ,arcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù)
	GraphKind kind;//圖的種類標(biāo)志
}MGraph;

int LocateVex(MGraph G,char v){
	for(int i=0;v!=G.vexs[i]&&i<G.vexnum;++i);
	if(i>=G.vexnum)return -1;
	return i;
}
Status CreateUDN(MGraph &G){
	//采用數(shù)組（鄰接矩陣）表示法，構(gòu)造無向網(wǎng)
	int IncInfo=0;
	printf("請輸入圖的種類(有向1,無向0)\n");
	scanf("%d",&G.kind);
	printf("請輸入頂點數(shù)vexnum，弧數(shù)arcnum和各弧的其他信息IncInfo(默認值0)\n");
	scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);//IncInfo為0則各弧不含其它信息
	printf("構(gòu)造頂點向量\n");
	for (int i1=0;i1<G.vexnum;++i1)
		scanf("%s",&G.vexs[i1]);//構(gòu)造頂點向量
	for(int i=0;i<G.vexnum;++i)
		for(int j=0;j<G.vexnum;++j){
			G.arcs[i][j].adj=INFINITY;//{adj,info}
			G.arcs[i][j].info=NULL;
		}
		char v1,v2;
		int w;
		for(int k=0;k<G.arcnum;++k){//構(gòu)造鄰接矩陣
			printf("輸入一條邊依附的頂點和權(quán)值v1 v2 w :\n");
			scanf("%s%s%d",&v1,&v2,&w);//輸入一條邊依附的頂點和權(quán)值
			int i=LocateVex(G,v1);
			int j=LocateVex(G,v2);//確定v1和v2在G中的位置
			G.arcs[i][j].adj=w;//弧的權(quán)值
			if(IncInfo)scanf("%d",&G.arcs[i][j].info);//若弧含有相關(guān)信息，則輸入
			if(!G.kind)G.arcs[j][i].adj=G.arcs[i][j].adj;//值<v1,v2>的對稱弧<v2,v1>
		}
		return OK;
}//CreateUDN
Status PrintfMGraph(MGraph G){
	printf("輸出鄰接矩陣\n");
	for(int i=0;i<G.vexnum;++i){
		printf("%d  %c ||  ",i,G.vexs[i]);
		for(int j=0;j<G.vexnum;++j){
			printf("%5d  ",G.arcs[i][j].adj);
		}
		j=0;
		printf("\n");
	}
	printf("----------32768代表無窮大----------\n");
	return OK;
}

Status ShortestPath_DIJ(MGraph G,VertexType vv,int P[][100],int D[]){
	//用Dijkstra算法求G的v0到其余頂點v的最短路徑及其帶權(quán)長度D[v]
	//若P[v][w]為TRUE，則w是從v0到w的當(dāng)前最短路徑的頂點
	//當(dāng)final[v]為TRUE時 表明已求得最短路徑
	int v0=LocateVex(G,vv);
	int final[10];
	for(int v=0;v<G.vexnum;++v){
		final[v]=FALSE;			//當(dāng)其為TRUE時 表明已求得最短路徑
		D[v]=G.arcs[v0][v].adj;
		for(int w=0;w<G.vexnum;++w) P[v][w]=FALSE;//設(shè)空路徑
		if(D[v]<INFINITY){
			P[v][v0]= TRUE;
			P[v][v]=TRUE;
		}
	}//for
	D[v0]=0;final[v0]=1;		//初始化，v0頂點屬于S集
	printf("%c到 v頂點的最短距離及途經(jīng)頂點\n",vv);
	int min=0;					//開始主循環(huán)，每次求得v0到某個v頂點的最短路徑，并加v到S集
	for(int i=1;i<G.vexnum;++i){	///其余G.vexnum－1各頂點//循環(huán)n-1次結(jié)束
		min=INFINITY;			//當(dāng)前離所知的頂點v0的最近距離
		for(int w1=0;w1<G.vexnum;++w1)
			if(!final[w1])		//w頂點在V－S中
				if(D[w1]<min){
					v=w1;
					min=D[w1];	//w1離頂點v0最近
				}
		final[v]=TRUE;			//離v0點最近的v加入S集
		printf("\n    %c%8d",G.vexs[v],min);//輸出函數(shù)部分
		printf("        ");
		for(int j=0;j<G.vexnum;++j)
			if(P[v][j])printf("%c",G.vexs[j]);//輸出最短路徑上的所有頂點
		for(int w2=0;w2<G.vexnum;++w2)	//更新當(dāng)前最段路徑機距離
			if(!final[w2]&&(min+G.arcs[v][w2].adj<D[w2])){//修改D[w2]和P[w2]
				D[w2]=min+G.arcs[v][w2].adj;
				for(int s=0;s<G.vexnum;++s)
				P[w2][s]=P[v][s];
				P[w2][w2]=TRUE;		//P[w2]=P[v]+P[w2]
			}//if
	}//for
	printf("\n");
	return OK;
}

void MiniSpanTree_PRIM(MGraph G,VertexType u){
	struct {
		VertexType adjvex;
		VRType lowcost;
	}closedge[MAX_VERTEX_NUM];
	int k=LocateVex(G,u);
	for(int j=0;j<G.vexnum;++j)
		if(j!=k){
			closedge[j].adjvex=u;
			closedge[j].lowcost=G.arcs[k][j].adj;
		}
		closedge[k].lowcost=0;
		printf("Prim 算法輸出最小生成樹\n");
		for(int i=1;i<G.vexnum;++i){
			int min=INFINITY;
			int k1=0;
			for(int n=0;n<G.vexnum;++n){
				if(closedge[n].lowcost){
					if(closedge[n].lowcost<min){
						min=closedge[n].lowcost;
						k1=n;
					}
				}
			}
			printf("%c-->%c  ",closedge[k1].adjvex,G.vexs[k1]);
			closedge[k1].lowcost=0;
			for(int j1=0;j1<G.vexnum;++j1)
				if(G.arcs[k1][j1].adj<closedge[j1].lowcost){
					closedge[j1].lowcost=G.arcs[k1][j1].adj;
					closedge[j1].adjvex=G.vexs[k1];
				}
		}
		printf("\n");
}

//單鏈隊列 ，隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)
typedef int QElemType;
typedef struct QNode{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q){
	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
	if(!Q.front)exit(OVERFLOW);
	Q.front->next=NULL;
	return OK;
}
Status QueueEmpty(LinkQueue Q){
	if(Q.front==Q.rear)return OK;
	else return ERROR;
}
Status EnQueue(LinkQueue &Q,QElemType e){
	QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
	if(!p)exit(OVERFLOW);
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}
Status DeQueue(LinkQueue &Q,QElemType &e){
	if(Q.front==Q.rear)return ERROR;
	QueuePtr p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)Q.rear=Q.front;
	free(p);
	return OK;
}
Status GetHead(LinkQueue &Q,QElemType &e){
	QueuePtr p;
	if(QueueEmpty(Q))return 0;
	else {
		p=Q.rear;
		return p->data;
	}
	return OK;
}
Status DestroyQueue(LinkQueue &Q){
	while(Q.front){
		Q.rear=Q.front->next;
		free(Q.front);
		Q.front=Q.rear;//從前向后依次刪除隊列中的結(jié)點
	}
	return OK;
}

//十字鏈表結(jié)構(gòu)
//有向圖無向圖的十字鏈表存儲表示
typedef struct ArcBox{
	VRType tailvex,headvex;//VRType是int類型，該弧的尾和頭頂點的位置
	struct ArcBox *hlink,*tlink;//分別為弧頭相同的弧和弧尾相同的弧的鏈域
	InforType *info;//改弧相關(guān)信息的指針
}ArcBox;
typedef struct VexNode{
	VertexType data;//VRType是頂點關(guān)系類型，對無權(quán)圖，用1或0表示相鄰否；對帶權(quán)圖，則為權(quán)值類型
	ArcBox *firstin,*firstout;//分別指向該頂點的第一個如入弧和出弧
}VexNode;
typedef struct {
	VexNode xlist[MAX_VERTEX_NUM];//頂點向量
	int vexnum ,arcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù)
	GraphKind kind;//圖的種類標(biāo)志
}OLGraph;

int LocateVex(OLGraph G,char v){
	for(int i=0;v!=G.xlist[i].data&&i<G.vexnum;++i);
	if(i>=G.vexnum)return -1;
	return i;
}
Status CreateUDG(OLGraph &G){
	//采用十字鏈表表示法，構(gòu)造無向網(wǎng)
	int IncInfo=0;
	printf("請輸入圖的種類(有向1,無向0)\n");
	scanf("%d",&G.kind);
	printf("請輸入頂點數(shù)vexnum，弧數(shù)arcnum和各弧的其他信息IncInfo(默認值0)\n");
	scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);//IncInfo為0則各弧不含其它信息
	printf("構(gòu)造頂點向量\n");
	for (int i1=0;i1<G.vexnum;++i1){
		scanf("%s",&G.xlist[i1].data);//構(gòu)造頂點向量
		G.xlist[i1].firstin=NULL;//初始化指針
		G.xlist[i1].firstout=NULL;
		}
		char v1,v2;
		for(int k=0;k<G.arcnum;++k){//構(gòu)造十字鏈表
			printf("輸入一條邊依附的頂點v1 v2 :\n");
			scanf("%s%s",&v1,&v2);//輸入一條邊依附的頂點
			int i=LocateVex(G,v1);
			int j=LocateVex(G,v2);//確定v1和v2在G中的位置
			ArcBox* p=(ArcBox*)malloc(sizeof(ArcBox));
			p->tailvex=i;
			p->headvex=j;
			p->hlink=G.xlist[j].firstin;
			p->tlink=G.xlist[i].firstout;
			p->info=NULL;
			G.xlist[j].firstin	= G.xlist[i].firstout=p;//完成入弧出弧連頭的插入
			if(IncInfo)scanf("%d",&(p->info));//若弧含有相關(guān)信息，則輸入
			if(!G.kind){//值<v1,v2>的對稱弧<v2,v1>
				ArcBox* q=(ArcBox*)malloc(sizeof(ArcBox));
				q->tailvex=j;
				q->headvex=i;
				q->hlink=G.xlist[i].firstin;
				q->tlink=G.xlist[j].firstout;
				q->info=NULL;
				G.xlist[i].firstin = G.xlist[j].firstout=q;//完成入弧出弧連頭的插入
				if(IncInfo)scanf("%d",&(q->info));//若弧含有相關(guān)信息，則輸入
			}
		}
		return OK;
}//CreateUDG
void visit_OL(OLGraph G){
	//輸出十字表
	int i;
	ArcBox *p;
	printf("%4s%6s%25s\n","No","data","adjvexs of arcs'tailvex");
	for(i=0;i<G.vexnum;i++){
		printf("%4d%5c  ",i,G.xlist[i].data);
		for(p=G.xlist[i].firstout;p;p=p->tlink)
			printf("%3d",p->headvex);//弧所指的頂點的位置
		printf("\n");
	}
}