">

">


求图a所示有向图顶点的拓扑序列,图b是它的邻接表,在表头结点中增加一个数据域in表示相应顶点的入度。




【正确答案】:

拓扑序列为C0,C3,C1,C2,C4。


【题目解析】:

首先C0、C3的入度都为0,选C0,删除C0及其边e1、e2,调整C1的入度为0, C2的入度为1,此时C1、C3的入度为0,选C3,删除C3及边e3,调整C2的入度为 0,从C1、C2中选C1,删除C1及边e4,调整C4的入度为1,选择C2,删除C2及边e5,调整C4的入度为0,输出C4,至此拓扑排序完成,拓扑序列为C0, C3, C1,C2, C4。 


Top