#define VertexMax 100 //最大顶点数为100
#define MaxInt 32767 //表示最大整数，表示 ∞
#define Maxsize 100 //队列最大元素个数100 

typedef char VertexType; //每个顶点数据类型为字符型
typedef  int dataType;

typedef struct
{
	char Vertex[100];//存放顶点元素的一维数组,VertexType表示元素的数据类型
	int AdjMatrix[1][100];//邻接矩阵二维数组 
	int vexnum, arcnum;//图的顶点数和边数
}MGraph;

//查找元素v在一维数组 Vertex[] 中的下标，并返回下标 
int LocateVex(MGraph* G, char v)
{
	int i;

	for (i = 0; i < G->vexnum; i++)
	{
		if (v == G->Vertex[i])
		{
			return i;
		}
	}

	printf("No Such Vertex!\n");
	return -1;
}

//无向图和有向图
void CreateUDG(MGraph* G)
{
	int i, j;
	//1.输入顶点数和边数
	printf("输入顶点个数和边数(用逗号隔开)：");
	scanf("%d,%d", &G->vexnum, &G->arcnum);
	printf("\n");

	//2.输入顶点元素 
	printf("输入顶点元素(无需空格隔开)：");
	scanf("%s", G->Vertex);
	printf("\n");
	//3.矩阵初始化
	for (i = 0; i < G->vexnum; i++)
		for (j = 0; j < G->vexnum; j++)
		{
			G->AdjMatrix[i][j] = 0;
		}

	//4.构建邻接矩阵
	int n, m;
	cv1, v2;

	printf("请输入边的信息：\n");
	for (i = 0; i < G->arcnum; i++)
	{
		scanf(" %c%c", &v1, &v2);
		n = LocateVex(G, v1); //获取v1所对应的在Vertex数组中的坐标 
		m = LocateVex(G, v2); //获取v2所对应的在Vertex数组中的坐标

		if (n == -1 || m == -1)
		{
			printf("NO This Vertex!\n");
			return;
		}

		G->AdjMatrix[n][m] = 1;   // 创建有向图
	//	G->AdjMatrix[m][n] = 1;      创建无向图
    //  G->AdjMatrix[n][m] = w;      将1改为w，而将0改为∞，则是网
	}
}

typedef struct ArcNode//边表 
{
	int adjvex;//存储的是该顶点在顶点数组即AdjList[]中的位置  下标域
	struct ArcNode *next;  //指针域，用于连接后续结点
}ArcNode;

typedef struct VNode //单个顶点 
{
	 int vertex;  //数据域   
	//int weight；//存储网的时候需要添加此项
	struct ArcNode *firstarc;   //第一个孩子节点  指针域，用于连接边表
}VNode;

typedef struct //顶点表 
{
	VNode AdjList[VertexMax];//由顶点构成的结构体数组 
	int vexnum,arcnum; //顶点数n和边数e 
}ALGraph;

//邻接矩阵法

int visitedBFS[VertexMax];//定义"标志"数组为全局变量 
void BFS(MGraph *G,int i)
{
	int j;
	CyQueue q;    //队列
	create(&q);   //初始化队列
	
    //1.设置起始点 
	printf("%c",G->Vertex[i]);//1.输出起始结点 
	visited[i]=1;//2.将已访问的结点标志成1
	EnQueue(&q,i);//3.将第一个结点入队 

    //2.由起始点开始，对后续结点进行操作 
	while(!QueueEmpty(&q))//队列非空
	{
		DeQueue(&q,&i);	  //出队  i的值根据出队的元素在变
		for(j=0;j<G->vexnum;j++)
		{
			if(G->AdjMatrix[i][j]==1&&visited[j]==0) //如果矩阵内存在路径
			{
			   printf("%c",G->Vertex[j]);//输出符合条件的顶点 
	            visitedBFS[j]=1;//设置成已访问状态1 
	            EnQueue(&q,j);//入队 j的值根据入队的元素在变
			}
		}
	} 	
} 
//为了避免孤岛结点无法被遍历到，需要确认visit数组都为1
void BFSTraverse(MGraph *G)
{
	int i;
	
	//数组初始化为全0 
	for(i=0;i<G->vexnum;i++)
	{
		visited[i]=0;
	} 
	
	for(i=0;i<G->vexnum;i++)
	{
		if(visited[i]==0)
		{
			BFS(G,i);
		}
	}
} 

