拓扑排序
在有向图中，有一种特殊的图，叫作有向无环图，也就是从图中的任意一个节点出发，都不可能回到出发点。有向无环图这种模型也有一定的适用场景，比如说在工程领域，可以把工程的每个小过程建模成图中的节点，由于工程进行时是有方向的，因此要用有向图，工程的进行不能有死循环，否则工程可能会陷入这个死循环中永远也完不成。判断一个工程是否完成可以通过判断工程的如有向图是否是有向无环图来判断，如何来判断一个有向图是否是有向无环图呢？而工程中有最短完成时间，可以通过求关键路径来求出这个最短时间。
抽象来看，根据有向无环图的特性，可以把有向图中是否有有向环的问题转换成是否可以生成拓扑序列的问题。拓扑序列是指对于图中的任意相连的两个节点<u,v>，由u指向v，那么在图的所有节点构造成的节点链中，u排列在v的前面。如果有向图中存在有向环a->b->c->a，那么{(1)a应该排在b的前面}，{(2)a应该排在c的后面}，{(3)b应该排在c的前面}，由条件(2)和条件(3)可知a应该排在b的后面，这和条件(1)矛盾，因此有向图中如果存在有向环，那么不可能生成一个拓扑序列。这是证明存在有向环的有向图不可能生成拓扑序列，那么如何用算法来证明呢？
在有向图中，如果一个节点不被其他节点所指，也就是这个节点的入度为0，那么这个节点一定不可能是有向环的一个节点，因此把这个节点从有向图中删去不会对图是否存在有向环产生影响。也就是说如果一个有向图中存在有向环，那么删去入度为0的节点不会破坏图中的有向环。那么就删除图中的所有入度为0的节点及其直接相连的边，这时候图中又会暴露出一些入度为0的节点，同样，这些入度为0的节点也不可能是有向环中的节点。这样一直删下去，最后就会剩下一个有向环构造的有向图，因为有向环中每个节点都指向另外一个节点，而且都一定被另外一个节点指向，所以有向环中的节点的入度都不能0，也就是说不能从有向环中删除节点。最后比较一下删除的节点数和原图的节点数，如果删除的节点数小于原图的节点数，则说明肯定还有节点不能被删除，也就是说最后还剩下了有向环，反之如果删除的节点数等于原图的节点数，就说明原图中不存在有向环，原图就是一个有向无环图。
根据如上的思想，可以设计如下的算法：把图中入度为0的节点添加到一个队列中，然后每次从队列中出队一个节点，从图中删除这个节点，这个删除的过程也就相当于把它的邻接节点的入度减1，如果发现它的哪个邻接节点的入度减1后变成了0，也就是这个邻接节点因为删除了当前节点而变成了一个入度为0的节点，那么也把这个节点添加到队列中。每删除一个节点，就让删除计数变量加1。如此循环下去，直到队列为空为止。最后再比较删除计算变量的值和原图的节点数。想了一下，其实这里不一定要用队列，也可以用栈，用队列的效果相当于从图的四周开始向图的有向环方向删节点，而如果用用栈的话，就相当于多次从不同起始点向中间删节点，一但删到不删处，就从另一个地方重新开始。
下面是用C++来实现拓扑排序
#include "stdafx.h"
#include <iostream>
using namespace std;
/**
* 求相当节点的第一个邻接节点
*/
int FirstAdjVex(bool **matrix,int size, int cv)
{
if(cv < 0 || cv >= size)
{
return -1;
}
for (int i = 0;i < size;i++)
{
if(matrix[cv][i])
{
return i;
}
}
return -1;
}
/**
* 求cv相对于av的下一个邻接节点
*/
int NextAdjVex(bool **matrix,int size,int cv,int av)
{
if(cv < 0 || cv >= size || av < 0 || av >= size -1)
{
return -1;
}
for (int i = av + 1;i < size;i++)
{
if(matrix[cv][i])
{
return i;
}
}
return -1;
}
/**
* 计算各个节点的入度
*/
void CaculateInDegree(bool **matrix,int size,int *inDegrees)
{
for (int i = 0;i < size;i++)
{
inDegrees[i] = 0;
}
for (int i = 0;i < size;i++)
{
for (int v = FirstAdjVex(matrix, size, i);v != -1;v= NextAdjVex(matrix,size,i,v))//把当前节点的所有邻接节点的入度+1
{
inDegrees[v]++;
}
}
}
/**
* matrix为邻接矩阵，size为节点数
*/
bool TopSort(bool **matrix, int size)
{
int *inDegrees = new int[size];
CaculateInDegree(matrix, size, inDegrees);
//简单的队列
int *queue = new int[size];
int front = 0, rear = 0;
for (int i = 0;i < size;i++)//将原图中入度为0的节点入队
{
if(inDegrees[i] == 0)
{
queue[rear++] = i;//入队
}
}
int count = 0;//删除计数器
int node;
while (front != rear) //队列不为空时
{
node = queue[front++];//出队
cout << node << ",";
count++;
//遍历当前节点的所有邻接节点，将邻接节点的入度减1
//相当于删除当前节点操作
for (int v = FirstAdjVex(matrix, size, node);v != -1;v = NextAdjVex(matrix,size,node,v))
{
if(--inDegrees[v] == 0)//邻接节点的入度减1后，邻接节点的入度变为0，则这个邻接节点也入队
{
queue[rear++] = v;
}
}
}
delete queue;//归还队列的内存
return count == size;//是否是有向无环图就是[较删除计数器和原图节点个数]
}
int main()
{
//构造有向图
int size = 5;
bool **matrix = new bool*[size];
for (int i = 0;i < size;i++)
{
matrix[i] = new bool[size];
//初始化为false
for (int j = 0;j < size;j++)
{
matrix[i][j] = false;
}
}
matrix[0][1] = true;
matrix[0][4] = true;
matrix[1][2] = true;
matrix[1][4] = true;
matrix[3][2] = true;
matrix[4][2] = true;
matrix[4][3] = true;
bool is = TopSort(matrix, size);
cout << endl;
cout << "can top sort? "<<is << endl;
system("pause");
return 0;
}
输入的有向图是一个有向无环图，运行程序执行结果如下
再试一个有环图
int main()
{
//构造有向图
//int size = 5;
//bool **matrix = new bool*[size];
//for (int i = 0;i < size;i++)
//{
// matrix[i] = new bool[size];
// //初始化为false
// for (int j = 0;j < size;j++)
// {
// matrix[i][j] = false;
// }
//}
//matrix[0][1] = true;
//matrix[0][4] = true;
//matrix[1][2] = true;
//matrix[1][4] = true;
//matrix[3][2] = true;
//matrix[4][2] = true;
//matrix[4][3] = true;
int size = 6;
bool **matrix = new bool*[size];
for (int i = 0;i < size;i++)
{
matrix[i] = new bool[size];
//初始化为false
for (int j = 0;j < size;j++)
{
matrix[i][j] = false;
}
}
matrix[0][1] = true;
matrix[0][2] = true;
matrix[2][3] = true;
matrix[3][4] = true;
matrix[4][5] = true;
matrix[5][2] = true;
bool is = TopSort(matrix, size);
cout << endl;
cout << "can top sort? "<<is << endl;
system("pause");
return 0;
}
输入的有向图改变之后，执行结果如下
