首页 > 试题广场 >

若对有向图进行拓扑排序,则能够得到拓扑序列的条件是()。

[问答题]

若对有向图进行拓扑排序,则能够得到拓扑序列的条件是()。

有向无环图

//拓扑排序  
//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;
}


发表于 2019-10-06 21:40:07 回复(0)