若对有向图进行拓扑排序,则能够得到拓扑序列的条件是()。
//拓扑排序
//AOV网以顶点表示活动,以边表示活动顺序,没有回路的有向图
/*
伪
1 选择一个入度为0的顶点
2 输出该顶点并入栈
3 当栈不为空
3.1 出栈一个顶点
3.2 访问该顶点所连接的所有顶点
3.2.1 将该顶点所指向的顶点的入度-1
3.2.2 若指向的顶点的入度为0,将该顶点入栈
*/
int TopSort(AGraph G)
{
int i, j;
int n = 0;//统计顶点个数
int stack[maxSize];
int top = -1;
ArcNode *p;
//1 将入度为0的顶点入栈
for(i = 0; i < G.n; ++i)
{
if(G.adjList[i].count == 0)
stack[++top] = i;
}
while(top != -1)
{
i = stack[top--];
++n;
printf("%d ", i);
//2.1将顶点i所指向的顶点的入度个数减一 ,如果count为0则入栈
p = G.adjList->firstArc;
while(p != NULL)
{
j = p->adjVertex;
--(G.adjList[j].count);
if(G.adjList[j].count == 0)
stack[++top] = j;
p = p->next;
}
}
if(n == G.n)
return 1;
else
return 0;
}