对一个图的拓扑排序,请指教
今天做数据结构的一个题目。关于拓扑排序的,我和同学做出了三种答案,但是标准答案只有一个请大家,照成的原因可能和效率有关,但我不是很懂,请各位解释解释:
下面是题目:
/***************************************************************************************************************/
已知一个图的顶点集V和边集E分别为:
V={1,2,3,4,5,6,7};
E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};
若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的,试给出得到的拓扑排序的序列。
/***************************************************************************************************************/
我们得出的答案是“4 3 6 2 5 7 1” 、“4 3 6 5 2 1 7” 、“4 3 6 5 7 2 1”。
但是标准答案是“4 3 6 5 7 2 1” 因为按照拓扑排序的基本算法,这三个答案都是对的,我不懂了,请大家看看
[解决办法]
简单的说,拓扑排序就是你做某项工作时要完成多个任务,但任务之间又互有影响,比如:只有完成A任务时才能做B任务,那么我们要做B任务之前要保证A任务已经完成。完成任务的先后顺序就是一个拓扑序列。一个图的拓扑排序会有多种,他们是一样的,并没有区别。
[解决办法]
图的拓扑排序结果不唯一的。跟程序有关。