int visitedDFS[VertexMax];//定义"标志"数组为全局变量 

void DFS(MGraph* G, int i)
{
	int j;

	//1.处理起始点 
	printf("%c", G->Vertex[i]);//1.输出起始结点 
	visitedDFS[i] = 1;//2.将已访问的结点标志成1

	 //2.由起始点开始，对后续结点进行操作
	for (j = 0; j < G->vexnum; j++)//依次搜索vi的邻接点 
	{
		if (G->AdjMatrix[i][j] == 1 && visitedDFS[j] == 0)
            //当满足有边且未被访问过时，递归调用去查找该邻接点 
		{
			DFS(G, j);//注意此处的G已经是指针类型，不需要再&G 
		}
	}
}
void DFSTraverse(MGraph* G)
{
	int i;
	//初始化"标志"数组为0，代表未访问
	for (i = 0; i < G->vexnum; i++)
	{
		visitedDFS[i] = 0;
	}
	for (i = 0; i < G->vexnum; i++)
	{
		if (visitedDFS[i] == 0)
		{
			DFS(G, i);//注意此处的G已经是指针类型，不需要再&G 
		}
    }
}

typedef struct
{
	VertexType begin;//起点
	VertexType end;//终点
	int weight;
}Edge;//边集数组edge[]的单元 

typedef struct
{
	VertexType Vertex[VertexMax];//顶点数组 
	Edge edge[VertexMax];//边集数组 
	int vexnum;//顶点数 
	int edgenum;//边数 
}EdgeGraph;

//选用简单排序
void sort(EdgeGraph *E)
{
	int i,j;
	Edge temp;
	
	for(i=0;i<E->edgenum-1;i++)
	{
		for(j=i+1;j<E->edgenum;j++)
		{
			if(E->edge[i].weight>E->edge[j].weight)
			{
				temp=E->edge[i];
				E->edge[i]=E->edge[j];
				E->edge[j]=temp;
			}
		}
	}
}

int FindRoot(int t,int parent[])//t接收到是结点在Vertex数组中的下标 
{
	while(parent[t]>-1)//parent=-1表示没有双亲，即没有根节点 
	{
		t=parent[t];//逐代查找根节点 
	}
	
	return t;//将找到的根节点返回，若没有根节点返回自身 
}

void MiniSpanTree_Kruskal(EdgeGraph *E)
{
	int i;
	int num;//生成边计数器，当num=顶点数-1 就代表最小生成树生成完毕 
	int root1,root2; 
	int LocVex1,LocVex2; 
	int parent[VertexMax];
    //用于查找顶点的双亲，判断两个顶点间是否有共同的双亲，来判断生成树是否会成环 
	
	//1.按权值从小到大排序 
	sort(E);
	print(E);
	//2.初始化parent数组 
	for(i=0;i<E->vexnum;i++)
	{
		parent[i]=-1;
	}
	
	printf("\n 最小生成树(Kruskal):\n\n");
	//3.
	for(num=0,i=0;i<E->edgenum;i++)
	{
		LocVex1=LocateVex(E,E->edge[i].begin);
		LocVex2=LocateVex(E,E->edge[i].end);
		root1=FindRoot(LocVex1,parent);
		root2=FindRoot(LocVex2,parent);
		
		if(root1!=root2)//若不会成环，则在最小生成树中构建此边 
		{
              printf("\t\t%c-%c w=%d\n",E->edge[i].begin,E->edge[i].end,E>edge[i].weight);
            //输出此边 
			parent[root2]=root1;//合并生成树
			num++;
			
			if(num==E->vexnum-1)//若num=顶点数-1，代表树生成完毕，提前返回 
			{
				return;
			}
		} 
	}	
}

