有向图中的深度：查找距给定节点k公里的节点

Question

我正在尝试使用函数来查找距给定节点k距离的节点。

这是我的代码：

def depth(graph, start, k):
    def levels(graph, start, visited, current_nodes, k):
        #base case
        if k == 0:
            return current_nodes
        else:
            current_nodes = []
        #if no neighbors, return
        if graph.adjacent_nodes(start) == []:
            return []
        for nodes in graph.adjacent_nodes(start):
            if nodes not in visited:
                visited.append(nodes)
            current_nodes.append(nodes)
        print("visited =", visited)
        print("current_nodes =", current_nodes)
        print("k =", k)
        for nodes in current_nodes:
            return levels(graph, nodes, visited, current_nodes, k-1)

    visited = [start]
    current_nodes = []
    required_nodes = levels(graph, start, visited, current_nodes, k)
    print(required_nodes)
    return required_nodes

这可以在Spyder中实现，但是对于我的在线课程而言，这不是（我刚刚开始学习）。我正在打印visited，current_nodes和k以查看发生了什么。

例如，对于a->b->c->d和start = a的k = 5，它应该返回一个空列表，这意味着在距离5的a处没有节点。 Spyder的输出如下：

visited = ['a', 'b']
current_nodes = ['b']
k = 5
visited = ['a', 'b', 'c']
current_nodes = ['c']
k = 4
visited = ['a', 'b', 'c', 'd']
current_nodes = ['d']
k = 3
[]

但是，对于在线课程，输出如下：

visited =  ['A', 'B']
current_nodes =  ['B']
k =  5
visited =  ['A', 'B', 'C']
current_nodes =  ['C']
k =  4
visited =  ['A', 'B', 'C', 'D']
current_nodes =  ['D']
k =  3
[]
visited =  ['A', 'B']
current_nodes =  ['B']
k =  4
visited =  ['A', 'B', 'C']
current_nodes =  ['C']
k =  3
visited =  ['A', 'B', 'C', 'D']
current_nodes =  ['D']
k =  2
[]
visited =  ['A', 'B']
current_nodes =  ['B']
k =  3
visited =  ['A', 'B', 'C']
current_nodes =  ['C']
k =  2
visited =  ['A', 'B', 'C', 'D']
current_nodes =  ['D']
k =  1
['D']
visited =  ['A', 'B']
current_nodes =  ['B']
k =  2
visited =  ['A', 'B', 'C']
current_nodes =  ['C']
k =  1
['C']
visited =  ['A', 'B']
current_nodes =  ['B']
k =  1
['B']
[]
visited =  ['A', 'B', 'D']
current_nodes =  ['B', 'D']
k =  3
visited =  ['A', 'B', 'D', 'C']
current_nodes =  ['C']
k =  2
visited =  ['A', 'B', 'D', 'C']
current_nodes =  ['D']
k =  1
['D']

有人可以告诉我我的代码是否有问题吗？

Answer 1

问题是current_nodes不应该附加已访问过的节点。在检查了相邻节点之后，如果current_nodes为空，则没有其他事情可做，因此返回一个空列表（指示在k距离处未找到任何节点）。

def depth(graph, start, k):
    def levels(graph, start, visited, current_nodes, k):
        '''BASE CASE'''
        if k == 0:
            return current_nodes
        else:
            current_nodes = []
        '''IF NO NEIGHBORS, RETURN AN EMPTY LIST'''
        if graph.adjacent_nodes(start) == []:
            return []
        for nodes in graph.adjacent_nodes(start):
            if nodes not in visited:
                visited.append(nodes)
                current_nodes.append(nodes)
        print("visited = ", visited)
        print("current_nodes = ", current_nodes)
        print("k = ", k)
        '''IF ALL ADJACENT NODES ALREADY VISITED, CURRENT NODES WILL BE EMPTY, RETURN []'''
        if current_nodes == []:
            return []
        '''RECURSION'''
        for nodes in current_nodes:
            return levels(graph, nodes, visited, current_nodes, k-1)

    visited = [start]
    current_nodes = []
    required_nodes = levels(graph, start, visited, current_nodes, k)
    print(required_nodes)
    return required_nodes