我会首先说我对python相对较新，所以如果答案很明显，请原谅我。我为有向图创建了一个类，我需要添加一个方法来打印从起始顶点到结束顶点的所有非循环路径。我已经尝试了几次，但我尝试这样做的方式让我有点困惑。
这是我的班级：
import string
class Graph(object):
def __init__(self):
self.vertexlist = []
self.edgelist = []
self.numedges = 0
self.numvertices = 0
def add_vertex(self, name):
check = False
for item in self.vertexlist:
if name == item:
check = True
break
if check is False:
self.vertexlist.append(name)
self.numvertices = self.numvertices + 1
else:
print "A vertex with that name already exists."
def add_edge(self, start, end):
if start not in self.vertexlist:
self.vertexlist.append(start)
self.numvertices += 1
if end not in self.vertexlist:
self.vertexlist.append(end)
self.numvertices += 1
tempedge = [start, end]
self.edgelist.append(tempedge)
self.numedges += 1
def remove_vertex(self, name):
if name in slef.vertexlist:
self.vertexlist.remove(name)
self.numvertices = self.numvertices - 1
else:
pass
def remove_edge(self, start, end):
for item in self.edgelist:
if item[0] is start and item[1] is end:
self.edgelist.remove(item)
self.numedges = self.numedges - 1
def vertices(self):
return self.vertexlist
def print_edges(self):
for x in self.edgelist:
print x[0] + " -> " + x[1]
def is_connected(self, start, end):
for item in self.edgelist:
if item[0] is start and item[1] is end:
return True;
return False
def pathFinder(self, begin, fin, p = None): # print_paths helper function
if p is None:
p = []
p = p + [begin]
if begin == fin:
return [p]
pathing = []
for item in self.edgelist:
if item[0] not in p:
newpath = self.pathFinder(item[0], fin, p)
for i in newpath:
pathing.append(i)
return pathing
def print_paths(self, start, end):
temp = self.pathFinder(start, end)
print temp
最后两个函数是我遇到问题的函数(print_paths和pathFinder)。目标是让pathFinder返回列表列表，其中每个内部列表都是一个路径序列。
例如，如果 A -> B、A -> C、B -> D、C -> D
那么从 A 到 D 有两条路径，路径查找器应该返回：[ ['A','B','D'] , ['A','C','D'] ]
我已经看到了一些关于类似目标的其他实现/问题，但我还没有看到任何像我试图的那样使用列表作为底层数据结构的东西。其他方式可能会更好，但如果可能的话，我想继续我现在的方式。
编辑 - 添加代码以测试下面的类：
from graph import Graph
g = Graph()
g.add_vertex('A')
g.add_vertex('A')
g.add_vertex('B')
g.add_vertex('C')
print "nVertices:", g.vertices()
g.add_edge('A', 'B')
g.add_edge('B', 'C')
g.add_edge('C', 'D')
g.add_edge('C', 'B')
g.add_edge('B', 'D')
g.add_edge('D', 'A')
print"nEdges:"
g.print_edges()
print "nA->B?", g.is_connected('A', 'B')
print "B->A?", g.is_connected('B', 'A')
print "C->D?", g.is_connected('C', 'D')
print "nAll non-cyclical paths from A to D:"
g.print_paths('A', 'D')
电流输出：
A vertex with name 'A' already exists.
Vertices: ['A', 'B', 'C']
Edges:
A -> B
B -> C
C -> D
C -> B
B -> D
D -> A
A->B? True
B->A? False
C->D? True
Paths from A to D:
[['A', 'B', 'C', 'D'], ['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C',
'B', 'D'], ['A', 'C', 'B', 'D'], ['A', 'C', 'D'], ['A', 'C', 'B', 'D'],
['A', 'C', 'B', 'D'], ['A', 'C', 'D'], ['A', 'B', 'C', 'D'], ['A', 'B', 'C',
'D'], ['A', 'B', 'D'], ['A', 'D']]
它提供了 13 条可能的路径，但实际上只有 2 条存在
graph.py
import string
import copy
class Graph(object):
...
def print_paths(self, start, end):
# Initialise a dict mapping nodes to whether they've been
# visited or not. Each path must maintain state about which
# nodes have been visited, and one path must not clash with
# another.
visited = {v : False for v in self.vertexlist}
temp = self.pathFinder(start, end, visited)
print temp
def pathFinder(self, begin, fin, visited, p=None):
# Mark this node as visited.
visited[begin] = True
if p is None:
p = []
p = p + [begin]
# Stopping condition - Success.
if begin == fin:
return [p]
pathlist = []
# Since you're using a list to store edges,
# this makes things a little messy.
# We need to check for a couple of things.
for item in self.edgelist:
# First, make sure that we are following a valid path
# and second, make sure the end of this edge has not
# already been visited. If not, we're ready to jump in
if begin == item[0] and not visited[item[1]]:
# The next recursive call will take a
# fresh copy of visited and attempt to repeat
# the process until it has found the end.
newpath = self.pathFinder(item[1], fin, copy.copy(visited), p)
pathlist.extend(newpath)
return pathlist # Stopping condition - Failure.
案例1
A -> B
A -> C
B -> D
C -> D
All non-cyclical paths from A to D:
[['A', 'B', 'D'], ['A', 'C', 'D']]
案例2
A -> B
B -> C
C -> D
C -> B
B -> D
D -> A
All non-cyclical paths from A to D:
[['A', 'B', 'C', 'D'], ['A', 'B', 'D']]
评论中的解释。