這個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函數如何返回數字，但也是一個字典？

回答

相關問題