【算法导论】邻接矩阵存储的拓扑排序

​ 在很多应用中，很多事情都是按照一定的次序来进行的，比如说起床穿衣时，不可能先穿鞋再穿袜子，但是穿袜子和穿裤子可以不分先后次序。这种按照一定顺序进行的活动，可以使用顶点表示活动，顶点之间的有向边表示活动间的先后关系，这种有向无回路图说明了活动的先后次序。

​ 当活动只能单个进行时，如果可以将图中的所有顶点排列成一个线性序列$v{i1}, v{i2}, \cdots, v_{in}$，并且这个序列同时满足关系：若从顶点$v_i$到顶点$v_j$存在一条路径，则在线性序列中$v_i$必在$v_j$之前，我们就称这个线性序列为拓扑序列。把对有向无回路图构造拓扑序列的操作称为拓扑排序。

其基本思想：

​ 拓扑排序的基本操作为：

• 从图中选择一个入度为0的顶点并且输出它；
• 从图中删除此顶点及所有由它发出的边；
• 重复上述过程，直到图中没有入度为0的边。

以上的操作会产生两种结果：一种是图中的全部顶点都被输出，整个拓扑排序完成；另一种是图中顶点未被全部输出，剩余的顶点的入度均不为0，则说明网中存在有向环。

上述表述比较抽象，下面我用图解的方式来介绍其思想：

假设有向无回路图如下所示：

因此得到的拓扑排序序列为： A B D C E F G.

具体的程序实现如下：

#include<stdio.h>
#include<stdlib.h>
#define N 7//顶点个数

typedef struct 
{
	char vexs[N];//顶点数组
	int arcs[N][N];//邻接矩阵
}graph;

void TopoSort_matrix(graph g)
{
	int row[N]={0};//按照列来设置标志，为1表示已经输出（不再考虑），为0表示未输出。
	int v=1;//标志符，1表示已经输出（不再考虑），为0表示未输出，赋给row数组
	int i,j,k,t,m;
	for(k=0;k<N;k++)
	{
		for(j=0;j<N;j++)
		{
			if(row[j]==0)//活动j还未输出
			{
				t=1;//标识符
				for(i=0;i<N;i++)
					if(g.arcs[i][j]==1)//当前活动有入度（活动i必须在活动j之前）
					{
						t=0;
						break;
					}
				if(t==1)//活动j没有入度
				{
					m=j;
					break;
				}
			}
		}
		if(j!=N)
		{
			row[m]=v;
			printf("%c",g.vexs[m]);
			for(i=0;i<N;i++)
				g.arcs[m][i]=0;//将已经输出的活动所到达的下个活动的入度置为0
			v++;
		}
		else 
			break;
		}
		if(v-1<N)//当row中不是所有的元素都被赋予新值v时，说明有环存在
			printf("\n该有向图有环存在！");
	
}

void main()
{
	graph g;
	int matrix[N][N]={{0,1,1,0,0,0,0},
					  {0,0,0,0,0,1,1},
			    	  {0,0,0,0,0,0,1},
					  {0,0,1,0,1,0,0},
					  {0,0,0,0,0,0,1},
					  {0,0,0,0,0,0,0},
					  {0,0,0,0,0,0,0}};
	char vertex[N]={'A','B','C','D','E','F','G'};//初始化
		for(int i=0;i<N;i++)
		{
			g.vexs[i]=vertex[i];
			for(int j=0;j<N;j++)
				g.arcs[i][j]=matrix[i][j];
		}
	TopoSort_matrix(g);
	printf("\n");
}