Introduction: Connected Components and Cycles
In previous blog posts, we've gone over graph theory, adjacency lists, adjacency matrixes, and BFS/DFS. We had another blog post on shortest paths in a graph. We also looked at maximum flow using the Ford Fulkerson Algorithm.
Today, we'll look at connected components and cycles in a graph. The graph that we'll be playing with is below.
A graph has some vertices, named nodes. It also has some edges, that connect nodes. But that doesn't mean that all nodes are reachable from all other nodes, and that everything is connected nicely. For example, we could have 10 nodes, but only 1 edge. That's still a valid graph.
A "connected component" is a set of vertices/edges that are connected. (The vertices can reach each other through edges.)
In our code, we'll represent connected components by labeling them with a number. We'll create an array that, for each node in the graph (the node being represented by the index in the array), holds the number for the connected component the node is in.
To find out which connected component each node is in, we'll do a DFS and label each node as we see it.
Note: There's a special case where a node in a connected component does not get reached by other nodes, but is still part of a connected component. For example, node 15 in our group can go to node 14, but no other node can get to 15. We have to make sure that if a node can reach another node that's already part of a connected component, (Basically, someone shows up late to class, the class has people getting together to form groups for a project, but the guy's friend already got them both a group.)
A cycle in a graph happens if it's possible to travel along the edges on a graph where you can revisit a previous node. For example, in our graph above, someone on node 4 can get to node 3, and from node 3 they can get to node 1, and then from node 1 they can get back to node 4. That's a cycle.
The code to find a cycle is pretty simple. It's just a DFS or BFS, and if we ever "visit" a node that's already been visited before, then we've detected a cycle.