题目
设计并实现求两点间所有路径的算法
代码应能读取规定格式的TXT文档作为输入，格式如下：
5 7 #第一行：图的节点数N，边数V
1 2 #后续V行： 图中每一条边的起点、终点
1 5
2 3
2 4
3 4
3 5
4 5
2 5 #最后一行：待求解目标的起点、终点
代码应以直观的形式输出所有可行路径，以便于结果检查。例如：
2->1->5
...
2->4->3->5
或
2 1 5
...
2 4 3 5
等等
检查时，我们将通过不同的图输入来检查代码的运行结果，例如一个包含14个节点，46条边的图，或一个20节点，156条边的图进行检查。因此请保证提交的代码在运行不同规模的问题时不会出现兼容性问题。
思路
计划利用深度搜索找出所有可能的路径。
为此，需要先将所有与起点相连的边，变化为从起点出发，而无法返回的有向边，从而避免多次经过起点。
接下来采用深度搜索的递归算法，同时定义global堆栈记录查找路径。
在搜索时还要进行判断，避免在两个节点之间来回跳动的情况发生。
graphviz的使用
首先需要前往官网下载软件包进行安装，接下来再用pip：
pip install graphviz
然后即可正常使用
from graphviz import Digraphdot = Digraph(comment='Gragh2Print') #新建图
dot.edge_attr.update(arrowhead='none') #去除箭头
dot.graph_attr['rankdir'] = 'LR' #左右顺序排列dot.node("name", "lable") #新建节点
dot.edge("name1", "name2") #新建边name1->name2
dot.render('graph-output/output.gv', view=True) #渲染为pdf并打开
代码实现
#!/usr/bin/env python3
#find_all_routes_of_2_points.py
#fumiama 20201001
import sys
from graphviz import Digraphdot = Digraph(comment='Gragh2Print')
dot.edge_attr.update(arrowhead='none')
dot.graph_attr['rankdir'] = 'LR'edgeLinks = dict()
size = 0stack = []
nodeNumber = 0def exitWithError(*error):print(*error)exit()def printGraph2Pdf(grf): grf.render('graph-output/output.gv', view=True)def printRoute(stackList):global nodeNumbernodeNumber += 1dot.node(str(nodeNumber), stackList[0])for node in stackList[1:]:nodeNumber += 1dot.node(str(nodeNumber), node)dot.edge(str(nodeNumber-1), str(nodeNumber))def addEdge(a, b):global edgeLinksif a not in edgeLinks: edgeLinks[a] = set()if b not in edgeLinks: edgeLinks[b] = set()edgeLinks[a].add(b)edgeLinks[b].add(a)def loadGraph(fileName):try: f = open(fileName, 'r')except: exitWithError("打开文件失败, 请检查文件名是否正确或程序是否有权限访问")global size, edgeLinkssize, edgeCount = map(int, f.readline().split())print("节点:", size, "边数:", edgeCount)for i in range(1, size+1): dot.node(str(i), str(i))for i in range(edgeCount):a, b = f.readline().split()addEdge(a, b)dot.edge(a, b)re = f.readline()f.close()return redef findAllRoutes(prev, start, end):global edgeLinks, stackstack.append(start)if start == end:print("找到路径:", stack)printRoute(stack)stack.pop()else:for nextPoint in edgeLinks[start]:if prev != nextPoint: findAllRoutes(start, nextPoint, end)stack.pop()def rmRoute2Itself(start):for point in edgeLinks:if point != start and start in edgeLinks[point]:edgeLinks[point].remove(start)if __name__ == '__main__':if len(sys.argv) != 3: exitWithError("用法:", sys.argv[0], "[pdf|nopdf] 文件位置")else:a, b = loadGraph(sys.argv[2]).split()print("起点:", a, "终点:", b)rmRoute2Itself(a)nodeNumber = size + 1findAllRoutes(a, a, b)if sys.argv[1] == "pdf":print("生成pdf格式图形化报告...")printGraph2Pdf(dot)
输出效果
输入数据如下：
16 20
1 2
1 5
2 3
2 4
3 4
3 5
4 5
5 7
5 14
5 6
6 9
7 4
9 4
10 6
11 5
12 7
13 8
13 6
15 13
16 10
2 5
控制台输出：
./find_all_routes_of_2_points.py pdf graph_sample.txt
节点: 16 边数: 20
起点: 2 终点: 5
找到路径: ['2', '3', '5']
找到路径: ['2', '3', '4', '9', '6', '5']
找到路径: ['2', '3', '4', '7', '5']
找到路径: ['2', '3', '4', '5']
找到路径: ['2', '1', '5']
找到路径: ['2', '4', '9', '6', '5']
找到路径: ['2', '4', '3', '5']
找到路径: ['2', '4', '7', '5']
找到路径: ['2', '4', '5']
生成pdf格式图形化报告...
生成pdf如下：
