执行深度优先搜索的递归函数

Question

我试图编写一个从命令行初始化的递归函数，该函数获取一个文本文件，其中包含一系列起点、终点和这些点之间的距离，然后找到从特定起点到特定终点的最短距离。在

例如，文本文件如下所示：

a,b,5
a,c,8
b,d,6
c,d,2
d,e,12
d,f,2
e,g,3
f,g,7

会用类似于：

^{pr2}$

这个想法是基于我下学期要上的一节课的一个项目，我想先开始。教授提供了一个广泛的“开始代码”，找到了here。在

我尝试了多种不同的方法来实现递归函数来遍历文本文件并记录和比较点之间的距离，但我似乎不能正确地实现它。现在我有一个（非常明显不正确的）代码：

if place not in distances:
    print('not in')
    distances[place] =roads[place]
    dist_so_far = distances[place]     
    dfs(place, 0.0, roads, distances)
elif place in distances and distances[place] <= dist_so_far:
    print('less than')
    #dfs(place,0.0, roads, distances)
elif place in distances and distances[place] > dist_so_far:
    print('greater than')
    distances[place] = dist_so_far
    dfs(place, 0.0, roads, distances)

我知道这是不对的，我只是认为它的格式是一个很好的起点。我只是不明白哪些字典包含什么，哪些索引要比较。在

Answer 1

I just can't seem to understand which dictionaries contain what and what indexes to compare and it's driving me wild!

我将试着解释一下starting-point code that your professor posted及其作用，而不必在银盘上给出解决方案（因为你可以通过自己解决它学到更多）。在

def read_distances(map_file):
    connections = dict()
    # ....
    return connections

这个函数是建立一个字典，你可以用它来查找任何两点是否相互连接，以及它们之间的距离。因此，如果在输入文本文件中有一行“a，B，5”，则read_distances的结果将创建两个条目，一个用于值为("B",5)的a，另一个用于值为("A",5)的B。还请注意，该字典中的每个条目都将是连接的列表。换句话说：

^{pr2}$

如果有多个连接，例如，如果文本文件包含：

^{3}$

然后你会得到这样的信息：

distances = read_distances(map_file)
print(distances["A"])  # Will print "[('B',5),('C',3)]"
print(distances["B"])  # Will print "[('A',5),('C',4)]"
print(distances["C"])  # Will print "[('A',3),('B',4)]"

当你得到一个所有的连接点时。该列表由2个元组（即包含2个元素的元组）组成，每个元组都具有结构（other_point，distance_as_int）。在

我想我就到此为止了，因为这可能足够帮助你克服目前的问题，而不必为你解决这个问题。（我刚刚删除了我写的一段话“我建议如何解决这个问题”，因为我意识到除非你要求帮助，否则我不应该给你帮助。）如果你需要更多的帮助，请对这个答案（或你的问题）发表评论，我会收到通知的。我很乐意在这方面给你更多的帮助，尤其是你在上课前就已经采取了正确的方法自己解决问题。在

---

更新1:

好吧，再给你一个解决不了问题的建议。当您查找distances[starting_point]并获得一个元组列表时，您需要遍历该列表，对每个元组执行一些操作。E、 g

connections = distances[start_point]
for connection in connections:
    end_point = connection[0]
    distance = connection[1]
    # Now do something with start_point, end_point, and distance
    # Precisely *what* you'll do with them is up to you

这些代码可以简化一点，因为Python有一个很好的“tuple unpacking”特性：如果您正在循环生成元组的东西，比如您的“connections”列表，您可以这样做：

connections = distances[start_point]
for end_point, distance in connections:
    # Now do something with start_point, end_point, and distance
    # Precisely *what* you'll do with them is up to you

这将自动为您“解包”元组。请注意，只有当您知道将得到的所有元组都具有相同数量的项（在本例中为2）时，这才有效。还有一件事我们可以做，那就是注意到我们并不需要这个connections变量，因为我们除了循环使用它之外，并没有使用它。消除这些，代码就会变成：

for end_point, distance in distances[start_point]:
    # Now do something with start_point, end_point, and distance
    # Precisely *what* you'll do with them is up to you

这是编写特定循环的最清晰、最“Pythonic”的方法。在

注意：上面的代码实际上不会按原样运行，因为Python要求任何循环中必须至少有一个语句，而注释不算作语句。要使代码实际运行，必须在循环中包含pass语句。pass语句是一个特殊的语句，它只是一个“no-op”，也就是说，它完全不做任何事情。因此，要想让实际上运行上面在循环中什么都不做的代码，您应该写：

^{8}$

这个循环是允许的，而没有单词pass的代码将产生一个IndentationError。为了简单起见，我在上面的所有示例中都没有使用pass，但我认为值得一提的是，为什么代码不能准确地按原样运行。在

---

更新2:

根据要求，这里有一个函数可以解决这个问题，这样您就可以一步一步地了解发生了什么。我已经添加了大量的注释，但是如果没有注释，这将只有8行代码。在

def dfs(place, dist_so_far, roads, distances):
    """Depth-first search, which may continue from from_place if dist_so_far
        is the shortest distance at which it has yet been reached.
       Args:
          place: Currently searching from here
          dist_so_far:  Distance at which from_place has been reached
              this time (which may not be the shortest path to from_place)
          roads:  dict mapping places to lists of hops of the form (place, hop-distance)
          distances: dict mapping places to the shortest distance at which they
               have been reached so far (up to this time).
    """
    #FIXME
    #   Consider cases:
    #      - We've never been at place before (so it's not in distances)
    #      - We've been at place before, on a path as short as this one (in distances)
    #      - We've been here before, but this way is shorter (dist_so_far)
    #    Consider which are base cases, and which require recursion.
    #    For the cases that require recursion, what is the progress step?

    # First scenario: we've never reached this place before
    if place not in distances:
        # Right now we only know one way to get to this place,
        # so that's automatically the shortest known distance.
        distances[place] = dist_so_far

    # Second scenario: we've been here before, via a route
    # that was shorter than dist_so_far. If so, then any
    # roads from here lead to places we've also already
    # visited via a shorter route. Any distance we calculate
    # right now would just be longer than the distance we've
    # already found, so we can just stop right now!
    if dist_so_far > distances[place]:
        return

    # Third scenario: dist_so_far is actually the shortest
    # path we've found yet. (The first scenario is actually
    # a special case of this one!) We should record the
    # shortest distance to this place, since we'll want to
    # use that later. Then we'll look at all the roads from
    # this place to other places, and for each of those
    # other places, we'll make a recursive call to figure
    # out more paths.

    # Note no "if" statement needed: because of the return
    # statement earlier, if we get here, we know that the
    # current route is the best one yet known.
    distances[place] = dist_so_far

    # Now for some recursion:
    for other_place, hop_distance in roads[place]:
        dist_to_other_place = dist_so_far + hop_distance
        dfs(other_place, dist_to_other_place, roads, distances)

    # That's it!

是的，就是这样。我对您提供的示例距离文件进行了运行，它为每对点找到了可能的最短距离。试着在脑子里一步一步地运行这个算法，看看你是否理解这一点。在

然而，有一个需要你理解的关键概念，可能不会立即显而易见你先看看这个。这个关键概念是：Python字典是持久的和可变的。也就是说，如果您将dictionary对象（如本例中的distances字典）传递给函数，并且该函数修改字典，传递给函数的字典将被修改。在

顺便说一句，专业程序员倾向于认为这是一件不好的事情，因为调用函数不应该意外地修改参数。这往往会在程序中引起微妙的、难以追踪的错误，通常应该避免。（不过，请注意那句话中的这个词出乎意料地。如果您调用的函数名为add_value_to_dict，那么您可能希望字典被修改。）

然而，在这种特殊情况下，字典修改效果（通常被认为是一种坏的副作用）是编写高效代码的关键。目前正在使用distances字典来跟踪我们目前所发现的内容，并查看是否还有任何工作要做。由于您希望通过对dfs()的递归调用来修改它，所以您不会为自己创建细微的bug。但我不想让你觉得这里使用的技术，修改作为函数参数传入的字典，一直是个好主意。大多数情况下，它会导致一些细微的错误，你要等到几个月后才能发现。在

好吧，这也许足够解释了。看看你能不能在脑子里一步一步地理解这些代码。如果有什么让你困惑的，告诉我。在