파이썬에서 그래프/트리를 나타내는 법과주기를 감지하는 방법은 무엇입니까?

Question

파이썬에서 kruskal의 알고리즘을 구현하고 싶습니다. 트리/그래프를 어떻게 표현할 수 있습니까? 그리고주기를 감지하기 위해 어떤 방법을 사용해야합니까?

Answer 1

(제 생각에)을 표현하는 가장 간단한 방법은 배열 목록의 딕셔너리를 사용하는 것입니다 :

graph = {} 
graph[node_id] = [other_node_id for other_node_id in neighbors(node_id)] 

사이클을 찾는 간단한 방법은 BF 또는 DF 검색을 사용하는 것입니다 :

def df(node): 
    if visited(node): 
     pass # found a cycle here, do something with it 
    visit(node) 
    [df(node_id) for node_id in graph[node]] 

면책 조항 : 이것은 실제로 스케치입니다. neighbors(), visited() 및 visit()은 알고리즘이 어떻게 나타나야 하는지를 나타내는 단지 인물입니다.

Answer 2

Python Graph API은 좋은 출발점입니다.

예를 들어 NetworkX에는 최소 스패닝 트리를 찾기위한 Kruskal의 알고리즘 구현이 있습니다.

바퀴를 다시 발명하고 직접 만들고 싶다면 그럴 수도 있습니다.