假设我们有一组任务要完成，并且有些任务要在其它任务完成之后才能开始，所以我们必须非常小心这些任务的执行顺序。
如果这些任务的执行顺序足够简单的话，我们可以用链表来存储它们，这是一个很好的方案，让我们可以准确知道任务的执行顺序。问题是有时候不同任务之间的关系是非常复杂的，有些任务依赖于两个甚至更多的任务，或者反过来很多任务依赖自己。
因此我们不能通过链表或者树的数据结构来对这个问题建模。对这类问题唯一合理的数据结构就是图。我们需要哪种图呢？很显然，我们需要有向图来描述这种关系，而且是不能循环的有向图，我们称之为有向无环图。要通过拓扑排序对图形进行排序，这些图必须是不能循环和有向的。为什么这些图不能循环呢？答案很明显，如果图形是循环的，我们无法知道哪个任务该优先执行，也不可能对任务进行排序。现在我们一要做的是对图中的每个节点排序，组成一条条边（u，v），u在v之前执行。然后我们就可以得到所有任务的线性顺序，并按这种顺序执行任务就一切都OK了。
例如,下面的图的一个拓扑排序是“5 4 2 3 1 0”。一个图可以有多个拓扑排序。
另一个拓扑排序是“4 5 2 3 1 0”。拓扑排序的第一个顶点总是入度为0。
-------------------------------------------------------------------------------------------------------------------------------------------
1.思想先找一个入度为零的访问
接着把它和它的路线删除.....................
但我们并没有真正把它删除，把访问过的入队即可并标记， 随后把与它相邻的元素入度减一即可！！！！
------------------------------
//topologicalsort 排序的实现 容器队列
#include <cstdio>
#include <cstdlib>
//#define _OJ_
#define maxsize 100
int visit[100]; //用来标记已被访问的元素
typedef struct Queue1
{
int top;
int base;
int *elem; //定义队列尊循先进先出的原则
} Queue1, *Queue;
typedef struct Graph1
{
int nv;
int ne;
int G[100][100];
} Graph1, *Graph;
Queue
creat_Queue(void)
{
Queue q;
q = (Queue) malloc (sizeof(Queue1));
q->elem = (int*) malloc (sizeof(int) * maxsize);
q->top = q->base = 0;
return q;
}
int
isempty(Queue q)
{
if(q->top == q->base)
return 1;
else
return 0;
}
void
Enqueue(Queue q, int data)
{
q->elem[q->top++] = data;
}
int
Dequeue(Queue q)
{
return q->elem[q->base++];
}
Graph
creat_Graph(void)
{
int v1, v2, i, j;
Graph g;
g = (Graph) malloc (sizeof(Graph1));
scanf("%d %d", &(g->nv), &(g->ne));
for(i = 1;i <= g->nv; i++) {
for(j = 1;j <= g->nv; j++) {
g->G[i][j] = 0;
}
}
for(i = 1;i <= g->ne; i++) {
scanf("%d %d", &v1, &v2);
g->G[v1][v2] = 1;
}
return g;
}
int
Topologicalsort(Graph g)
{
Queue q;
int i, j, i1, cnt = 0;
int indegree[100];
q = creat_Queue();
for(i = 1;i <= g->nv ; i++) {
indegree[i] = 0; //用一个临时数组来记录入度即每一列非零元素
for(j = 1;j <= g->nv; j++) {
if(g->G[j][i] != 0) ++indegree[i];
}
if(indegree[i] == 0) {Enqueue(q, i); visit[i] = 1;}
} //度为零那么入队并标记
while (isempty(q) != 1) {
i1 = Dequeue(q); printf("i1 == %d
", i1); cnt++;//cnt用于记录走过的元素
for(i = 1;i <= g->nv; i++) { //把与出队相邻的元素入度减一
if(g->G[i1][i] != 0) indegree[i]--;
if(indegree[i] == 0 && visit[i] == 0) {Enqueue(q, i); visit[i] = 1;}
}
}
if(cnt < g->nv) printf("error
"); //若从cnt< g->nv者出错表示图中有回路
}
// void
// print(void)
// {
// int i, j, t;
// for(i = 1;i < n - 1; i++) {
// printf("%d ", visit1[i]);
// }
// printf("%d
", visit1[n - 1]);
// }
int main(int argc, char const *argv[]) {
#ifndef _OJ_ //ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int i, j;
Graph g;
g = creat_Graph();
for(i = 1; i <= g->nv; i++)
visit[i] = 0;
Topologicalsort(g);
return 0;
}
输入：
6 7
1 2
2 3
1 5
2 4
3 6
5 4
4 6
输出：
i1 == 1
i1 == 2
i1 == 5
i1 == 3
i1 == 4
i1 == 6
-----------------------------------------------------------------------------------------------------------------------队列实现
---------------------------------------------------------------------------------------------------------------------------------------
//top 排序的实现 容器栈(正确)
#include <cstdio>
#include <cstdlib>
//#define _OJ_
#define maxszie 100
int visit[100];
typedef struct stack1
{
int top;
int base;
int *elem;
} stack1, *stack;
typedef struct Graph1
{
int nv;
int ne;
int G[100][100];
} Graph1, *Graph;
stack
creat_stack(void)
{
stack s;
s = (stack) malloc (sizeof(stack1));
s->elem = (int*) malloc (sizeof(int) * maxszie);
s->top = s->base = 0;
return s;
}
int
isempty(stack s)
{
if(s->top == s->base)
return 1;
else
return 0;
}
void
push(stack s, int data)
{
s->elem[s->top++] = data;
}
int
pop(stack s)
{
return s->elem[--s->top];
}
Graph
creat_Graph(void)
{
int v1, v2, i, j;
Graph g;
g = (Graph) malloc (sizeof(Graph1));
scanf("%d %d", &(g->nv), &(g->ne));
for(i = 1;i <= g->nv; i++) {
for(j = 1;j <= g->nv; j++) {
g->G[i][j] = 0;
}
}
for(i = 1;i <= g->ne; i++) {
scanf("%d %d", &v1, &v2);
g->G[v2][v1] = 1;
}
return g;
}
void
Topologicalsort(Graph g)
{
stack s;
int i, j, i1, cnt = 0;
int indegree[100];
s = creat_stack();
for(i = 1;i <= g->nv ; i++) {
indegree[i] = 0;
for(j = 1;j <= g->nv; j++) {
if(g->G[j][i] != 0) ++indegree[i];
}
if(indegree[i] == 0) {push(s, i); visit[i] = 1;}
}
while (isempty(s) != 1) {
i1 = pop(s); printf("i1 == %d ", i1); cnt++;
for(i = 1;i <= g->nv; i++) {
if(g->G[i1][i] != 0) indegree[i]--;
if(indegree[i] == 0 && visit[i] == 0) {push(s, i); visit[i] = 1;}//printf("i2=%d
", i);}
}
}
if(cnt < g->nv) printf("error
");
else printf("ok
");
}
int main(int argc, char const *argv[]) {
#ifndef _OJ_ //ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int i;
Graph g;
g = creat_Graph();
for(i = 1; i <= g->nv; i++)
visit[i] = 0;
Topologicalsort(g);
return 0;
}
-----------------------------------------------------------------------------------------------------------------------------
输入：
6 7
1 2
2 3
1 5
2 4
3 6
5 4
4 6
输出：
i1 == 6 i1 == 4 i1 == 5 i1 == 3 i1 == 2 i1 == 1 ok
-----------------------------------------------------------------------------------------------------------------------栈的实现
栈的实现和队列的实现其实是一样的，，不过一个是先进先出，，一个先进后出，，so答案有所出入，，不过原理都一样！！！