how to represent graphs /trees in python and how to detect cycles?

i want to implement kruskal's algorithm in 开发者_C百科python how can i go about representing the tree/graph and what approach should i follow to detect the cycles ?

---

The simplest way of representing it (in my opinion) is by using a dict of arrays lists:

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

A simple way of finding cycles is by using a BF or DF search:

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]]

Disclaimer: this is actually a sketch; neighbors(), visited() and visit() are just dummies to represent how the algorithm should look like.

---

Python Graph API is a good place to start.

For example, NetworkX has a Kruskal's algorithm implementation to find the minimum spanning tree.

If you want to re-invent the wheel and do it yourself, that is also possible.