Python 求两点间所有路径

class Graph():#定义类
    nodes=list()
    edges=dict()#属性,分别创建空列表和字典并赋值
    def insert(self, a, b):
        if not(a in self.nodes):
            self.nodes.append(a)
            self.edges[a]=list()
        if not(b in self.nodes):
            self.nodes.append(b)
            self.edges[b]=list()
        #如果节点列表没有该节点则存入节点,并在字典中为其对应一个列表
        self.edges[a].append(b)
        self.edges[b].append(a)
        #为字典里节点对应列表存入相邻节点

with open('graph.txt','r') as f:
    txt = f.readlines()
f.close()
#打开文件按行读取并存入列表txt中,随手关门

graph=Graph()
for line in txt:
    a,b=line.split()
    graph.insert(a,b)
#对txt的元素进行遍历,将'a b'以空格为分隔符切开成a和b,再传入类的函数形成邻接字典

with open('result.txt','w') as f:
    f.close()
#只写打开文件再关闭,以此来清空文件内容

def printf(path):
    with open('result.txt','a') as f:
        for i in path:
            if (i == path[-1]):
                print(i, file=f)
            else:
                print(i, end="->", file=f)
    f.close()
#打印路径的函数,每次输出列表函数用箭头间隔,加入判断在最后一个元素输出时不加箭头

def findAllPath(graph, start, end, path=[]):
#定义寻找路径的函数
    path.append(start)
#将开始节点存入路径
    if start == end:
#递归的终止条件
        printf(path)
#抵达终点,打印路径
        path.pop()
#将最新进入的元素弹出栈
        return
#返回,不再执行剩下的语句

    for node in graph[start]:
#遍历开始节点的所有相邻节点
        if node not in path:
#同时这个节点不在路径上
            findAllPath(graph, node, end, path)
#递归调用函数,使该相邻节点做开始节点找路径
    path.pop()
#循环结束后,所有的相邻节点都遍历过一遍,该开始节点弹出

start=input("start:")
end=input("end:")
findAllPath(graph.edges,start,end)
#传入起点和终点,调用函数
暂无评论
标签: