单选题 对下图进行拓补排序,可以得到不同的拓补序列的个数是( )
【正确答案】 B
【答案解析】[解析] 根据拓扑排序的规则可知,a节点没有前驱节点,则将a节点先输出,见下图:
[*]
a节点先输出后,拓扑序列变化见下图:
[*]
e,b节点没有前驱节点,则可以将e,b节点先输出;此时需要讨论以下两种情况:
如果先输出e,情况如下图:
[*]
接下来,只有b节点没有前驱节点,将b输出。
在这种情况下,拓扑序列为:aebcd;
如果先输出b,情况如下图:
[*]
e,c节点没有前驱节点,则可以将e,c节点先输出;
此时可以产生两种不同的排序序列情况:abced abecd。