How to build a graph of connected components?

Question

Suppose I have a matrix of chars (A, B, ...). I would like to find all contiguous "areas" filled with the same char and create a graph with vertices corresponding to those "areas". The graph vertices are connected if and only if the correspondent areas have a common border.

For example:

input matrix:
A A B C
A B B B
C C D D

areas:
1(A), 2(B), 3(C), 4(C), 5(D)

output graph (adjacency list):

1(A) - 2(B), 4(C)
2(B) - 1(A), 3(C), 4(C), 5(D)
3(C) - 2(B)
4(C) - 1(A), 2(B), 5(D)
5(D) - 2(B), 4(C)

My question is: how to build such a graph given a matrix.

Obviously, I can do it as follows;

run BFS/DFS to find the connected components ("areas")
scan the matrix again to find the neighbors for each "area".

Is there any simpler and more efficient way to do that?

AlexWien AlexWien · Accepted Answer · 2012-11-30T20:44:32

I dont think that there is a much better solution.
Some optimisation would be possible converting characters to int. But this would not change the effort in big O Notation.

Some might want to to store the info in bit fields to win a speed contest, but this is not worth the effort, neither the code would be readable.

How to build a graph of connected components?

1 Answers