int FindMinDist(int dist[],int s[],int vexnum) 
{
	int i;
	int loc;
	int min=MaxInt+1;
	for(i=0;i<vexnum;i++)
	{
		if(s[i]==0)//只对s[i]=0的顶点进行查找 
		{
			if(dist[i]<min)
			{
				min=dist[i];
				loc=i;
			}
		}
	}
	return loc;//返回dist中最小元素的下标 
}

void ShortestPath_Dijkstra(MGraph *G,VertexType start)
{
	int i,j,num;
	int loc;
	int min;
	int dist[VertexMax];//最短路径长度数组 
	int path[VertexMax];//最短路径数组 
	int s[VertexMax];
    //代表集合S（1代表该顶点已处理，属于集合S；0代表该顶点未处理，不属于集合S，属于集合V-S） 
	
	//1.初始化dist和path数组 
	loc=LocateVex(G,start);//获取源点的下标位置 
	for(i=0;i<G->vexnum;i++)
	{
		dist[i]=G->AdjMatrix[loc][i];//初始化dist数组
		
		if(dist[i]!=MaxInt)//初始化path数组
		{
			path[i]=loc;
		}
		else
		{
			path[i]=-1;
		}	  
	} 
    
//2.初始化S数组(s数组：代表集合S，1代表该元素属于集合S(已处理的顶点),0该元素不属于集合S(未处理的顶点)) 
    for(i=0;i<G->vexnum;i++)
	{
		s[i]=0;
	} 
	s[loc]=1;//代表起始点(源点)以处理完毕 
	num=1;
	
	//3.
	while(num<G->vexnum)
	{
		min=FindMinDist(dist,s,G->vexnum);
        //在dist数组中查找其对应s[i]=0，即未处理的最小值元素 
		s[min]=1;//将找到的最短边所对应的的顶点加入集合S
		
		for(i=0;i<G->vexnum;i++)//加入新的顶点后，更新dist和path数组 
		{
			if((s[i]==0)&&(dist[i]>dist[min]+G->AdjMatrix[min][i]))//路径累加
			{
				dist[i]=dist[min]+G->AdjMatrix[min][i];
				path[i]=min;
			}
		}
	    num++;	
	}    
} 

int dist[VertexMax][VertexMax];
int path[VertexMax][VertexMax];

void ShortestPath_Floyd(MGraph G)
{
	int i,j,k;
    //初始化部分
	for(i=0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)
		{
			dist[i][j]=G.AdjMatrix[i][j];
			
			if(dist[i][j]!=MaxInt)
		            {
		              	path[i][j]=i;//存入前驱 
					}
			else path[i][j]=-1;
		}
	}
	
   //Floyd算法核心部分
	for(k=0;k<G.vexnum;k++)//拿出每个顶点作为遍历条件
	 for(i=0;i<G.vexnum;i++)
	  for(j=0;j<G.vexnum;j++)
	   {
	   	    if(dist[i][j]>dist[i][k]+dist[k][j])
	   	    {
	   	    	dist[i][j]=dist[i][k]+dist[k][j];
	   	    	path[i][j]=path[k][j];//存入前驱 
			} 
       }

}	  

typedef struct ArcNode//边表 
{
	int adjvex;//存储的是该顶点在顶点数组即AdjList[]中的位置 
	struct ArcNode *next;
}ArcNode;

typedef struct VNode //单个顶点 
{
	char data;  //数据域
	struct ArcNode *firstarc;   //第一个孩子节点
}VNode;

typedef struct //顶点表 
{
	VNode AdjList[MAX];//由顶点构成的结构体数组 
	int vexnum,arcnum; //顶点数n和边数e 
}ALGraph;

int indegree[MAX];//用来存储所有节点的入度之和

