有向图中基于函数调用的路径搜索方法
摘 要
路径搜索问题是一个重要的问题，在很多领域都能找到它的应用。本文在一个有向图环境中实现路径搜索，在给定限定路径长度的条件下，从源顶点求解所有符合条件的通往目标顶点的路径集合，并很容易地找出最短路径。采用函数递归调用的方法进行求解，在求解过程中舍弃不符合条件的路径，保留符合条件的路径。在不同的限定路径长度下，用本方法给出了生成的相应路径数目。通过实验证明，该方法能实现准确的路径搜索并快速给出搜索结果。
【关键词】路径搜索 有向图 函数调用 递归算法
路径搜索问题在科学研究领域和工程应用领域具有很重要的研究价值，因为在研究和应用过程中很多问题都最终归结为路径搜索问题，这类问题的解决具有一般性和通用性。在过去的时间里，研究者对路径搜索问题进行了广泛的研究，提出了不同的方法解决各种应用环境下的路径搜索问题。Dijkstra算法作为一个经典的最短路径求解算法，求解了从某个单源节点出发到其他节点的最短路径，在很多应用问题中得到了广泛的应用。A*算法是一种启发式路径搜索算法，它通过选取估计函数来确定其搜索方向，能够以较快的速度找到最优路径。A*算法在很多寻径问题，特别是电子游戏设计中得到了广泛的应用。遗传算法模拟了自然界中生物进化和遗传的过程，是采用优胜劣汰法则的一种智能搜索算法。遗传算法的特点是群体搜索和群体之间的个体之间进行信息交换，从而解决路径优化问题。蚁群算法是Dorigo等人提出的一种模拟进化算法，模拟了自然界中蚂蚁群体的觅食行为，是一种基于种群的启发式仿生进化算法。蚁群算法最早成功地应用于路径规划问题，由于它求解问题简单、搜索能力强，在很多领域发挥了它的作用。本文实现一种以函数调用为基础的路径搜索算法，能在有向图中搜索出所有满足条件的路径，并搜索到其中的最短路径。
1 环境图和问题定义
定义1. 图：图[5]是由定点集合及定点关系集合组成的一种数据结构，，其中，某数据对象集合是顶点有穷非空集合；或是定点之间关系的有穷集合，也称为边集合。其中，表示从u到v的一条单向通路，它是有方向的。
定义2. 有向图：有向图是指在图中顶点对
定义3. 权：某些图的边具有与之相关的数，称为权。这些权可以表示从一个顶点到另一个顶点的距离、花费的代价、所需的时间、次数等。
定义4. 邻接顶点：在有向图中，如果
定义5. 顶点的度：一个顶点v的度是与它相关联的边的条数。在有向图中，顶点的度等于该顶点的入度与出度之和。其中，顶点v的入度是以v为终点的有向图边的条数，记作；顶点v的出度是以v为始点的有向图边的条数，记作。顶点v的度。
定义6. 路径：在图中，若从顶点出发，沿一些边经过一些顶点，到达顶点。则称顶点序列为从顶点到顶点的路径。它经过的边、、…、为属于E的边。
定义7. 路径长度：对于不带权的图，路径长度是指此路径上边的条数。对于带权图，路径长度是指路径上各边的权之和。
定义8. 简单路径和回路：若路径上各个顶点均不重合，则称这样的路径为简单路径。若一路径上第一个顶点与最后一个顶点重合，则这样的路径称为回路。
在图中，用C++语法定义顶点V的数据结构如下：
const int N=3；
class Vertex
{
public：
char mark；
Vertex *point[N]；
}；
以上结构中，mark用来表示顶点标识，Vertex *point[N]用来标识指针数组，N为顶点的出度，N取大于零的整数值。
在一个具有众多如上述数据结构定义的顶点构成的有向图中，从某顶点开始求解到另一顶点的路径。这一问题的解决有多种方案，如：Dijkstra算法、A*算法、遗传算法和蚁群算法等。本文将给出一个基于函数调用的方法求解路径搜索问题，方案具有更好的确定性和可扩展性。
2 基于函数调用的路径搜索方法
在有向图中，给定一个任意顶点v0，求解其到达目标顶点vD的路径，要求路径长度小于M（边上不带权值）。
下面给出算法描述。
主函数的程序如算法1所示。
算法1. 定义每个顶点，生成M个节点对象。
（1）初始化各个顶点对象的mark属性值；
（2）通过给顶点对象的指针数组赋值，建立有向图；
（3）定义指针变量Vertex *p，令指针p指向源顶点v0的对象；
（4）路径数目count初始化为零，路径顶点索引值index置为零，初始化由顶点构成的路径轨迹path为空；
（5）调用子函数search（p， index， path）；
主函数的程序如算法2所示。
算法2.
以一个函数的形式说明算法。
void search（Cpoint * p ， int index， string path）
{
取出p指向当前对象，取出mark值，添加到path中；
index++；
如果index的值大于预设长度M，退出函数；
如果p指向的当前对象为结束对象，则count++，输出路径及其长度，退出函数；
定义顶点指针p0， p1，…， p（n-1），令其指向当前顶点的下一个顶点；
对于顶点指针px{ p0， p1，…， p（n-1）}，循环：
{
若px不等于NULL，调用函数search（px， index， path）}；
}
}
算法1实现了有向图顶点的生成、顶点之间连接边的定义，实现了源顶点对象指针的定义以及各个变量的初始化工作，然后调用算法2。
算法2从当前顶点开始运行，实现的终止条件包括：index的值大于预设长度M，退出函数，表示没有找到求解路径；当p指针指向终止节点，退出函数，此时找到了求解路径，输出结果。否则指针指向当前顶点的后继顶点，这是一个顶点集合，对顶点集合中非空的指针再调用算法2的search函数实现递归调用。
3 实验结果与分析
为了验证上述方法，给出一个有向图，如图1所示。图中共有10个顶点，用A～J标出。令顶点A为源顶点，顶点J为目标顶点，顶点指针p指向源顶点。限定路径长度的最大值为预设长度M，以求解长度小于M的路径集合。本试验的设定路径最大长度M=6，求解得到的路径集合如图2所示。
由图2可知，共搜索出满足条件的路径有12条，其中ABHJ为最短路径，其长度为4。预设不同的限定长度M，重做上述实验，得到相应的路径总数如表1所示。从表1中发现，随着限定路径长度的增加，搜索出的路径数目急剧增加。
4 结论
本文采用了一种方法实现了有向图的路径搜索。算法对有向图的顶点和边进行了结构描述，并从源顶点出发在限定路径长度的条件下，搜索出到达目标顶点的所有路径数目，同时给出了每条搜索路径的长度。从中也很容易找出人们所关心的最短路径。在本文方法的基础上很容易将算法扩展到带权有向图和无向图的情形。本算法的优点是在网络环境已知的情况下，能够很快找到确定性的路径，并具有较好的应用潜力。
参考文献
[1]Dijkstra E W.A note on two problems in connexion with graphs[J]. Numerische Mathematik，1959，1，（1）：269-271.
[2]Hart P E，Nilsson N J，Raphael，B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths [J].IEEE Transactions on Systems Science and Cybernetics，1968，4（2）： 100-107.
[3]王小平，曹立明.遗传算法—理论、应用与软件实现[M].西安：西安交通大学出版社，2006.
[4]Dorigo M，Gambardella L M.Ant colony system：a cooperative learning approach to the traveling salesman problem[J].Evolutionary Computation， IEEE Transactions on，1997，1（1）：53-66.
[5]段海滨，王道波，朱家强.蚁群算法理论及应用研究的进展[J].控制与决策，2004，19（12）：1321-1326.
[6]殷人昆，陶永雷，谢若阳.数据结构[M].北京：清华大学出版社，2004.
作者简介
刘颖姗（1998-），女，山东省日照市第一中学东校区2013级理科部高中生。
