问答题

阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
  【说明】
  对有向图进行拓扑排序的方法是:
  (1)初始时拓扑序列为空;
  (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧;
  (3)重复(2),直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序,否则由于有向图中存在回路无法完成拓扑排序)。
   函数int*TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序,返回拓扑序列中的顶点编号序列,若不能完成拓扑排序,则返回空指针。其中,图G中的顶点从1开始依次编号, 顶点序列为v1,v2,…,vn,图G采用邻接表表示,其数据类型定义如下:
  
  例如,某有向图G如图4-1所示,其邻接表如图4-2所示。
  
  函数TopSort中用到了队列结构(Queue的定义省略),实现队列基本操作的函数原型如下表所示:
  
  【C代码】
  
  

【问题2】(2分) 对于图4-1所示的有向图G,写出函数TopSort执行后得到的拓扑序列。若将函数TopSort中的队列改为栈,写出函数TopSort执行后得到的拓扑序列。

【参考答案】

队列方式:v1 v2 v5 v4 v3 v7 v6 或者 1 2 5 4 3 7 6 栈方式:v1 v2 v5 v4 v......

(↓↓↓ 点击下方‘点击查看答案’看完整答案 ↓↓↓)