1. 图的基础概念

• 图的定义: 由顶点的有穷非空集合和顶点之间边的集合组成的数据类型
• 图的表示:G(V,E),G表示一个图,V是图G的顶点集合,E为图G的边的集合
• 图的逻辑结构:多对多
• 图的存储结构:邻接矩阵 邻接表 十字链表 邻接多重表
• 图的一些无聊术语:
  1. 顶点i与j之间的边无方向,则称此边为无向边(Edge),无向边构成的图成为无向图,无序偶表示(i,j)
  2. 若i到j有方向,则叫有向边,也成为弧(Arc),i叫弧尾,j叫弧头,有序偶表示:<i,j>
  3. 任意两顶点都存在边的图称为(有向|无向)完全图
  4. 边少的图成为稀疏图,反之稠密图
  5. 带权的图称为网
  6. 以顶点v为头的弧的数目称为v的入度,对应的叫出度
  7. 路径:从顶点a到顶点b的一个序列叫路径
  8. 路径长度:路径上的边或者弧的数目
  9. 连通:从顶点i到顶点j有路径,则称i和j是连通的
  10. 连通图:图中任何两个顶点都是连通的图

2.图的两种遍历

• 图的创建一般用邻接表或者邻接矩阵,下面依次给出图的邻接矩阵和邻接表的创建及两种遍历
• 图的遍历方式有两种:深度优先遍历(DFS) 广度优先遍历(BFS)

邻接表创建并遍历图代码(粘贴即可运行):

#include <iostream>
#include <stdlib.h>
using namespace std;
#define maxSize 100
int visit[maxSize];
typedef struct EdgeNode{//边结点(其实就是尾顶点) 
	int adjvex;//当前顶点下标 
	int weight;//边的权值 
	struct EdgeNode *next;//指向下一个边结点的指针 
}EdgeNode;

typedef struct VNode{//顶点结点 
	int data;//数据域 
	EdgeNode *firstEdg;//指向与之相邻接的边结点 
}VNode;

typedef struct AGraph{//图结点 
	VNode adjList[maxSize];//顶点数组 
	int numVNode,numEdge;//顶点数和边数 
}AGraph;

void createGraph(AGraph &G){//创建无向图 (因为要真正改变G,所以要传引用&) 
	int numVNode,numEdge,i,j,k;
	EdgeNode *s,*p;
	printf("请输入顶点个数和边数\n");
	scanf("%d %d",&numVNode,&numEdge);
	G.numEdge=numEdge;
	G.numVNode=numVNode; 
	printf("请输入顶点\n");
	for(i=0;i<numVNode;i++){//输入顶点 
		scanf("%d",&G.adjList[i].data);
		G.adjList[i].firstEdg=NULL;
	}
	
	printf("请输入边(vi,vj)的顶点的下标,格式为:i j\n");
	for(k=0;k<numEdge;k++){
		
		scanf("%d %d",&i,&j);
		s=(EdgeNode *)malloc(sizeof(EdgeNode));
		s->adjvex=j;
		s->next=G.adjList[i].firstEdg;
		G.adjList[i].firstEdg=s;
		p=(EdgeNode *)malloc(sizeof(EdgeNode));
		p->adjvex=i;
		p->next=G.adjList[j].firstEdg;
		G.adjList[j].firstEdg=p;
	} 
}
void dfs(AGraph G,int i){//深度优先遍历顶点i(类似二叉树的前序遍历) 
	printf("%d ",G.adjList[i].data);//先访问顶点 
	visit[i]=1;//然后标记被访问顶点 
	EdgeNode *p;
	p=G.adjList[i].firstEdg; 
	while(p!=NULL){//接着遍历被访问顶点的边表 
		if(visit[p->adjvex]!=1){//若顶点未访问 
			dfs(G,p->adjvex);//则递归调用 
		}
		p=p->next;
	}
} 

