이 파이썬 함수는 숫자뿐만 아니라 사전을 어떻게 반환합니까?

Question

다음은 노드, 경로 등을 배우는 알고리즘 클래스에 대한 할당입니다.이 코드는 한 노드가 다른 노드에 도달 할 수 있는지를 확인하도록 설계되었습니다. 아래의 코드는 작동하지만 왜 불분명합니다. G는 각 노드가 키로 연결되어있는 값인 "노드"가있는 "그래프"입니다. 아래의 mark_component 함수는 주어진 노드에서 여러 개의 노드를 반환합니다.

그러나 두 노드에 도달 할 수 있으면 True를 반환하도록 설계된 check_connection 함수에서이 함수는 mark_component 함수를 호출 한 다음 노드가 사전에 있는지 테스트합니다.

check_connection은 빈 사전 "marked"로 시작한 다음이 사전을 사용하여 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') 

Answer 1

예, marked 자체는 변경 가능한 데이터 구조, 그 내용을 의미한다하더라도 원래의 범위를 외부에서 변경 될 수 있습니다. marked이 mark_component 함수로 전달되면 후자는 marked 개체에 대한 참조를 받고 인덱서 (예 : marked[node])를 사용하여 해당 참조에 액세스하여 해당 콘텐츠를 업데이트 할 수 있습니다.

그러나 함수 check_connection은 여전히 ​​변수 marked에 저장된 메모리에있는 marked 개체에 대한 참조를가집니다. 'a' in marked이라는식이 실행되면 marked은 mark_component 함수로 업데이트 된 개체를 나타냅니다.

이 개념은 C 및 C++와 같은 다른 언어의 포인터 개념 (예 : int * pointer)과 유사합니다.

Answer 2

나는이 알고리즘이 잘 구현되지 않았다고 생각한다.

이것은 유향 그래프에서 욕심이 많습니다. 나는 첫 번째 노드 (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 아이디어를 살펴 보겠습니다. 파이썬은 항상 참조로 인수를 전달합니다 (C++의 v.s 포인터). 따라서 호출자는 호출 수신자가 수행 한 변경 사항을 볼 수 있습니다. 또 다른 하나는 "x in b"입니다. "in"은 대부분의 파이썬 컨테이너에 구현 된 연산자입니다. "marked"(사전)의 경우 v2가 표시된 키 중 하나 인 것과 같습니다. 사실 파이썬에서 그렇게하는 것이 좋습니다.

Answer 3

mark_component가 재귀 적으로 호출되는 것을 인식하지 못하는 것 같아요. mark_component에 대한 첫 번째 호출 이후 그래프를 통해 다시 작동하기 위해 다시 호출됩니다. 다른 사람들이 언급했듯이, 자주 보게 될 패턴입니다.