파이썬 - 가장 긴 경로 찾기

이 함수는 사전을 입력으로 가져오고 사전에서 가장 긴 경로의 길이를 찾고 싶습니다. 기본적으로 사전에 key2가 value1과 일치하고 key3이 value2와 일치하는 경우 등이 경로로 계산됩니다. 예 :파이썬 - 가장 긴 경로 찾기

{'a':'b', 'b':'c', 'c':'d'}

위의 경우 길이는 3이어야합니다. 나는 이것을 어떻게 얻을 수 있을까? 또는 더 구체적으로 키를 값과 비교하는 방법은 무엇입니까? (숫자 일뿐만 아니라 문자열, 숫자 등이 될 수 있음)

미리 감사드립니다.

출처

2017-01-14 aRandomStudent

"키와 값을 비교해야하는 이유는 무엇입니까?" – alfasin

다른 방법을 확인하는 법을 모르겠습니다 ... 프로그래밍을 처음 사용했습니다 – aRandomStudent

루프가있을 수 있습니까? '{'a ':'b ','b ':'c ','c ':'d ','d ':'a '}'? – DyZ

내가 방향성 비순환 그래프 (DAG)의 가장자리의 목록으로 사전을 치료하고 그래프에서 가장 긴 경로를 찾기 위해 networkx 모듈을 사용합니다 : 당신이하지에 주장하는 경우

import networkx as nx 

data = {'a':'b', 'b':'c', 'c':'d'} 

G = nx.DiGraph() 
G.add_edges_from(data.items()) 
try: 
    path = nx.dag_longest_path(G) 
    print(path) 
    # ['a', 'b', 'c', 'd'] 

    print(len(path) - 1) 
    # 3 
except nx.exception.NetworkXUnfeasible: # There's a loop! 
    print("The graph has a cycle")

출처

2017-01-14 01:29:05 DyZ

정확하게 작동합니다! 원래 게시물에서 언급 했음에 틀림 없지만 모듈을 사용하지 않고이 작업을 수행 할 수있는 방법이 있습니까? – aRandomStudent

있어야합니다. 하지만 왜? 'networkx'의 기능을 재 구현해야합니다. – DyZ

아직 결정을 내리지 못했다면, 길고 굴곡이 많은 경로가 있습니다. 시작 위치는 다음과 같습니다. http://stackoverflow.com/questions/21880419/how-to-find-the-longest-simple-path- in-a-graph – DyZ

을

def find_longest_path(data): 
    longest = 0 
    for key in data.iterkeys(): 
     seen = set() 
     length = -1 
     while key: 
      if key in seen: 
       length = -1 
       raise RuntimeError('Graph has loop') 
      seen.add(key) 
      key = data.get(key, False) 
      length += 1 
     if length > longest: 
      longest = length 

    return longest

출처

2017-01-14 03:37:27 Batman

'RuntimeError ('Graph has loop')''length = -1' '휴식'은 불필요합니다. – DyZ

네 말이 맞아. 질문을 다시 읽은 후에'RuntimeError'를 추가했습니다. – Batman

파이썬 - 가장 긴 경로 찾기

답변

관련 문제