void dfsTravering(AGraph G){//dfs方法中只能遍历连通图的所有顶点,而此方法则能遍历有独立顶点的图的所有顶点 
	for(int i=0;i<G.numVNode;i++){
		visit[i]=0;//标记数组初始化 
	}
	printf("深度优先遍历的结果为:\n");
	for(int i=0;i<G.numVNode;i++){//遍历所有顶点 
		if(visit[i]!=1){//未访问的顶点 
			dfs(G,i);//从下标为0的开始访问 
		} 
	}
	printf("\n");
}

void bfs(AGraph G,int v){//广度优先遍历下标为v的顶点及和其相邻接的顶点(类似二叉树的广度遍历) 
	int que[maxSize];//注:队列存放的都是顶点下标 
	int front,rear;front=rear;//初始化队头队尾指针 
	int i,j;
	EdgeNode *p;//边结点 
	printf("%d ",G.adjList[v].data);//先访问结点,再标记,接着入队 
	visit[v]=1;
	rear=(rear+1)%maxSize;//注:循环队列进出队都是先移指针再改数据 
	que[rear]=v;//顶点下标v入队 
	while(rear!=front){//循环条件:队不为空 
		front=(front+1)%maxSize;
		i=que[front];//出队 
		p=G.adjList[i].firstEdg;//出队顶点指向的边结点 
		while(p!=NULL){//遍历出队顶点的边表 
			if(visit[p->adjvex]!=1){//顶点未曾访问过 
				printf("%d ",G.adjList[p->adjvex].data);//访问顶点 
				visit[p->adjvex]=1;//标记 
				rear=(rear+1)%maxSize;//入队 
				que[rear]=p->adjvex;
			}
			p=p->next;//边结点往下走 
		}
	}
}

void bfsTravering(AGraph G){//广度优先遍历(当图不是连通图时需要这个方法) 
	for(int i=0;i<G.numVNode;i++){
		visit[i]=0;//初始化标记数组 
	}
	printf("广度优先遍历结果:\n");
	for(int i=0;i<G.numVNode;i++){
		if(visit[i]!=1){//不为1说明顶点未曾访问 
			bfs(G,i);
		}
	}
	printf("\n");
}
int main(int argc, char** argv) {
	AGraph G;
	createGraph(G);
	dfsTravering(G); 
	bfsTravering(G);
	return 0;
}
/*
示例输入:
顶点数:10 边数:13
顶点:0 1 2 3 4 5 6 7 8 9
边下标:
0 2
0 1
1 4
1 3
2 5
2 3
3 4
4 7
4 6
5 7
6 9
7 8
8 9
*/

邻接矩阵创建并遍历图代码(粘贴即可运行):

#include <iostream>
#define maxSize 100
#define infinity 65535
using namespace std;
bool visit[100]={false};
typedef struct {//图结点 
	int vertext[maxSize];//顶点数组 
	int edge[maxSize][maxSize]; //邻接矩阵(matrix) 
	int n,e;//图的顶点数和边数 
}MGraph; 

void createGraph(MGraph &G){//用邻接矩阵创建无向图 
	int i,j,k,weight;
	printf("请输入顶点数和边数\n");
	scanf("%d %d",&G.n,&G.e);
	printf("请输入顶点:\n");
	for(i=0;i<G.n;i++){
		scanf("%d",&G.vertext[i]);//输入顶点 
	} 
	for(i=0;i<G.n;i++){
		for(j=0;j<G.n;j++){//初始化数组 
			G.edge[i][j]=infinity;
		}
	} 
	printf("请输入边的顶点下标i j及边的权重w\n");
	for(k=0;k<G.e;k++){
		scanf("%d %d %d",&i,&j,&weight);
		G.edge[i][j]=weight;
		G.edge[j][i]=G.edge[i][j];//无向图的邻接矩阵是对称的 
	}
}

void dfs(MGraph G,int v){//深度优先遍历算法 (类似前序遍历) 
	int i;
	printf("%d ",G.vertext[v]);//先访问 
	visit[v]=true;//再标记 
	for(i=0;i<G.n;i++){//最后遍历所有没访问过且与下标为v的顶点相邻的顶点,递归dfs 
		if(!visit[i]&&G.edge[v][i]!=infinity){
			dfs(G,i);
		}
	} 
}

