從Excel導入中查找包含邊界的區域

Question

我從具有各種表格佈局的Excel導入海量數據。我有足夠好的表檢測例程和合並單元格處理，但是當處理邊界時我遇到了一個問題。即性能。其中一些文件中的邊界區域有意義。

數據設置：
我使用VB6和MSXML直接從Office Open XML導入。數據從XML解析成單元數據字典。這非常奇妙，並且與在Access中使用docmd.transferspreadsheet一樣快，但返回更好的結果。每個單元格都包含一個指向樣式元素的指針，該元素包含一個指向邊界元素的指針，該邊界元素定義每個邊界的可見性和權重（這也是OpenXML內數據的結構）。

挑戰：
我想要做的是找到封閉在邊框內的每個區域，並創建該區域內的單元格列表。

我所做的：
我最初創建了一個BFS（寬度優先搜索）填充例程來查找這些區域。對於「正常」大小的電子表格，這種方法非常快速，但對於導入數千行的行爲而言速度太慢。一個問題是Excel中的邊框可能存儲在您正在檢查的單元格或相鄰單元格中的相對邊框中。沒關係，我可以在導入時合併這些數據以減少所需的檢查次數。

我想過的一件事是創建一個單獨的圖表，概述了使用邊框作爲我的邊緣的單元格，並使用圖形算法來查找區域，但我無法弄清楚如何實現算法。我過去曾使用過迪傑斯特拉，並認爲我可以做類似的事情。因此，我可以使用無端點來搜索整個圖表，如果遇到封閉節點，我知道我剛剛找到一個封閉區域，但是如何知道我找到的路線是否是最佳路線？我想我可以將其標記爲針對找到的封閉節點對前一個節點執行單獨檢查，而忽略該邊緣。

這可以工作，但在密集圖表上性能不會更好。任何人都可以提出更好的方法嗎？感謝您抽時間閱讀。

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