若对有向图进行拓扑排序,则能够得到拓扑序列的条件是()。
//拓扑排序 //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; }