void dfsTravering(MGraph G){//若不是连通图,则需要一个个检查顶点是否遍历过(连通图不需要,直接调用dfs方法即可) 
	for(int i=0;i<G.n;i++){
		visit[i]=false;
	}
	for(int i=0;i<G.n;i++){
		if(!visit[i]){
			dfs(G,i);
		}
	}
}

void bfs(MGraph G,int v){//广度优先搜索遍历 
	int i,j;
	int que[maxSize];
	int front,rear;
	front=rear=0;
	printf("%d ",G.vertext[v]);
	visit[v]=true;
	rear=(rear+1)%maxSize;
	que[rear]=v;
	while(front!=rear){
		front=(front+1)%maxSize;
		i=que[front];
		for(j=0;j<G.n;j++){
			if(!visit[j]&&G.edge[i][j]!=infinity){//没有被访问且顶点之间相邻接
				printf("%d ",G.vertext[j]); 
				visit[j]=true;
				rear=(rear+1)%maxSize;
				que[rear]=j; 
			}
		}
	} 
}
int main(int argc, char** argv) {
	MGraph G;
	createGraph(G);
	dfs(G,8);
	dfsTravering(G);
	bfs(G,5);
	return 0;
}
/*
实例输入:
顶点数:10,边数:13
顶点:0 1 2 3 4 5 6 7 8 9
边顶点下标及权值:
0 2 4
0 1 3
1 4 6
1 3 5
2 5 7
2 3 8
3 4 3
4 7 4
4 6 9
5 7 6
6 9 2
7 8 5
8 9 3
*/

**深度优先遍历4部曲(dfs): **

1. 先访问给定下标为v的顶点
2. 再标记已访问顶点下标
3. 遍历已访问顶点的边表
4. 边表的顶点下标未曾被标记,则递归调用dfs(G,v)

广度优先遍历6部曲(bfs) :

1. 先访问给定顶点下标v的顶点
2. 再标记下标为v的顶点
3. 接着将下标为v的顶点入队
4. 然后遍历下标为v的顶点的边表
5. 随后将边表中未曾标记的顶点依次入队
6. 一个一个出队,重复执行以上步骤

3. 最小生成树两种经典算法(prim和kruskal)

• 一个连通图的生成树是图的一个极小连通子图,它包含所有顶点,但只有足以构成树的n-1条边

• 这意味着对生成树来说,砍去它的任何一条边,就会使生成树变成非连通图,若给他增加一条边就会形成一条回路

• 最小生成树:权值最小的那颗生成树叫~

• 最小生成树的性质:

  1. 最小生成树并不唯一,准确的来说是最小生成树的树形并不唯一
  2. 最小生成树的权值之和唯一,并且是最小的
  3. 最小生成树的边数=顶点数-1

• 求最小生成树有两种经典算法:普里姆算法(prim)和克鲁斯卡尔(kruskal)算法

普里姆算法求最小生成树代码(粘贴即能跑)

#include <iostream>
#include<stdlib.h>
#define maxSize 100
#define infinity 65535
using namespace std;
typedef struct{
	char vnode[maxSize];
	int edge[maxSize][maxSize];
	int n,e;
}MGraph; 

void createMGraph(MGraph &G){//邻接矩阵构造图 
	int i,j,n,e,k,w;
	cout<< "请输入图的顶点数和边数"<<endl;
	cin>> G.n >> G.e;
	n=G.n;
	e=G.e;
	cout<< "请输入顶点"<<endl;
	for(i=0;i<n;i++){
		cin>> G.vnode[i]; 
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			G.edge[i][j]=infinity;
		}
	}
	cout<< "请输入边的下标i,j"<<endl;
	for(k=0;k<e;k++){
		scanf("%d %d %d",&i,&j,&w);
		G.edge[i][j]=w;
		G.edge[j][i]=G.edge[i][j];
	} 
}

