图--有向无环图的拓扑排序

有向无环图(directed acycline graph),DAG:一个无环的有向图。
有向无环图是描述含义公共子式的表达式的有效工具。
有向无环图是描述一项工程或系统的进行过程的有效工具。–关键路径和拓扑排序

###拓扑排序
拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序。
若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。
若R是集合X上的偏序，如果对于每个x,y属于X必有xRy或yRx，则称R是集合X上的全序关系。

一个表示偏序的有向图可用来表示一个流程图。

用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的图(Activity On Vertex Network),简称AOV-网。
在AOV网中，不应该出现有向环，
对给定的AOV网应该首先判读网中是否存在环–>方向:对有向图构造其顶点的拓扑有序序列，若网中所有的顶点都在它的拓扑有序序列中，则该AOV网中必定不存在环。

算法描述：
1）在有向图中选一个没有前驱的顶点且输出之。
2）从图中删除该顶点和所有以它为尾的弧。
重复上述步骤，直到全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。

实现：
在头结点中增加一个存放顶点入度的数组(indegree)。
入度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，可换以弧头顶点的入读减1来实现。

算法实现：

#include <stdio.h>
#include <stdlib.h>
/*栈 在拓扑排序的时候用到了*/
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct SqStack
{
	int *base;
	int *top;
	int stacksize;
}SqStack;

void InitStack(SqStack &S);
void Push(SqStack &S, int e);
void Pop(SqStack &S, int &e);
int StackEmpty(SqStack S);


//图的邻接表存储表示
#define MAX_VERTEX_NUM 20
#define INF INT_MAX
typedef int InfoType;
typedef int VertexType;
typedef struct ArcNode{
	int adjvex; //邻接点序号
	int value; //表示边的权值
	struct ArcNode* nexttarc; //下一条边的顶点
	InfoType *info;
};
typedef struct VNode{
	VertexType data;    //顶点信息 
	ArcNode *firsttarc;  //指向第一条边节点
}VNode, AdjList[MAX_VERTEX_NUM];  //单链表的头结点类型

typedef struct{
	AdjList Vertices;   //单链表头结点数组
	int vexnum, arcnum;  //实际的顶点数vexnum 边数arcnum
}ALGraph;

int visited[MAX_VERTEX_NUM];
int finished[MAX_VERTEX_NUM];
int count;
#define LENGTH 6
#define ARCLENGTH 8

typedef struct Minimum{
	VertexType adjvex;
	int lowcost;
	int flag;
}Minimum, closedge[MAX_VERTEX_NUM];

//int graph[6][6] = {
//	INF, 5, INF, 7, INF, INF,
//	INF, INF, 4, INF, INF, INF,
//	8, INF, INF, INF, INF, 9,
//	INF, INF, 5, INF, INF, 6,
//	INF, INF, INF, 5, INF, INF,
//	3, INF, INF, INF, 1, INF
//};

//int graph[LENGTH][LENGTH] = {
//	INF, 6, 1, 5, INF, INF,
//	6, INF, 5, INF, 3, 0,
//	1, 5, INF, 5, 6, 4,
//	5, INF, 5, INF, INF, 2,
//	INF, 3, 6, INF, INF, 6,
//	INF, INF, 4, 2, 6, INF
//};

int graph[LENGTH][LENGTH] = {
	INF, 1, 1, 1, INF, INF,
	INF, INF, INF, INF, INF, INF,
	INF, 1, INF, INF, 1, INF,
	INF, INF, INF, INF, 1, INF,
	INF, INF, INF, INF, INF, INF,
	INF, INF, INF, 1, 1, INF
};

int indegree[MAX_VERTEX_NUM];

//确定节点u在图中的编号
int LocateVex(ALGraph G, VertexType u){
	int i;
	for (i = 0; i < G.vexnum; i++){
		if (G.Vertices[i].data == u)
			return i;
	}
	return -1;
}
int FirstAdjVex(ALGraph G, VertexType u){
	return LocateVex(G, G.Vertices[u].firsttarc->adjvex);
}
int NextAdjVex(ALGraph G, VertexType v, VertexType w){
	return 1;
}

