algorithm - 如何构建连接组件图？

Question

假设我有一个字符矩阵 (A, B, ...)。我想找到所有填充有相同字符的连续“区域”，并创建一个顶点与这些“区域”相对应的图形。当且仅当对应区域具有公共(public)边界时，图顶点才相连。

例如:

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)

我的问题是:如何在给定矩阵的情况下构建这样的图。

显然，我可以按如下方式进行；

• 运行 BFS/DFS 以找到连接的组件(“区域”)
• 再次扫描矩阵以找到每个“区域”的邻居。

有没有更简单、更有效的方法来做到这一点？

Answer 1

我认为没有更好的解决方案。
一些优化可能会将字符转换为 int。 但这不会改变大 O 表示法的努力。

有些人可能希望将信息存储在位字段中以赢得速度竞赛， 但这不值得付出努力，代码也不可读。