深度优先搜索中的意外结果

Question

我正在实现一个图 class 并且想编写一个函数来确定给定路径是否存在。

我的图表示为{a:{b:c}}，其中a和b是相互连接的顶点，c是边的权重。 这是一个无向图。我想为非方向图实现我的 does_path_exist() 函数。 它目前的计算就像我的图是方向性的一样。

鉴于：

{0: {1: 5.0, 2: 10.0}, 1: {3: 3.0, 4: 6.0}, 3: {2: 2.0, 4: 2.0, 5: 2.0}, 4: {6: 6.0}, 5: {6: 2.0}, 7: {9: 1.0}, 8: {7: 2.0, 9: 4.0}}

存在从顶点 2 到 3 的路径。由于我的函数是面向方向的，所以它 returns 错误。

class Graph:
    def __init__(self, n):
        """
        Constructor
        :param n: Number of vertices
        """
        self.order = n
        self.size = 0
        self.vertex = {}

    def insert_edge(self, u, v, w): #works fine
        if u in self.vertex and v < self.order:
            if not v in self.vertex[u]:
                self.vertex[u][v] = w
                self.size += 1
        elif u not in self.vertex and u < self.order and v < self.order:
            self.vertex[u] = {}
            self.vertex[u][v] = w
            self.size += 1
        else:
            raise IndexError

    def does_path_exist(self, u, v): #works for directed graph, but not non-directed graph
        if u >= self.order or v >= self.order:
            raise IndexError
        if u == v:
            return True
        stac = []
        stac.append(u)
        visited = []
        while len(stac) != 0:
            u = stac.pop(0)
            if u not in visited:
                if u == v:
                    return True
                visited.append(u)
                if u in self.vertex:
                    t = self.vertex[u]
                else:
                    break
                a = t.keys()
                for u in a:
                    if u not in visited:
                        stac.append(u)
        return False

我的主要功能：

def main():

g = Graph(10)
g.insert_edge(0,1,5.0)
g.insert_edge(0,2,10.0)
g.insert_edge(1,3,3.0)
g.insert_edge(1,4,6.0)
g.insert_edge(3,2,2.0)
g.insert_edge(3,4,2.0)
g.insert_edge(3,5,2.0)
g.insert_edge(4,6,6.0)
g.insert_edge(5,6,2.0)
g.insert_edge(7,9,1.0)
g.insert_edge(8,7,2.0)
g.insert_edge(8,9,4.0)

print(g.vertex)
print(g.does_path_exist(2,3)) #returns False but should return True

if __name__ == '__main__':
    main()

Answer 1

您提到该图是有向图，但您在 insert_edge 函数中只分配了从 u 到 v 的边。我更新了函数，这样它也可以将边缘从 v 分配给 u 并返回 True 作为测试输入。

    def insert_edge(self, u, v, w): #works fine
        # Allow to travel from u to v
        if u in self.vertex and v < self.order:
            if not v in self.vertex[u]:
                self.vertex[u][v] = w
                self.size += 1
        elif u not in self.vertex and u < self.order and v < self.order:
            self.vertex[u] = {}
            self.vertex[u][v] = w
            self.size += 1
        else:
            raise IndexError

        # Allow travel to v from u
        if v in self.vertex and u < self.order:
            if not u in self.vertex[v]:
                self.vertex[v][u] = w
        elif v not in self.vertex and v < self.order and u < self.order:
            self.vertex[v] = {}
            self.vertex[v][u] = w
        else:
            raise IndexError

Answer 2

你的循环只检查出边。如果你给它u=2，它发现没有来自2的出边，所以它在一次迭代后结束。

您需要：

在 insert_edge() 的两个方向上添加有向边。这是 insert_edge() 中的更多工作，以及更多的内存使用。
在顶点字典中搜索循环中的后向边和前向边。 does_edge_exist().

深度优先搜索中的意外结果

Unexpected result in Depth First Search

python

graph-algorithm