comment représenter des graphes/arbres en python et comment détecter des cycles?

Question

Je veux implémenter l'algorithme de kruskal en python comment puis-je représenter l'arbre/graphique et quelle approche dois-je suivre pour détecter les cycles?

Answer 1

La façon la plus simple de le représenter (à mon avis) est en utilisant un dict de tableaux listes:

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

Une façon simple de trouver des cycles est à l'aide d'une recherche BF ou 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]] 

Avertissement: il s'agit en fait d'un croquis; , visited() et visit() sont juste des mannequins pour représenter comment l'algorithme devrait ressembler.

Answer 2

Python Graph API est un bon point de départ.

Par exemple, NetworkX a une implémentation d'algorithme de Kruskal pour trouver l'arbre recouvrant minimum.

Si vous voulez réinventer la roue et le faire vous-même, c'est également possible.