Strongly Connected Components
A strongly connected component
of a graph is a set of vertices such that for each pair
of vertices in the component, there exists a path from
This algorithm sorts the vertices in the different strongly connected components of the graph. It is implemented by the
which uses the
contains extension methods that hides these implementation details for you.
The concept of strong connectivity is very important in many algorithms because it means there is always “a way back”. For example, one expects that the directed graph that represent the different states of a dialog window is strongly connected, i.e. the user
can always go back or undo.
This sample shows how to compute and display the component information from a directed graph:
IDictionary<Vertex,int> components=new Dictionary<Vertex,int>();
int componentCount = g.StronglyConnectedComponents(components);
Console.WriteLine(“Warning the graph is not strongly connected”);
foreach(KeyValuePair<Vertex,int> kv in components)