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

Question

首先我会说我对 python 比较陌生，如果答案显而易见，请原谅我。我为有向图制作了一个 class，我需要添加一个方法来打印从起始顶点到结束顶点的所有非循环路径。我已经尝试了几次，但我尝试这样做的方式让我有点困惑。

这是我的 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 return 一个列表列表，其中每个内部列表都是一个路径序列。

例如，如果 A -> B，A -> C，B -> D，C -> D

那么从A到D有两条路径，pathFinder应该return:
[ ['A','B','D'] , ['A','C','D'] ]

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

编辑 - 添加代码以测试下面的 class：

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.

案例一

A -> B
A -> C
B -> D
C -> D

All non-cyclical paths from A to D:
[['A', 'B', 'D'], ['A', 'C', 'D']]

案例二

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

在评论中解释。

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

Printing all paths in a directed graph using lists

python

recursion

graph

list

directed-graph