Dict을 사용한 Python Depth First Search

Question

Depth First Search에 대한 의사 코드가 계속 표시되어 내 특정 문제와 관련하여 완전히 혼란 스럽습니다. 나는 '유향 그래프'가 강하게 연결되어 있는지 판단하려고합니다.

나는 가장자리 무게 나타내는 두 문자열 (첫 번째 대상을 나타냅니다, 소스를 나타냄) 및 선택적 번호가있는 딕셔너리가있는 경우 :

{'Austin': {'Houston': 300}, 'SanFrancisco': {'Albany': 1000}, 'NewYorkCity': { 'SanDiego': True }} 

가 어떻게의 요소 중 일부를 구현할 수 있습니다 DFS? 나는 정점 'Austin'에서 시작할 수 있고 'Houston'은 또 다른 정점이라는 것을 알고 있습니다. 나는 내 시작으로 '오스틴'을 통과 할 수 있음을 알 수

function graph_DFS(start): 
    # Input: start vertex 
    S = new Stack() 
    # Mark start as visited 
    S.push(start) 
    while S is not empty: 
     node = S.pop() 
     # Do something? (e.g. print) 
     for neighbor in node’s adjacent nodes: 
      if neighbor not visited: 
       # Mark neighbor as visited 
       S.push(neighbor) 

:하지만 난이 의사를 가지고있는 것처럼이 모든 파이썬 코드

에서 어떻게 작동하는지 볼 수 없습니다. 하지만 전 세계에서 어떻게 '오스틴'을 방문하도록 설정했으며, 어떤 노드가 '오스틴'에 인접 해 있는지 어떻게 알 수 있습니까?

그래프가 강하게 연결된 경우 어떻게 알고리즘을 사용하여 true 또는 false를 반환 할 수 있습니까?

의사 코드에서 코드로의이 전송을 보는 데 어려움을 겪고 있습니다. 어떤 도움을 주시면 감사하겠습니다.

Answer 1

내가 오스틴을 처음 시작할 수 있음을 알 수 있습니다. 하지만 어떻게 세상에서 내가 오스틴을 방문하도록 설정합니까, 그리고 어떤 노드가 인접한 지 어떻게 알 수 있습니까? 'Austin'에 ?

코드에서 '오스틴'이 튀어 나왔다는 것을 알 수 있으므로 다시 살펴볼 필요가 없습니다. 데이터 구조에서는 꼭지점에서 하나의 가장자리 만 허용하므로 두 개 이상의 이웃을 가질 수 없습니다.

그래프가 강하게 연결된 경우이 알고리즘을 사용하여 true 또는 false를 반환하는 방법은 무엇입니까?

이것은 단지 유틸리티 DFS 함수이며 그래프가 강하게 연결되어 있는지 여부를 찾는 알고리즘으로 DFS를 두 번 실행해야합니다. 기본적으로 힌트는 DFS를 실행할 때 트리가 있는지 또는 포리스트가 있는지 여부를 알고 자하는 것입니다.

제 생각에는 모든 키의 값이 목록 (모서리가있는 정점)이되도록 데이터 구조를 업데이트해야합니다. 나중에 필요한 경우 가중치도 목록에 저장할 수 있습니다.