连通图中任意两顶点间所有路径的求取算法

• 作者: 王军 田波
• 来源期刊: 福建电脑
• 关键词: 连通图 路径搜索 栈 深度优先
• 年，卷（期）: 2017,（12）
• 所属期刊栏目: 基金项目论文
• 页码范围: 16-17
• 页数: 2页
• 字数: 2327字
• 语种: 中文
• DOI: 10.16707/j.cnki.fjpc.2017.12.007

摘要

连通图中任意两顶点间所有路径的求取是路径搜索(path search)中的一个重要问题.通过采用邻接表为存储结构,栈存储每轮搜索的路径,而标志数组用来标志每一轮搜索过程中路径上的顶点是否被访问,提出一种基于深度优先的求取任意两顶点间所有的路径的求取算法.分析表明,该算法空间复杂度和时间复杂度较低,可以满足各类嵌入式设备的要求,具有较强的实际应用价值.