这个Python函数如何返回数字，但也是一个字典？

下面是我们正在学习节点，路径等的算法类的分配。代码旨在检查一个节点是否可以从另一个节点到达。下面的代码工作，但我不清楚为什么。 G是包含每个节点作为关键字的“图形”，值为它连接的节点。下面的mark_component函数返回给定节点的多个节点。这个Python函数如何返回数字，但也是一个字典？

然而，其目的是返回True如果两个节点都可访问的功能check_connection，它调用此函数mark_component，然后进行测试，看看如果一个节点是在一本字典。

我不明白的是check_connection开始与“标记”一个空的字典，然后使用该字典要求mark_component。节点然后被添加到它。但是，mark_component返回一个数字，那么check_connection函数如何能够“读取”标记的内容呢？就这个功能而言，我认为标记仍然是空的。我想我假设标记是一个包含字典的局部变量，但它显然可以传递给另一个函数并进行更改。

任何人都可以向我解释这个吗？非常感谢

def mark_component(G, node, marked): 
    marked[node] = True 
    total_marked = 1 
    for neighbor in G[node]: 
     if neighbor not in marked: 
      total_marked += mark_component(G, neighbor, marked) 
    return total_marked 

def check_connection(G, v1, v2): 
    # Return True if v1 is connected to v2 in G 
    # or False if otherwise 
    marked = {} 
    mark_component(G, v1, marked) 
    return 'a' in marked  


G = {'a': {'d': 1, 'g': 1}, 'c': {'g': 1}, 'b': {'f': 1}, 
    'e': {'h': 1, 'f': 1}, 'd': {'a': 1, 'g': 1}, 
    'g': {'a': 1, 'c': 1, 'd': 1}, 'f': {'b': 1, 'e': 1}, 'h': {'e': 1}} 



print check_connection(G,'a', 'b')

来源

2014-02-06 Andy

这在别处详细解释。例如，请参阅[这里]（http://stackoverflow.com/questions/986006/python-how-do-i-pass-a-variable-by-reference/986145#986145）。 –

是，marked本身是一个可变的数据结构，这意味着它的内容可以甚至在其原有范围的改变。当marked传递给mark_component功能，后者接收到marked对象的引用，并且还能够通过访问使用索引（即marked[node]），该参考来更新其内容。

但是，函数check_connection仍然参照储存在变量marked中的内存中的marked对象。当执行表达式'a' in marked时，marked引用由mark_component函数更新的对象。

这个概念类似于如C和C++等语言中的指针概念（又名int * pointer）。

来源

2014-02-06 02:19:05 rae1

感谢@ rae1由于某种原因，我虽然变量是本地内的功能，这是我的困惑开始。 – Andy

我想这个算法没有很好的实现。

这是一个有向图中的贪婪搜索。我从第一个节点（v1）开始，尝试尽可能地走。然后，它转向另一个节点。我们还在过程中标记访问过的笔记。

那么，它做了一些简单的优化。如果该节点已被访问，请不要再次执行此操作。因此，我不会“检查”单个节点两次。

check_connection（）的最后一行是错误的。我们应该检查v2是否被访问过。因此，代码应该是

def mark_component(G, node, marked): 
    marked[node] = True 
    total_marked = 1 
    for neighbor in G[node]: 
     if neighbor not in marked: 
      total_marked += mark_component(G, neighbor, marked) 
    return total_marked 

def check_connection(G, v1, v2): 
    # Return True if v1 is connected to v2 in G 
    # or False if otherwise 
    marked = {} 
    mark_component(G, v1, marked) 
    return v2 in marked 


G = {'a': {'d': 1, 'g': 1}, 'c': {'g': 1}, 'b': {'f': 1}, 
      'e': {'h': 1, 'f': 1}, 'd': {'a': 1, 'g': 1}, 
      'g': {'a': 1, 'c': 1, 'd': 1}, 'f': {'b': 1, 'e': 1}, 'h': {'e': 1}} 



print check_connection(G,'a', 'b')

让我们通过一些python的想法。 Python总是通过引用传递参数（在C++中指向指针）。因此，调用者可以看到被调用者所做的更改。另一个是“x in b”。 “in”是在大多数python容器中实现的运算符。对于“标记”（字典），就好像v2是标记的键之一。实际上，建议在python中这样做。

来源

2014-02-06 02:24:05 liuyruc

这听起来像你对我不承认mark_component被称为递归。在第一次调用mark_component之后，它会再次被调用以通过图表。正如其他人提到的那样，你会经常看到这种模式。

来源

2014-03-07 10:52:08

这个Python函数如何返回数字，但也是一个字典？

回答

相关问题