Python - en uzun yolu bul

Question

İşlev bir sözlükte girdi olarak alacaktır ve sözlükte en uzun yolun uzunluğunu bulmak istiyorum. Temel olarak, eğer bir sözlükte, anahtar 2 değeri 1 ile eşleşir ve 3 tuşu değer 2 ile eşleşirse, vb., Bu bir yol olarak sayılır. Örneğin: Yukarıdaki durumda, uzunluk üç olmalıdır. Örneğin, bu durumda, üç adet olmalıdır. Bunu nasıl başarabilirim? Ya da daha spesifik olarak, anahtarları değerlerle nasıl karşılaştırırım? (sadece bir sayı, dizge, sayı, vb. olabilir)

Çok teşekkürler şimdiden!

Answer 1

Ben yönlendirilmiş Mercury grafikte (DAG) kenarların liste olarak sözlüğü tedavi ve grafikte en uzun yolu bulmak için networkx modülünü kullanabilirsiniz: Eğer değil ısrar ediyorsanız

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") 

Answer 2

herhangi bir şeyi yapabileceğiniz her şeyi içe aktarabilirsiniz:

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