Menu
I'm trying to find out it there is a way of finding the largest connected component in a adj matrix graph. Such as this:
0000000110
0001100000
0000000000
0100000010
0100000100
0000000100
0000000000
1000110000
1001000000
0000000000
I've Google'd the problem and am struggling to find anything, I've also read though the wiki article on graph theory and no joy. I assume their must be an algorithm out there to solve this problem. Can anybody point me in the right direction and give me some pointers on what I should be doing to solve this myself?
788
Suppose the graph has adjacency matrix A and n vertices. Compute M=(A+I)n. Now define vertices u and v to be equivalent if Mu,v≠0. The equivalence classes of this relation are the connected components of the graph.
Algorithm to find Weakly Connected Component: Construct the underlying undirected graph of the given directed graph. Find all the connected components of the undirected graph. The connected components of the undirected graph will be the weakly connected components of the directed graph.
If we can reach every vertex of a component from every other vertex in that component then it is called a Strongly Connected Component (SCC). Single node is always a SCC. The graph below is a basic example of SCC, as it has four SCCs each contained in its own shape.
Apply a connected components algorithm.
For an undirected graph, just pick a node and do a breadth-first search. If there are any nodes left over after the first BFS, pick one of the left-overs and do another BFS. (You get one connected component per BFS.)
Note that directed graphs require a slightly stronger algorithm to find the strongly connected components. Kosaraju's algorithm springs to mind.
Count the number of nodes in each of the connected components from (1). Pick the largest one.
197
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
