#define MAX_VERTEX_NUM 20 	/* 最多顶点个数 */

#define INFINITY 32768 		/* 表示极大值，即∞*/

/* 图的种类：DG 表示有向图，DN 表示有向网，UDG 表示无向图，UDN 表示无向网 */

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

typedef char VertexData; 		/* 假设顶点数据为字符型 */

typedef struct ArcNode{

    AdjType adj; /* 对于无权图，用 1 或 0 表示是否相邻；对带权图，则为权值类型 */

	OtherInfo info;

} ArcNode;

typedef struct{

	VertexData vertex[MAX_VERTEX_NUM]; /* 顶点向量 */

	ArcNode arcs [MAX_VERTEX_NUM][MAX_VERTEX_NUM]; /* 邻接矩阵 */

	int vexnum, arcnum; 		/* 图的顶点数和弧数 */

	GraphKind kind; 			/* 图的种类标志 */

}AdjMatrix; 					/*(Adjacency Matrix Graph) 邻接矩阵 */

/* 求顶点位置函数 */

int LocateVertex(AdjMatrix * G, VertexData v){ 

	int j=Error,k;

    for(k=0;k<G->vexnum;k++)

 		if(G->vertex[k]==v){

            j=k;

            break;

        }

 		return(j);

}

int CreateDN(AdjMatrix *G){ /* 创建一个有向网 */

	int i,j,k,weight; VertexData v1,v2;

	scanf("%d,%d",&G->arcnum,&G->vexnum); /* 输入图的顶点数和弧数 */

	for(i=0;i<G->vexnum;i++) /* 初始化邻接矩阵 */

		for(j=0;j<G->vexnum;j++)

			G->arcs[i][j].adj=INFINITY;

	for(i=0;i<G->vexnum;i++)scanf("%c",&G->vertex[i]); /* 输入图的顶点 */

	for(k=0;k<G->arcnum;k++){

        scanf("%c,%c,%d",&v1,&v2,&weight);/* 输入一条弧的两个顶点及权值 */

 		i=LocateVex_M(G,v1);

 		j=LocateVex_M(G,v2);

 		G->arcs[i][j].adj=weight; /* 建立弧 */

    }

 	return(Ok);

}

#define MAX_VERTEX_NUM 20 /* 最多顶点个数 */

typedef enum{DG, DN, UDG, UDN} GraphKind; /* 图的种类 */

typedef struct ArcNode{

	int adjvex; /* 该弧指向顶点的位置 */

	struct ArcNode *nextarc; /* 指向下一条弧的指针 */

 	OtherInfo info; /* 与该弧相关的信息 */

} ArcNode;

typedef struct VertexNode{

 	VertexData data; /* 顶点数据 */

 	ArcNode *firstarc; /* 指向该顶点第一条弧的指针 */

} VertexNode;

typedef struct{

 	VertexNode vertex[MAX_VERTEX_NUM];

 	int vexnum,arcnum; /* 图的顶点数和弧数 */

 	GraphKind kind; /* 图的种类标志 */

}AdjList; /* 基于邻接表的图 (Adjacency List Graph)*/

// 主函数

void DFSTraverseAL(ALGraph *G){

    /* 深度优先遍历以邻接表存储的图 G*/

	int i;

	for (i=0;i<G->n;i++)visited[i]=FALSE;

	for (i=0;i<G->n;i++)

        if (!visited[i]) DFS(G,i);

}

/* 以 Vi 为出发点对邻接表存储的图 G 进行 DFS 搜索 */

void DFS(ALGraph *G,int i){ 

	EdgeNode *p;

	//visit(v0);

    printf("visit vertex:V%c\n",G->adjlist[i].vertex); /* 访问顶点 Vi*/

	visited[i]=1;

	p=G->adjlist[i].firstedge;

	while(p){

        if (visited[p->adjvex]==0){

            DFS(G,p->adjvex);

        }

	p=p->next;// 下一个邻接点

	}

}

// 用邻接矩阵方式实现深度优先搜索，图 g 为邻接矩阵类型 AdjMatrix

void DepthFirstSearch(AdjMatrix g, int v0){

	visit(v0); 

    visited[v0]=True;

	for ( vj=0;vj<n;vj++)

 		if (!visited[vj] && g.arcs[v0][vj].adj==1)

			DepthFirstSearch(g, vj);

}/* DepthFirstSearch */

// 用邻接表方式实现深度优先搜索，图 g 为邻接表类型 AdjList

void DepthFirstSearch(AdjList g, int v0){

    visit(v0) ;

    visited[v0]=True;

	p=g.vertex[v0].firstarc;

	while( p!=NULL ){

        if (! visited[p->adjvex])

			DepthFirstSearch(g, p->adjvex);

		p=p->nextarc;

 	}

}/*DepthFirstSearch*/

/* 广度优先搜索图 g 中 v0 所在的连通子图 */

