如何在隐式图中找到多个连通的组件？

我有陈述那样的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

如何在隐式图中找到多个连通的组件？

回答

相关问题