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

Question

首先，我会说我对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的路径，pathFinder应该返回：
[ ['A','B','D'] , ['A','C','D'] ]

我看到了一些关于类似目标的其他实现/问题，但是我没有看到像我尝试的那样使用列表作为底层数据结构的任何东西。其他方法可能更好，但如果可能的话，我想继续我现在的方式。在

编辑-添加代码以测试以下类：

^{pr2}$

电流输出：

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

^{pr2}$

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

注释中的解释。在