void BreadthFirstSearch(Graph g, int v0){

	visit(v0);

    visited[v0]=True;

	InitQueue(&Q); /* 初始化空队 */

	EnterQueue(&Q, v0); /* v0 进队 */

	while ( ! Empty(Q)){

        DeleteQueue(&Q, &v); /* 队头元素出队 */

		w=FirstAdjVertex (g, v); /* 求 v 的第一个邻接点 */

		while (w!=-1 ){

            if (!visited[w]){

                visit(w);

                visited[w]=True;;

				EnterQueue(&Q, w);

			}

			w=NextAdjVertex (g, v, w); /* 求 v 相对于 w 的下一个邻接点 */

	 	}

	}

}

// 深度优先找出从顶点 u 到 v 的简单路径

int *pre;

/* 在连通图 G 中找一条从第 u 个顶点到 v 个顶点的简单路径 */

void one_path(Graph *G, int u, int v){

    int i;

	pre=(int *)malloc(G->vexnum*sizeof(int));

	for(i=0;i<G->vexnum;i++) pre[i]=-1;

 	pre[u]=u; /* 将 pre [u] 置为非 - 1，表示第 u 个顶点已被访问 */

 	DFS_path(G, u, v); /* 用深度优先搜索找一条从 u 到 v 的简单路径。*/

	free(pre);

}

 /* 在连通图 G 中用深度优先搜索策略找一条从 u 到 v 的简单路径。*/

void DFS_path(Graph *G, int u, int v){

    int j;

 	if(pre[v]!=-1)

 		for(j=firstadj(G,u);j>=0;j=nextadj(G,u,j))

 			if(pre[j]==-1){

 				pre[j]=u;

 				if(j==v) print_path(pre ,v); /* 输出路径 */

 				else DFS_path(G,j,v);

 			}

}

struct {

	VertexData adjvex;

    int lowcost;

} closedge[MAX_VERTEX_NUM]; /* 求最小生成树时的辅助数组 */

/* 从顶点 u 出发，按普里姆算法构造连通网 gn 的最小生成树，并输出生成树的每条边 */

void MiniSpanTree_Prim(AdjMatrix gn, VertexData u){

	k=LocateVertex(gn, u);

	closedge[k].lowcost=0; /* 初始化，U={u} */

	for (i=0; i<gn.vexnum; i++)

       /* 对 V-U 中的顶点 i，初始化 closedge [i]*/

		if ( i!=k){

            closedge[i].adjvex=u;

			closedge[i].lowcost=gn.arcs[k][i].adj;

		}

    /* 找 n-1 条边 (n= gn.vexnum) */

	for (e=1; e<=gn.vexnum-1; e++){ 

		k0=Minium(closedge); /* closedge [k0] 中存有当前最小边 (u0,v0) 的信息 */

		u0= closedge[k0].adjvex; /* u0∈U*/

		v0= gn.vertex[k0] /* v0∈V-U*/

	 	printf(u0, v0); /* 输出生成树的当前最小边 (u0,v0)*/

	 	closedge[k0].lowcost=0; /* 将顶点 v0 纳入 U 集合 */

	 	for ( i=0 ;i<vexnum;i++) /* 在顶点 v0 并入 U 之后，更新 closedge [i]*/

	 		if ( gn.arcs[k0][i].adj <closedge[i].lowcost){

                closedge[i].lowcost= gn.arcs[k0][i].adj;

				closedge[i].adjvex=v0;

	 		}

	}

}

// 拓扑排序算法

int TopoSort (AdjList G){ 

    Stack S;

	int indegree[MAX_VERTEX_NUM];

	int i, count, k;

 	ArcNode *p;

 	FindID(G,indegree); /* 求各顶点入度 */

 	InitStack(&S); /* 初始化辅助栈 */

 	for(i=0;i<G.vexnum;i++)

 		if(indegree[i]==0) Push(&S,i); /* 将入度为 0 的顶点入栈 */

 	count=0;

 	while(!IsEmpty(S)){

		Pop(&S,&i);

 		printf("%c", G.vertex[i].data);

 		count++; /* 输出 i 号顶点并计数 */

 		p=G.vertex[i].firstarc;

		while(p!=NULL){

            k=p->adjvex;

 			indegree[k]--; /*i 号顶点的每个邻接点的入度减 1*/

 			if(indegree[k]==0) Push(&S, k); /* 若入度减为 0，则入栈 */

			p=p->nextarc;

		}

	}

 	if (count<G.vexnum) return(Error); /* 该有向图含有回路 */

 	else return(Ok);

}

/* 求各顶点的入度 */

void FindID( AdjList G, int indegree[MAX_VERTEX_NUM]){ 

    int i; ArcNode *p;

	for(i=0; i<G.vexnum; i++)indegree[i]=0;

	for(i=0; i<G.vexnum; i++){

        p=G.vertex[i].firstarc;

		while(p!=NULL){

            indegree[p->adjvex]++;

			p=p->nextarc;

        }

	} 

}

// 关键路径算法