void minSpanTree_prim(MGraph G){//prim算法求最小生成树 
	int n,e,i,j,min,k,t;
	n=G.n;
	int lowcost[maxSize];//为0表示顶点加入最小生成树,其他存放边的权值 
	int adjvex[maxSize];//这个存放顶点下标,标明顶点是新增顶点,还是之前遍历过的顶点 
	lowcost[0]=0;//把首个顶点(下标为0的顶点)加入到最小生成树 
	adjvex[0]=0;//下标为0 
	for(i=1;i<n;i++){//循环0下标顶点与其他顶点的连接情况 (不从0开始是因为0 0表示自己和自己的环) 
		lowcost[i]=G.edge[0][i];//把0下标顶点和其他顶点组成的边的权值存放到lowcost数组中 
		adjvex[i]=0;//当前lowcost数组中的边的权值的起始顶点全部都是下标为0的顶点,而结束顶点则是序号为lowcost数组下标的顶点 
	}
	cout<<"最小生成树为:"<<endl; 
	for(t=1;t<n;t++){//循环所有顶点,构造最小生成树 
		min=infinity;//初始化min,刚开始为一个极大值 
		j=1;k=0;
		while(j<n){//遍历lowcost数组 
			if(lowcost[j]!=0&&lowcost[j]<min){//除去已加入最小生成树的顶点 
				min=lowcost[j];//找出lowcost数组中最小的权值,并赋值给min 
				k=j;//记录最小权值的下标 (这个k其实就是权值最小的那条边的结束顶点) 
			}
			j++;
		}
		printf("(%d,%d)\n",adjvex[k],k);//打印权值最小的那条边的起始顶点和结束顶点 
		lowcost[k]=0;//把k下标的顶点加入到最小生成树 
		for(i=1;i<n;i++){//遍历顶点 
			if(lowcost[i]!=0&&G.edge[k][i]<lowcost[i]){//要除去已加入最小生成树的顶点 
				lowcost[i]=G.edge[k][i];//在k结点与其他顶点邻接的权值和lowcost数组中取较小的一方更新lowcost 
				adjvex[i]=k;//记录较小权值的边的起始顶点下标 
			}
		}
	}
}
int main(int argc, char** argv) {
	MGraph G;
	createMGraph(G);
	minSpanTree_prim(G);
	return 0;
}
	/*
	示例输入:
		顶点数和边数: 9 15
		输入顶点:	0 1 2 3 4 5 6 7 8
		输入顶点下标和权值: 
				4 7 7
				2 8 8
				0 1 10
				0 5 11
				1 8 12
				3 7 16
				1 6 16
				5 6 17
				1 2 18
				6 7 19
				3 4 20
				3 8 21
				2 3 22
				3 6 24
				4 5 26
	*/

克鲁斯卡尔算法构造最小生成树代码:

#include <iostream>
#include<algorithm>
#include<stdlib.h>
#define maxSize 100
#define infinity 65535
using namespace std;
typedef struct{//邻接矩阵构造的图结点 
	char vnode[maxSize];
	int edge[maxSize][maxSize];
	int n,e;
}MGraph; 

typedef struct{//边集结点(存放边的顶点下标和边的权重) 
	int start;//边起点 
	int end;//边终点 
	int w;//边权值 
}Road; 
Road road[maxSize];//边集数组
int parent[maxSize];
int getRoot(int i){//此函数用于找到下标为i的顶点在生成树中的父节点 (并查集) 
	while(parent[i]!=i){  
		i=parent[i];
	}
	return i;
}

bool compare(Road x,Road y){//自定义结构体比较方式,按结构体中的权值升序排 
	return x.w<y.w;
}