void FindInputDgeree(ALGraph G){//计算所有节点的入度
	ArcNode *p;   //临时边表变量
	int i;
 
	for(i = 0; i < G.vexnum; i ++)
		indegree[i] = 0;         //初始化入度数组
 
	for(i = 0; i < G.vexnum; i ++){
		p = G.AdjList[i].firstarc;    //p设置为顶点的第一条边
 
		while(p){            //如果边不为空
			indegree[p->adjvex] ++;  //顶点的对应位置的度+1
			p = p->next;
		}
	}
}

void TopologicalSort(ALGraph *G)
{   
	int i;
	int count=0;
 //用于统计拓扑排序生成的结点数（若生成结点数 < 图的结点数，则代表图中有环，拓扑排序不成功） 
 //顺便检测了图中是否存在环
    SqStack S;   //文中说的space就是此处的栈结构
    ArcNode *p;//临时边表变量 
    
    InitStack(S);   //初始化栈
    
	FindInputDegree(G); //求入度
    
    //2.初始化部分：将初始入度为0的顶点序号入栈
	for(i=0;i<G->vexnum;i++)
	{
		if(indegree[i]==0)   
		{
			Push(S,i);    
		}	
	} 
    
    //3.拓扑排序
    while(!StackEmpty(S)){
		Pop(S,i);    //pop操作会改变i的值
		printf("%c",G.AdjList[i].data);	 //输出栈顶元素 
                count++;
 
		p = G.AdjList[i].firstarc;  //p为结点的第一条边
		while(p)
        {
             indegree[p->adjvex]--;       //p->adjvex代表的的A-->B中的B的序号1
			if(indegree[p->adjvex]==0)//判断去掉一条边后节点的入度是否为零
            {
                Push(S,p->adjvex);  //如果入度为0，压入栈中
            }
			p = p->next;     //下一条边
		}
	
	//4.判断拓扑排序是否成功（生成结点数 < 图的结点数，则代表图中有环，拓扑排序不成功） 
	if(count<G->vexnum) 
	   printf("TopologicalSort Failed!\n");
	else return;     
}

//邻接矩阵实现拓扑排序

void FindInDegree(MGraph G){//计算图中各节点的入度
	int i,j;
	for(i = 0; i < G.vexnum; i ++){
		for(j = 0; j < G.vexnum; j ++)
			if(G.AdjMatrix[i][j])//当两顶点之间存在边时，入度自加
				indegree[j] ++;  //列表示入度
	}
}

void TopologicalSort(MGraph G){
	FindInDegree(G);
	SqStack S;                //使用栈存储
	int i,j,count = 0;
	InitStack(S);           //初始化栈
 
	for(i = 0; i < G.vexnum; i ++)
		if(indegree[i]==0)
			Push(S,i);//把入度为零的节点压栈
     
	printf("拓扑序列如下:\n");
	while(!StackEmpty(S)){
		Pop(S,i);
		printf("%c\n",G.Vertex[i]);		
         count ++;
 
		for(j = 0; j < G.vexnum; j ++){
			if(G.AdjMatrix[i][j]！=0){
                indegree[j]--;       //删除出栈结点向对应的边，让其相邻结点的入度-1
				if(indegree[j]==0)   //如果入度为0，进栈
					Push(S,j);
			}
		}
	}
 
	if(count < G.vexnum)
		printf("此图有环存在!\n");
}

void DFS(MGraph* G, int i)
{
	int j;

	//1.处理起始点 

	visitedDFS[i] = 1;//2.将已访问的结点标志成1

	 //2.由起始点开始，对后续结点进行操作
	for (j = 0; j < G->vexnum; j++)//依次搜索vi的邻接点 
	{
		if (G->AdjMatrix[i][j] == 1 && visitedDFS[j] == 0)
            //当满足有边且未被访问过时，递归调用去查找该邻接点 
		{
			DFS(G, j);//注意此处的G已经是指针类型，不需要再&G 
		}
	}
    printf("%c", G->Vertex[i]);//逆拓扑排序，在出栈时输出 
}

void DFSTraverse(MGraph* G)
{
	int i;
	//初始化"标志"数组为0，代表未访问
	for (i = 0; i < G->vexnum; i++)
	{
		visitedDFS[i] = 0;
	}
	for (i = 0; i < G->vexnum; i++)
	{
		if (visitedDFS[i] == 0)
		{
			int x;
			x= DFS(G, i);//注意此处的G已经是指着类型，不需要再&G 
			if (x == false) {
				printf("false");
			}
		}
	}
}
/*深度优先遍历DFS*/
int visitedDFS[VertexMax];//定义"标志"数组为全局变量 
bool DFS(MGraph* G, int i)
{
	int j;
	//1.处理起始点 
	if (1 == visitedDFS[i])
		return true;
	if (-1 == visitedDFS[i])
		return false;
	visitedDFS[i] = -1;
	 //2.由起始点开始，对后续结点进行操作
	for (j = 0; j < G->vexnum; j++)//依次搜索vi的邻接点 
	{
		if (G->AdjMatrix[i][j] == 1)//当满足有边时，递归调用去查找该邻接点 
    //此处要把visitedDFS[j] == 0的条件删掉，因为有向无环图是不可能递归到父节点的
		{
			DFS(G, j);//注意此处的G已经是指针类型，不需要再&G 
			if (DFS(G,j) == false) {
				return false;
			}
		}
	}
	visitedDFS[i] = 1;
	return true;
}

void CriticalPath(ALGraph *G)
{
	int i;
	int j,k;// <Vj,Vk>
	int e,l;//活动最早开始时间/活动最晚开始时间  
	int topo[VertexMax];//拓扑数组，用于存储拓扑排序结果（存储内容是每个结点的坐标） 
	int ve[VertexMax]; //事件vi的最早发生时间 
	int vl[VertexMax]; //事件vi的最晚发生时间 
	struct ArcNode *p;
	
	//1.调用拓扑排序，检测图是否存在环 
	if(!TopologicalSort(G,topo))//若拓扑排序成功，topo数组也将处理完毕 
		 return; 
		 
	//2.正拓扑排序，求出事件最早发生时间 
	for(i=0;i<G->vexnum;i++)
	    ve[i]=0;//所有ve都初始化为0
	for(i=0;i<G->vexnum;i++)
	{
		j=topo[i];//j为起始点，k为终点 
		p=G->AdjList[j].firstarc;//用指针p去依次寻找j的每一个邻接点 
		while(p)
		{
			k=p->adjvex;
			if(ve[k]<ve[j]+p->weight)
             //根据j的邻接点k，不断更新ve[]的值（选出最大值，原理类似于选择排序） 
			{
				ve[k]=ve[j]+p->weight;
			}
			p=p->next;    
		}
	}	 
	//3.逆拓扑排序，求出事件最迟发生时间 
	for(i=0;i<G->vexnum;i++)
	    vl[i]=ve[G->vexnum-1];//所有vl都初始化为ve[G->vexnum-1]
	for(i=G->vexnum-1;i>=0;i--)
	{
		j=topo[i];
		p=G->AdjList[j].firstarc;//让p去依次查找邻接点 
		while(p)
		{
			k=p->adjvex;
			if(vl[j]>vl[k]-p->weight)
               //根据j的邻接点k，不断更新vl[]的值（选出最小值，原理类似于选择排序）
			{
				vl[j]=vl[k]-p->weight;
			}
			p=p->next;
		}
	}      	 
	//4.计算e和l，通过判断e是否等于l确定该活动是否是关键活动，从而确定关键路径
	for(i=0;i<G->vexnum;i++)
	{
		p=G->AdjList[i].firstarc;//让p去依次查找邻接点 
		while(p)
		{
			j=p->adjvex;
			e=ve[i];//计算活动最早开始时间 e 
			l=vl[j]-p->weight;//计算活动最晚开始时间 l 
			
			
			if(e==l)//如果e=l，说明该活动是关键活动 
			{
			    //把每个关键活动输出，即是关键路径
	printf("\t%c->%c(%d)\n",G->AdjList[i].vertex,G->AdjList[j].vertex,p->weight);
			}
			p=p->next;
		}
	} 
}