python - 使用列表打印有向图中的所有路径

Question

我首先要说的是，我对 python 比较陌生，所以如果答案很明显，请原谅我。我为有向图创建了一个类，我需要添加一个方法来打印从起始顶点到结束顶点的所有非循环路径。我已经尝试过几次，但我尝试的方式让我有点困惑。

这是我的类(class):

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 有两条路径，pathFinder 应该返回:
[ ['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 条存在

Answer 1

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']]

评论中的解释。