如何在隱式圖中找到多個連通的組件？

我有陳述那樣的CS問題：（「」或者（切割）或‘＃’（不切斷））如何在隱式圖中找到多個連通的組件？

鑑於紙與一些細胞切下，由字符表示的片材，我需要找出將會形成多少片。

實施例：

##..#####. 
.#.#.#.... 
###..##.#. 
..##.....# 
.###.#####

回答爲上面的例子中是5 。

一個片將形成：

.... 
.##. 
....

兩片將形成：

.... 
.#.. 
..#.

常識表明我找到一種方法，以表示與曲線圖的片材（各數字符號是頂點，並且如果它們共享一側，則連接兩個頂點）。但是，我不清楚該怎麼做。我發現有隱式圖（由返回給定頂點的所有鄰居的函數定義的圖）。像這樣的功能在這種情況下實現是微不足道的。

現在的問題是：我應該如何修改DFS算法來查找這類圖中的組件？

來源

2017-09-27 Alex Danilov

當我們遍歷從頂點的邊緣，我們使用隱式的邊緣，而不是存儲的邊緣。
將頂點表示爲它們的二維座標(row, col)是有用的。

的僞碼如下：

dRow = [-1, 0, +1, 0] 
dCol = [ 0, -1, 0, +1] 
...later, when we want to move from vertex (row, col)... 
for dir in [0..4): 
    nRow = row + dRow[dir] 
    nCol = col + dCol[dir] 
    if vertex (nRow, nCol) is in rectangle bounds: 
     try to move from vertex (row, col) to vertex (nRow, nCol)

這是在一個典型的DFS的實現將有一個像一個循環的地方：

for each vertex u in {neighbors of vertex v}: 
    try to move from vertex v to vertex u

來源

2017-09-27 10:06:17 Gassa

如何在隱式圖中找到多個連通的組件？

回答

相關問題