从 Excel 导入中查找包含的边框区域

Question

我正在从具有各种表格布局的 Excel 导入大量数据。我有足够好的表格检测例程和合并单元格处理，但是在处理边框时遇到了问题。即性能。其中一些文件中的边框区域具有含义。

数据设置：
我使用 VB6 和 MSXML 直接从 Office Open XML 导入。数据从 XML 解析为单元格数据字典。这非常神奇，与在 Access 中使用 docmd.transferspreadsheet 一样快，但返回的结果要好得多。每个单元格都包含一个指向样式元素的指针，该样式元素包含一个指向定义每个边框的可见性和粗细的边框元素的指针（这也是 OpenXML 内部数据的结构方式）。

挑战：
我想做的是找到边界内封闭的每个区域，并创建该区域内的单元格列表。

我所做的：
我最初创建了一个 BFS（广度优先搜索）填充例程来查找这些区域。对于“正常”大小的电子表格来说，这非常有效且快速，但对于导入数千行来说就太慢了。一个问题是 Excel 中的边框可能存储在您正在检查的单元格中或相邻单元格中的相对边框中。没关系，我可以在导入时合并这些数据，以减少所需的检查数量。

我想做的一件事是创建一个单独的图形，使用边界作为边缘来概述单元格，并使用图形算法以这种方式查找区域，但我在弄清楚如何实现该算法时遇到了麻烦。我过去使用过 Dijkstra，并认为我可以用它做类似的事情。因此，我可以不使用端点来搜索整个图，如果我遇到一个封闭的节点，我知道我刚刚找到了一个封闭的区域，但我如何知道我找到的路线是否是最佳路线？我想我可以标记为对找到的闭合节点与前一个节点运行单独的检查，忽略该一条边。

这可以工作，但在密集图上不会有更好的性能。其他人可以建议更好的方法吗？感谢您花时间阅读本文。

Answer 1

你的问题非常复杂，但听起来好像你需要一种算法来找到图的连通分量（连通分量=全部相互连接但没有其他节点的节点集），这可以通过以下方式在线性时间内完成反复遍历。伪代码：

FindComponents(G):
    For all vertices v in G:
        Let C be a mutable empty collection
        Traverse(G, C, v)
        If C is nonempty, then it is a connected component

Traverse(G, C, v):
    If v has not been visited:
        Mark v as visited
        Add v to C
        For each neighbor w of v in G:
            Traverse(G, C, w)

Traverse 的迭代变体：

Traverse(G, C, r):
    Let S be an empty stack
    Push r onto S
    While S is not empty:
        Pop the top element v of S
        If v is not marked as visited:
            Mark v as visited
            Add v to C
            For each neighbor w of v in G:
                Push w onto S