void createMGraph(MGraph &G){//创建图 
	int i,j,n,e,k,w;
	cout<< "请输入图的顶点数和边数"<<endl;
	cin>> G.n >> G.e;
	n=G.n;
	e=G.e;
	cout<< "请输入顶点"<<endl;
	for(i=0;i<n;i++){
		cin>> G.vnode[i]; 
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			G.edge[i][j]=infinity;
		}
	}
	cout<< "请输入边的下标i,j"<<endl;
	for(k=0;k<e;k++){
		scanf("%d %d %d",&i,&j,&w);
		G.edge[i][j]=w;
		road[k].start=i;//创建的时候就给边集数组赋值
		road[k].end=j;
		road[k].w=w;
		G.edge[j][i]=G.edge[i][j];//根据无向图邻接矩阵的对称性赋值
	} 
}

int kruskal(MGraph G){//克鲁斯卡尔算法 
	int a,b,sum=0;
	int e=G.e;
	for(int i=0;i<G.e;i++){//初始化根结点下标数组 
		parent[i]=i;//为存放根节点下标数组赋初值,自身作为自己的根节点 
	} 
	sort(road,road+e,compare);//按边集数组中的权值由小到大排序 
	for(int i=0;i<e;i++){//遍历已经排好序的边 
		a=getRoot(road[i].start);//获取开始顶点在生成树中的父节点
		b=getRoot(road[i].end);//获取终结顶点在生成树中的父节点
		if(a!=b){//当ab不等说明两者不是同一个父节点,不会构成环 
			parent[a]=b;//把b点作为孩子加在a的后面 
			printf("(%d,%d)\n",road[i].start,road[i].end);//打印构成最小生成树的边
			sum+=road[i].w;//最小生成树的权值总和
		}
	}
	printf("sum=%d\n",sum);
	return sum;
}
int main(int argc, char** argv) {
	MGraph G;
	createMGraph(G);
	kruskal(G);
	return 0;
}
/*
	示例输入:
		顶点数和边数: 9 15
		输入顶点:	0 1 2 3 4 5 6 7 8
		输入顶点下标和权值: 
				4 7 7
				2 8 8
				0 1 10
				0 5 11
				1 8 12
				3 7 16
				1 6 16
				5 6 17
				1 2 18
				6 7 19
				3 4 20
				3 8 21
				2 3 22
				3 6 24
				4 5 26
	*/

4. 最短路径经典算法(Dijkstra)

• 最短路径:指两顶点之间经过的边上的权值之和最小的路径,并称路径的第一个顶点为源点,最后一个顶点为终点
• 求最短路径的算法通常都依赖一种性质:两点之间的最短路径也包含了路径上 其他顶点之间的最短路径
• 带权有向图G的最短问题分两类:
  1. 单源最短路径:即某一顶点到其他各顶点的最短路径,可用Dijkstra算法求
  2. 任意一对顶点最短路径:可通过Floyd-Warshall算法求解

Dijkstra算法(迪杰斯特拉算法)代码实现

#include <iostream>
#include<stdlib.h>
#define maxSize 100
#define infinity 65535
using namespace std;
typedef struct{//邻接矩阵构造的图结点 
	char vnode[maxSize];
	int edge[maxSize][maxSize];
	int n,e;
}MGraph; 


void createMGraph(MGraph &G){//创建图 
	int i,j,n,e,k,w;
	cout<< "请输入图的顶点数和边数"<<endl;
	cin>> G.n >> G.e;
	n=G.n;
	e=G.e;
	cout<< "请输入顶点"<<endl;
	for(i=0;i<n;i++){
		cin>> G.vnode[i]; 
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			G.edge[i][j]=infinity;
		}
	}
	cout<< "请输入边的下标和权值:i j w"<<endl;
	for(k=0;k<e;k++){
		scanf("%d %d %d",&i,&j,&w);
		G.edge[i][j]=w;
		G.edge[j][i]=G.edge[i][j];
	} 
}


