如何编制图中简单回路的演示算法

2022-09-11

1 基本目标

为了使学生对图的深度优先遍历有一个深刻认识, 特编制了求解简单回路的演示算法, 简单回路问题是图的深度优先遍历的一个具体应用, 本演示算法操作简单, 系统启动后屏幕上给出提示信息, 学生可以选择回路所经过的顶点, 为学生们提供了一个模拟环境, 并可将其应用到导游咨询系统中, 是一个教师用的教学软件, 考虑到在邻结表结构中便于查找一个顶点的相邻顶点, 故采用邻接表作了存储结构。下图1为结点图, 图2为其邻接表结构。

2 存储表示

3 算法基本思想及主要算法

3.1 算法基本思想

深度优先遍历是从图G中某个顶点V0出发, 访问V0, 然后选择一个与相邻且没被访问过的顶点Vi访问, 再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问, 依次继续。如果当前被访问过的所有邻接顶点都已被访问过, 则回退到已被访问的顶点序列中最后一个拥有未被访问的邻接顶点W, 从W出发按同样方法向前遍历, 直到图中所有顶点都被访问过。图1的深度优先遍历顺序是V0V1V3V7V4V5V2V6。为了求简单回路, 我们从给定顶点V0出发进行深度优先遍历, 在遍历过程中判别当前访问的顶点是否是V0, 若是V0并且路径的长度大于2, 则找到一条回路, 否则继续遍历。为此, 需设立两个棧, 占S存放被访问过结点的未被访问过的邻接点, 以便回朔查找该结点, 棧C Y C L E记录构成回路的顶点序列, 同时把深度优先遍历中访问顶点的操作改为将当前访问的顶点入C Y C L E棧, 相应地, 若从某一顶点搜索完再回朔, 则做退棧操作。另外, 还设置一个变量found, 起初值只为false, 当找到回路后为true, 变量i为当前路径的长度, 初始值为1。