§6.6.2拓扑排序算法与实现 (一)基本方法 ·进行拓扑排序的基本方法是简单而直观的,其包含下列几个步骤: [1]从有向图中找一个没有前趋的结点v,若v不存在,则表明不可进 行拓扑排序(图中有环路),结束(不完全成功); [2]将v输出; [3]将v从图中删除,同时删除关联于v的所有的边 「4]若图中全部结点均已输出,则结束(成功),否则转[]继续进行
6 §6.6.2 拓扑排序算法与实现 (一）基本方法 • 进行拓扑排序的基本方法是简单而直观的，其包含下列几个步骤： [1] 从有向图中找一个没有前趋的结点v，若v不存在，则表明不可进 行拓扑排序（图中有环路），结束（不完全成功）； [2] 将v输出； [3] 将v从图中删除，同时删除关联于v的所有的边 [4] 若图中全部结点均已输出，则结束（成功），否则转[1]继续进行
§6.6.2拓扑排序算法与实现 (一)基本方法 通过对此方法做适当扩充,就可在求拓扑序列的过程中 标识出可并行活动(结点) 具体做法是,初始时将所有无前趋结点标为一组可并行 结点。然后,每次执行步骤[3]后,将新产生的无前趋结点 标为新的一组可并行结点。为了将同组并行结点连续排列, 在步骤[中应优先选取并行组号与上次选择结点的并行组 号相同的结点(若有的话)
7 §6.6.2 拓扑排序算法与实现 (一）基本方法 • 通过对此方法做适当扩充，就可在求拓扑序列的过程中 标识出可并行活动（结点）。 • 具体做法是，初始时将所有无前趋结点标为一组可并行 结点。然后，每次执行步骤[3]后，将新产生的无前趋结点 标为新的一组可并行结点。为了将同组并行结点连续排列， 在步骤[1]中应优先选取并行组号与上次选择结点的并行组 号相同的结点（若有的话）
§6.6.2拓扑排序算法与实现 (二)数据结构的选取 邻接表的图结点的定义修改为: template <class TElem> struct TGrphNode long noded;∥结点编号 TElem nodelnfo;∥结点信息 long in Degree;∥结点的入度 TGrphedge* firstOutEdge;第一条出边的指针
8 §6.6.2 拓扑排序算法与实现 (二）数据结构的选取 • 邻接表的图结点的定义修改为： template <class TElem> struct TGrphNode { long nodeIdx; //结点编号 TElem nodeInfo; //结点信息 long inDegree; //结点的入度 TGrphEdge * firstOutEdge; //第一条出边的指针 };
§6.6.2拓扑排序算法与实现 (二)数据结构的选取 而图边的定义仍为: template <class TEdgeInfo> struct TGrphEdge long edgeEndldx;∥边终点编号 TEdgelnfo edgeInfo;,边信息 TGrphedge*next;/链指针
9 §6.6.2 拓扑排序算法与实现 (二）数据结构的选取 • 而图边的定义仍为： template <class TEdgeInfo> struct TGrphEdge { long edgeEndIdx; //边终点编号 TEdgeInfo edgeInfo; //边信息 TGrphEdge *next; //链指针 };
§6.6.2拓扑排序算法与实现 (二)算法实现 for(每个结点V if(入度为0)V进栈; while(栈不空) 从栈中弹出一个元素送v 输出v 求出v的第1个直接可达邻接点w; while(w存在) 将w的入度域减1 if(w的入度域为0)w进栈; 求出ⅴ的下个直接可达邻接点w; 3 //while //while
10 §6.6.2 拓扑排序算法与实现 (二）算法实现 for (每个结点v) if (v入度为0) v进栈; while (栈不空) { 从栈中弹出一个元素送v; 输出v; 求出v的第1个直接可达邻接点w; while (w存在) { 将w的入度域减1; if (w的入度域为0) w进栈; 求出v的下个直接可达邻接点w; } //while } //while