void shortPath_Dijkstra(MGraph G,int v,int path[],int distance[]){//最短路径(顶点v到各顶点的最小距离) 
	int i,j,k,t,min;
	int final[maxSize];
	for(i=0;i<G.n;i++){
		final[i]=0;//初始化,刚开始生成树里没顶点 
		distance[i]=G.edge[v][i];//开始顶点v与其他顶点的距离(若v与其他顶点没有交集,则距离为infinity) 
		path[i]=0;//能构成最小路径的顶点的下标
	}
	distance[v]=0;//自己与自己的距离为0 
	final[v]=1; //把起始顶点v加入到生成树中
	for(t=1;t<G.n;t++){
		min=infinity;
		for(j=0;j<G.n;j++){
			if(final[j]==0&&distance[j]<min){
				min=distance[j];//找出distance中的最小值(剔除已加入生成树的顶点,不然min就为0了)
				k=j;//distance的下标都是以final[v]为起点构成边的终止顶点,distance值为边的权值 
			}
		} 
		final[k]=1;//把终止顶点k放入生成树
		for(i=0;i<G.n;i++){//min就代表了final[i]=1的那部分顶点到k顶点构成的最小路径的值 
			if(final[i]==0&&(min+G.edge[k][i]<distance[i])){//若有多条分支到某个顶点的距离比直接去更短则更新 
				distance[i]=min+G.edge[k][i];//若开始顶点v与i顶点没交集,而k与i相邻接,则v与i的距离就记作min+k与i的距离
											 //若v与i有交集,且k与i也有交集,若min+k与i的距离比v与i的距离短则更新 
				path[i]=k;//顶点i的前驱顶点为k (与终止顶点i配套的起始顶点为k) 
						  //若找到了v与i更近的路径,则更新与i相邻的顶点即为k 
						  //接下来的循环就是找与k顶点相邻接的终止顶点中构成路径最小的那个,然后放入生成树 
			}
		}
	}
} 
int main(int argc, char** argv) {
	MGraph G;
	int path[maxSize];
	int distance[maxSize];
	createMGraph(G);
	shortPath_Dijkstra(G,0,path,distance);//迪杰斯特拉算法 
	for(int i=0;i<G.n;i++){
		printf("path[%d]=%d,distance[%d]=%d\n",i,path[i],i,distance[i]);
	}
	return 0;
}

/*
    示例输入:
        顶点数和边数: 9 15
        输入顶点:   0 1 2 3 4 5 6 7 8
        输入顶点下标和权值: 
			4 7 7
			2 8 8
			0 1 10
			0 5 11
			1 8 12
			3 7 16
			1 6 16
			5 6 17
			1 2 18
			6 7 19
			3 4 20
			3 8 21
			2 3 22
			3 6 24
			4 5 26
    */

5. 关键路径

• 在一个表示工程的带权有向图中,用顶点表示事件,有向边表示活动,用边上的权值表示活动的持续事件,这种有向图我们称之为AOE网(Activity On Edge Network)

• AOE网中入度为0的顶点称为始点或源点,出度为0的顶点成为终点或汇点

• AOE网是用来表示工程流程的,它带有明显的工程特性,如果在某顶点所代表的事情发生后,从该顶点出发的各活动才能开始,只有在进入某顶点的各活动都已经结束,该顶点所代表的事件才能发生

• 由于工程一般只有一个源点和一个汇点,所以AOE网同样各有一个

• AOE网与AOV网的区别: AOV只描述活动之间的制约关系,而AOE是要建立在活动制约关系没有矛盾的基础上再来分析完成整个工程至少需要多少时间,或怎么缩短工期时间

• 我们把各个活动持续的时间之和成为路径长度,从源点到汇点最大的长度的路径叫做关键路径,在关键路径的活动叫关键活动

• 想要缩短工程工期,则必须提高关键路径上的关键活动的速度,它们才是影响工期的狗贼

• 一个AOV可能具有多条关键路径,唯有提高所有关键路径上的关键活动的速度才能缩短整个工程的工期

所以你明白关键路径的重要性了吧,废话不多说,上求最小关键路径代码(粘贴即可执行)

#include <iostream>
#include<stdlib.h>
#define maxSize 100
using namespace std;

typedef struct EdgeNode{//边结点
	int adjvex;
	int weight;//边的权重
	struct EdgeNode* nextEdge;
}EdgeNode;