int CriticalPath(AdjList G){

    ArcNode *p;

 	int i,j,k,dut,ei,li; char tag;

	int vl[MAX_VERTEX_NUM]; /* 每个顶点的最迟发生时间 */

	Stack T;

 	if(!TopoOrder(G, &T)) return(Error);

    /* 将各顶点事件的最迟发生时间初始化为汇点的最早发生时间 */

    for(i=0; i<G.vexnum; i++)

		vl[i]=ve[G.vexnum-1]; 

    /* 按逆拓扑顺序求各顶点的 vl 值 */

	while(!IsEmpty(&T)){ 

 		Pop(&T,&j);

		p=G.vertex[j].firstarc;

		while(p!=NULL){

            k=p->adjvex;

            dut=p->weight;

 			if(vl[k]-dut<vl[j]) vl[j]= vl[k]-dut;

 			p=p->nextarc;

 		}

 	}

    /* 求 ei,li 和关键活动 */

	for(j=0;j<G.vexnum;j++){ 

  		p=G.vertex[j].firstarc;

		while(p!=NULL){

    	    k=p->Adjvex;

    	    dut=p->Info.weight;

 			ei=ve[j];li=vl[k]-dut;

			tag = (ei==li) ? '*' : ' ' ; /* 标记并输出关键活动 */

			printf("%c,%c,%d,%d,%d,%c\n",G.vertex[j].data,G.vertex[k].data,dut,ei,li,ta

g);	

 			p=p->nextarc;

 		}

 	}

	return(Ok);

} /*CriticalPath*/

// 图的最短路径算法

#define INFINITY 32768 /* 表示极大值，即∞*/

typedef unsigned int WeightType;

typedef WeightType AdjType;

typedef SeqList VertexSet;

/* path [i] 中存放顶点 i 的当前最短路径。dist [i] 中存放顶点 i 的当前最短路径长度 */

void ShortestPath_DJS(AdjMatrix g, int v0,WeightType dist[MAX_VERTEX_NUM],VertexSet path[MAX_VERTEX_NUM] ){

	VertexSet s; /* s 为已找到最短路径的终点集合 */

    /* 初始化 dist [i] 和 path [i] */

	for ( i =0;i<g.vexnum ;i++) {

        InitList(&path[i]);

		dist[i]=g.arcs[v0][i].adj;

	 	if ( dist[i] < INFINITY){

            AddTail(&path[i], g.vertex[v0]); /* AddTail 是表尾添加操作 */

			AddTail(&path[i], g.vertex[i]);

	 	}

	}

	InitList(&s);

	AddTail(&s, g.vertex[v0]); /* 将 v0 看成第一个已找到最短路径的终点 */

    /* 求 v0 到其余 n-1 个顶点的最短路径 (n= g.vexnum)*/

	for ( t = 1; t<=g.vexnum-1; t++) {

		min= INFINITY;

		for ( i =0; i<g.vexnum;i++)

			if (! Member(g.vertex[i], s) && dist[i]<min ) {

                k =i;

                min=dist[i];

            }

		AddTail(&s, g.vertex[k]);

         /* 修正 dist [i], i∈V-S*/

		for ( i =0; i<g.vexnum;i++)

	 	if (!Member(g.vertex [i], s) && g.arcs[k][i].adj!= INFINITY	&& (dist[k]+ g.arcs [k][i].adj<dist[i])){

			dist[i]=dist[k]+ g.arcs [k][i].adj;

			path[i]=path[k];

	 		AddTail(&path[i], g.vertex [i]); /* path[i]=path[k]∪{Vi} */

		}

	}

}

// 弗洛伊德算法

typedef SeqList VertexSet;

/* g 为带权有向图的邻接矩阵表示法， path [i][j] 为 vi 到 vj 的当前最短路径，dist [i][j] 为 vi 到 vj 的当前最短路径长度 */

void ShortestPath_Floyd(AdjMatrix g,WeightType dist [MAX_VERTEX_NUM] [MAX_VERTEX_NUM],VertexSet path[MAX_VERTEX_NUM] [MAX_VERTEX_NUM] ){

    /* 初始化 dist [i][j] 和 path [i][j] */

	for (i=0; i<g.vexnumn; i++) 

		for (j =0;j<g.vexnum; j++){

	 		InitList(&path[i][j]);

			dist[i][j]=g.arcs[i][j].adj;

	 		if (dist[i][j]<INFINITY){

                AddTail(&path[i][j], g.vertex[i]);

				AddTail(&path[i][j], g.vertex[j]);

	 		}

		}

	for (k =0;k<g.vexnum;k++)

		for (i =0;i<g.vexnum;i++)

	 		for (j=0;j<g.vexnum;j++)

	 			if (dist[i][k]+dist[k][j]<dist[i][j]){

                    dist[i][j]=dist[i][k]+dist[k][j];

			 		paht[i][j]=JoinList(paht[i][k], paht[k][j]);

				} /* JoinList 是合并线性表操作 */

}