[Math] How to find the largest connected component of an undirected graph using its incidence matrix

algorithmsgraph theory

Usually, finding the largest connected component of a graph requires a DFS/BFS over all vertices to find the components, and then selecting the largest one found.

Suppose I only have an incidence matrix as a representation of a graph. Is there another algorithm (faster perhaps) to find the largest component by taking advantage of the structure of the incidence matrix?

Best Answer

There could be an algorithm that would be useful for a sparse graph that takes $O(|E|)$ time. In that case you would want to just have a list of edges and would not want to have to scan an adjacency matrix. This would be the fastest possible in order to be certain you've found all components.

Related Solutions

[Math] the expected size of the largest strongly connected component of a graph

Much is known about the behavior of the (undirected) random graph $G(n, p)$ in the Erdős–Rényi model, including the following:

$\langle$Begin quote$\rangle$

If $np < 1$, then a graph in $G(n, p)$ will almost surely have no connected components of size larger than $O(\log(n))$.

If $np = 1$, then a graph in $G(n, p)$ will almost surely have a largest component whose size is of order $n^{2/3}$.

If $np → c > 1$, where $c$ is a constant, then a graph in $G(n, p)$ will almost surely have a unique giant component containing a positive fraction of the vertices. No other component will contain more than $O(\log(n))$ vertices.

If $p<\tfrac{(1-\epsilon)\ln n}{n}$, then a graph in $G(n, p)$ will almost surely contain isolated vertices, and thus be disconnected.

If $p>\tfrac{(1+\epsilon) \ln n}{n}$, then a graph in $G(n, p)$ will almost surely be connected.

Thus $\tfrac{\ln n}{n}$ is a sharp threshold for the connectedness of $G(n, p)$.

$\langle$End quote$\rangle$

The directed case is studied here.

[Math] How to use BFS or DFS to determine the connectivity in a non-connected graph

Your solution looks good to me!

I have one suggestion if you consider directed graphs. Consider the graph:

A -> B -> C
D -> F

Let's say your algorithm starts arbitrarily at node B. It will traverse the graph through B and C and mark them as connected components - but it won't catch A!

A simple way to solve this problem is to allow the DFS to traverse the graph going both forwards and backwards, as though the graph was non-directed.

This is another way to solve it: Your algorithm produces sets of connected components. Let's say, as above, that the algorithm starts at B and produces the set {B, C}. Then, let's say that the algorithm arbitrarily selects A as its next starting point. When it traverses the graph to B, it should union the new set of connected components {A} with the already-existing set {B, C} instead of simply skipping node B.

In general, if you encounter a node that's already part of a group of connected components during a DFS, mark the set of connected components that the node is in and then skip the node. Then, when you've finished traversing as many nodes as possible without retracing paths found by previous DFS's, union all of the marked sets and the set produced by the most recent DFS into one set of connected components and discard the unioned sets.

Best Answer

Related Solutions

[Math] the expected size of the largest strongly connected component of a graph

[Math] How to use BFS or DFS to determine the connectivity in a non-connected graph

Related Question