typedef struct Vnode{//顶点结点
	int data;
	int in;//顶点入度
	EdgeNode *firstEdge;
}Vnode,AdjList[maxSize];

typedef struct AGraph{//图结点
	AdjList adjList;//顶点数组
	int n,e;//顶点数和边数
}AGraph; 

void createGraph(AGraph &G){//创建图 
	int i,j,k,w;
	EdgeNode *p;
	printf("请输入顶点数和边数\n");
	scanf("%d %d",&G.n,&G.e);
	printf("请输入顶点:\n");
	for(i=0;i<G.n;i++){
		scanf("%d",&G.adjList[i].data);
		G.adjList[i].firstEdge=NULL;
		G.adjList[i].in=0;
	}
	printf("请输入边的顶点下标权值及i j w\n");
	for(k=0;k<G.e;k++){
		scanf("%d %d %d",&i,&j,&w);
		p=(EdgeNode *)malloc(sizeof(EdgeNode));//创建边结点 
		p->adjvex=j;//边结点下标 
		p->weight=w; //边结点权值 
		p->nextEdge=G.adjList[i].firstEdge;//头插法连接边结点 
		G.adjList[i].firstEdge=p;
		G.adjList[j].in++;//边的入度自增长 
	}
}

int *etv;
int *ltv;
int *stack2;//辅助栈2(动态数组) 
int top2;
int topSort(AGraph G){//拓扑排序 
	int i,j,k,w,count=0;
	EdgeNode *p;
	int *stack1;
	stack1=(int *)malloc(G.n*sizeof(int));
	int top1=-1;//初始化栈1 
	top2=-1;
	stack2=(int *)malloc(G.n*sizeof(int));//给辅助栈2动态分配内存空间,并进行初始化 
	etv=(int *)malloc(G.n*sizeof(int));//给顶点最早开始时间数组动态分配内存空间 
	for(i=0;i<G.n;i++){
		if(G.adjList[i].in==0){//若入度为0则进栈1 
			stack1[++top1]=i;
		}
		etv[i]=0;//初始化顶点最早开始时间数组 
	}
	while(top1!=-1){//若栈不为空 
		i=stack1[top1--];//栈顶出栈 
		count++;//顶点计数 
		stack2[++top2]=i;
		for(p=G.adjList[i].firstEdge;p;p=p->nextEdge){//遍历出栈顶点的弧表 
			j=p->adjvex;
			G.adjList[j].in--;//入度自减 
			if(!G.adjList[j].in){//若入度为0,则顶点下标入栈 
				stack1[++top1]=j;
			}
			if(etv[i]+p->weight>etv[j]){ 
				etv[j]=etv[i]+p->weight;//事件j最早开始时间=事件i最早开始时间+len(i,j)的最大值 
			}
		}
	}
	if(count<G.n){//若count比顶点数少,则此拓扑排序是失败的 
		return 0;
	}
	return 1;
}

void criticalPath(AGraph G){//关键路径(最早开始时间=最晚开始时间的活动),即决定工期进度的活动 
	EdgeNode *e;
	int i,j,k,ete,lte;
	topSort(G);//进行拓扑排序,得到相应的stack2 (因为求活动最晚开始时间需要倒序开始) 
	ltv=(int *)malloc(sizeof(int)*G.n);//给事件最晚开始时间数组动态分配内存空间 
	for(i=0;i<G.n;i++){
		ltv[i]=etv[G.n-1];//初始化所有事件的最晚开始时间全为项目完成时间(其实只要保证初始值很大就行) 
	}
	while(top2!=-1){//栈不为空 
		i=stack2[top2--];//顶点序号出栈 
		for(e=G.adjList[i].firstEdge;e;e=e->nextEdge){//遍历出栈顶点的弧表 
			j=e->adjvex;
			if(ltv[j]-e->weight<ltv[i]){//事件i最晚开始时间=事件j最晚开始时间-len(i,j)中的最小值 
				ltv[i]=ltv[j]-e->weight; 
			} 
		}
	}
	for(i=0;i<G.n;i++){//遍历所有顶点及其弧表 
		for(e=G.adjList[i].firstEdge;e;e=e->nextEdge){
			j=e->adjvex;
			ete=etv[i];//ete是指事件i到事件j的最早开始时间,针对的是活动(即弧),而etv[i]针对的是事件i,这里它们值一致 
			lte=ltv[j]-e->weight;//事件i到事件j(活动i->j)最晚开始时间=事件j最晚开始时间-len(i,j); 
			if(ete==lte){//若事件i到j的最早和最晚时间一致则说明它们一刻也不能耽误,它们是决定工程工期的因素 
				printf("<%d->%d> %d,\n",G.adjList[i].data,G.adjList[j].data,e->weight);//关键路径 
			}
		}
	}
}
 
