Breaking Code

April 8, 2013

A Python example on finding connected components in a graph

Filed under: Programming — Tags: , , — Mario Vilas @ 10:30 pm

Today I’ve been coding a solution for a problem we’ve encountered with @ggdaniel (cr0hn) during the development of GoLismero 2.0. It called for an implementation of an algorithm to find connected components in an undirected graph. You can find the source code at the bottom of this post.


A graph algorithm a day keeps the CS doctor away…

Suppose we have an undirected graph (connected by lines rather than arrows) in which we can find one or more “islands” of nodes that form connections to each other, but not to nodes in other “islands”. In graph theory, these “islands” are called connected components. In the image below, we see a graph with three connected components:

Example graph with three connected components. Image from Wikipedia.

Now, suppose we have a set containing all nodes, and we can visit each node to know what are its neighbors, that is, the other nodes it’s connected to. We want to find all the connected components and put their nodes into separate sets. How would we do that?

(more…)

The Silver is the New Black Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 2,479 other followers