void FindInDegree(ALGraph G){
	for (int i = 0; i < G.vexnum; i++){
		indegree[i] = 0;
	}	
	int k;
	for (int i = 0; i < G.vexnum; ++i){
		ArcNode *p = G.Vertices[i].firsttarc;
		while (p){
			k = LocateVex(G, p->adjvex);
			indegree[k] ++;
			p = p->nexttarc;
		}
	}

}

int TopologicalSort(ALGraph G){
	
	ArcNode * p;
	FindInDegree(G);
	
	SqStack S;
	InitStack(S);
	int i;
	for ( i = 0; i < G.vexnum; ++i){
		if (!indegree[i])
			Push(S, i);
	}
	int count = 0;
	while (!StackEmpty(S)){
		int k;
		Pop(S, i);
		printf("%d %d\n", i, G.Vertices[i].data);
		++count;
		p = G.Vertices[i].firsttarc;
		while (p){
			k = LocateVex(G, p->adjvex);
			if (!(--indegree[k]))
				Push(S, k);
			p = p->nexttarc;
		}
	}
	if (count < G.vexnum)
		return -1;
	else
		return 0;

}


/*深度优先搜索遍历DFS*/
void DFS(ALGraph G, int v){
	visited[v] = true;
	printf("v%d-->", G.Vertices[v].data);
	ArcNode *p = G.Vertices[v].firsttarc;
	while (p != NULL){
		int k = LocateVex(G, p->adjvex);
		if (!visited[k]){
			DFS(G, k);
		}
		p = p->nexttarc;
	}

}
void DFSTraverse(ALGraph G){
	for (int v = 0; v < G.vexnum; ++v){
		visited[v] = false;
	}
	for (int v = 0; v < G.vexnum; ++v){
		if (!visited[v]){
			DFS(G, v);
		}
	}
}

void CreateGraph(ALGraph &G){
	G.vexnum = LENGTH;
	G.arcnum = ARCLENGTH;
	//初始化顶点的信息
	for (int i = 0; i < G.vexnum; i++){
		G.Vertices[i].data = i + 1;
		G.Vertices[i].firsttarc = NULL;
	}
	for (int i = 0; i < LENGTH; i++){
		for (int j = LENGTH - 1; j >= 0; j--){
			if (graph[i][j] != INF){
				ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
				p->adjvex = j + 1;
				p->value = graph[i][j];
				p->nexttarc = G.Vertices[i].firsttarc;
				G.Vertices[i].firsttarc = p;
			}
		}
	}
}
void DisplayerGraph(ALGraph &G){
	int i = 0;
	ArcNode *p;
	for (i = 0; i < G.vexnum; i++){
		printf("顶点[V%d]的邻接边 ", G.Vertices[i].data);
		p = G.Vertices[i].firsttarc;
		while (p){
			printf("-->(%d,%d)", p->adjvex, p->value);
			p = p->nexttarc;
		}
		printf("-->(^)\n");
	}
}

int main(){
	ALGraph  *G;
	G = (ALGraph*)malloc(sizeof(ALGraph));
	CreateGraph(*G);
	DisplayerGraph(*G);
	printf("深度优先搜索：\n");
	DFSTraverse(*G);
	printf("^\n拓扑排序的结果\n");
	TopologicalSort(*G);
	
	return 1;
}



void InitStack(SqStack &S){

	S.base = (int *)malloc(STACK_INIT_SIZE*sizeof(int));
	if (!S.base)
		exit(-1);
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
}

void Push(SqStack &S, int e){

	if ((S.top - S.base) >= S.stacksize)
	{
		S.base = (int *)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(int));
		if (S.base)
			exit(-1);
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
}

void Pop(SqStack &S, int &e){

	if (S.base == S.top)
		return;
	e = *--S.top;
}

int StackEmpty(SqStack S){

	if (S.top == S.base)
		return 1;
	else
		return 0;
}