int main(int argc, char** argv) {
	AGraph G;
	createGraph(G);
	criticalPath(G);
	return 0;
}
/*
式例图 
i j weight(i->j 权值) 
0 2 4
0 1 3
1 4 6
1 3 5
2 5 7
2 3 8
3 4 3
4 7 4
4 6 9
5 7 6
6 9 2
7 8 5
8 9 3
*/

6.拓扑排序

• 什么是拓扑排序

对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。

• 背景知识

一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。

• 算法大致思想

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

1. 选择一个入度为0的顶点并输出之；
2. 从网中删除此顶点及所有出边。
3. 循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列

#include <iostream>
#include<stdlib.h>
#define maxSize 100
typedef struct EdgeNode{//边结点 
	int adjvex;
	struct EdgeNode* next;
}EdgeNode; 

typedef struct Vnode{//顶点结点 
	int data;
	int in;//新增的入度个数 
	EdgeNode *firstEdge;	
}Vnode,Adjvex[maxSize];

typedef struct AGraph{//图结点 
	Adjvex adjvex;
	int n,e;
}AGraph;

void createGraph(AGraph &G){//邻接表创建图 
	EdgeNode *p;
	int i,j,k;
	printf("请输入图的顶点数和边数\n");
	scanf("%d %d",&G.n,&G.e); 
	printf("请输入图的顶点\n");
	for(i=0;i<G.n;i++){//输入图的顶点 
		scanf("%d",&G.adjvex[i]);
		G.adjvex[i].firstEdge=NULL;
		G.adjvex[i].in=0;//所有的顶点入度初始化为0 
	}
	
	printf("请输入边的下标i j\n");
	for(k=0;k<G.e;k++){//输入图的边 
		scanf("%d %d",&i,&j);
		p=(EdgeNode *)malloc(sizeof(EdgeNode));
		p->adjvex=j;
		p->next=G.adjvex[i].firstEdge;
		G.adjvex[i].firstEdge=p;
		G.adjvex[j].in++; //j顶点入度自增长 
	}
}

int topSort(AGraph G){//拓扑排序 
	EdgeNode *p;
	int i,j,k,count=0;
	int *que;//栈里面存放的是顶点下标 
	que=(int *)malloc(G.n*sizeof(int));
	int top=-1;//创建并初始化栈 
	for(i=0;i<G.n;i++){
		if(!G.adjvex[i].in){//若入度为0的,则入栈 
			que[++top]=i;
		}
	}
	while(top!=-1){//若栈不为空 
		k=que[top--];//栈顶出栈 
		printf("%d ",G.adjvex[k].data);
		count++;//计数访问了多少顶点 
		for(p=G.adjvex[k].firstEdge;p!=NULL;p=p->next){//遍历出栈顶点的边表 
			G.adjvex[p->adjvex].in--;//与之相邻接的顶点的入度自减 
			if(G.adjvex[p->adjvex].in==0){//把自减后入度为0的顶点入栈 
				que[++top]=p->adjvex;
			}
		} 
	}
	if(count<G.n){//若有顶点未访问到,则拓扑排序失败 
		return 0;
	}else{
		return 1;
	}
}
int main(int argc, char** argv) {
	AGraph G;
	createGraph(G);
	topSort(G);
	return 0;
}