极客笔记在Python中检测2D网格中的循环的程序
在计算机科学中，网格是指一个由一些条线构成的规则空间。在二维情况中，网格被称为平面网格。在这个平面网格上，如何检测循环呢？
在这篇文章中，我们将讨论如何用多种不同的方法在Python中检测2D网格中的循环。我们将介绍以下方法：
- DFS算法
- 广度优先搜索算法
- Floyd算法
为了更好地理解这些算法，我们将使用以下示例代码：
grid = [
['#', '#', '#', '#', '#', '#'],
['#', '.', '.', '.', '.', '#'],
['#', '.', '#', '#', '.', '#'],
['#', '.', '.', '.', '.', '#'],
['#', '#', '#', '#', '#', '#']
]
这是一个简单的5×6网格。其中，’#’表示墙，’.’表示通路。我们希望能够检测出这个网格是否存在循环。接下来我们将详细介绍每种算法的特点和用法。
DFS算法
深度优先搜索（DFS）算法是一种用于图像/树遍历的算法。该算法从一个起始节点（起点）开始遍历至访问到目标节点为止。在遍历的过程中，每个节点只访问一次。这种算法适合用于找寻简单的循环路径。
我们可以用DFS来检测网格中的循环。在该算法中，每个节点都有一个状态。节点的可能状态有：未访问、在访问中、已访问。
以下是如何用DFS算法检测网格中的循环：
def hasCycleDFS(grid):
ROWS = len(grid)
COLS = len(grid[0])
visited = [[False for _ in range(COLS)] for _ in range(ROWS)]
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def DFS(r, c, parent):
if visited[r][c]:
return True
visited[r][c] = True
for dir in directions:
nr, nc = r + dir[0], c + dir[1]
if nr < 0 or nc < 0 or nr >= ROWS or nc >= COLS: # 越界
continue
if grid[nr][nc] == '#' or (nr, nc) == parent: # 遇到墙或者回溯到父节点
continue
if DFS(nr, nc, (r, c)): # 递归处理子节点
return True
return False # 没有找到循环
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == '.' and not visited[r][c]:
if DFS(r, c, (-1, -1)):
return True
return False
该算法先通过循环遍历每个节点，如果该节点是未访问过的通路，则用DFS开始遍历。在DFS的过程中，首先将该节点标记为已访问，然后遍历该节点的上下左右四个方向。如果遇到墙或者回溯到父节点，则继续往下遍历。如果遇到已经被访问过的节点，则说明存在循环。
以下是如何使用DFS来检测示例网格中的循环：
cycleDetected = hasCycleDFS(grid)
print("DFS算法检测到循环：", cycleDetected)
输出：
DFS算法检测到循环： True
我们可以看到，上述代码正确地检测到了示例网格中的循环。
广度优先搜索算法
广度优先搜索（BFS）算法是一种用于图像/树遍历的算法。该算法从一个起始节点（起点）开始遍历，先访问与该节点邻接的节点，然后访问与邻接节点相邻的节点。该算法适合用于找寻较为复杂的循环路径。
以下是如何用BFS算法检测网格中的循环：
from queue import Queue
def hasCycleBFS(grid):
ROWS = len(grid)
COLS = len(grid[0])
visited = [[False for _ in range(COLS)] for _ in range(ROWS)]
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def BFS(sr, sc):
q = Queue()
q.put((sr, sc, (-1, -1)))
while not q.empty():
r, c, parent = q.get()
if visited[r][c]:
return True
visited[r][c] = True
for dir in directions:
nr, nc = r + dir[0], c + dir[1]
if nr < 0 or nc < 0 or nr >= ROWS or nc >= COLS: # 越界
continue
if grid[nr][nc] == '#' or (nr, nc) == parent: # 遇到墙或者回溯到父节点
continue
q.put((nr, nc, (r, c))) # 将满足要求的节点加入队列
return False # 没有找到循环
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == '.' and not visited[r][c]:
if BFS(r, c):
return True
return False
该算法与DFS算法类似，先通过循环遍历每个节点，如果该节点是未访问过的通路，则用BFS开始遍历。在BFS的过程中，首先将该节点标记为已访问，然后遍历该节点的上下左右四个方向。如果遇到墙或者回溯到父节点，则继续往下遍历。将满足要求的节点加入队列，直到队列为空。
以下是如何使用BFS来检测示例网格中的循环：
cycleDetected = hasCycleBFS(grid)
print("BFS算法检测到循环：", cycleDetected)
输出：
BFS算法检测到循环： True
我们可以看到，上述代码正确地检测到了示例网格中的循环。
Floyd算法
Floyd算法是一种用于查找图像/树中最短路径的算法。该算法通过遍历所有节点来计算出每个节点到其他节点的最短路径。这种算法适合用于查找最短循环路径。
以下是如何用Floyd算法检测网格中的循环：
def hasCycleFloyd(grid):
ROWS = len(grid)
COLS = len(grid[0])
INF = 99999999
dist = [[INF for _ in range(ROWS*COLS)] for _ in range(ROWS*COLS)]
def toIndex(r, c):
return r * COLS + c
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == '#':
continue
curIndex = toIndex(r, c)
dist[curIndex][curIndex] = 0 # 距离初始化为0
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = r + dr, c + dc
if nr < 0 or nc < 0 or nr >= ROWS or nc >= COLS: # 越界
continue
if grid[nr][nc] == '#':
continue
nextIndex = toIndex(nr, nc)
dist[curIndex][nextIndex] = 1 # 相邻节点距离为1
for k in range(ROWS*COLS):
for i in range(ROWS*COLS):
for j in range(ROWS*COLS):
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == '#':
continue
index = toIndex(r, c)
if dist[index][index] < INF: # 存在从该节点到自身的最短路径
return True
return False
该算法首先将每个节点看成一个图像/树上的点。然后，将距离矩阵dist初始化为INF。对于每个节点，通过四个方向遍历相邻节点，并将相邻节点之间的距离设置为1。接下来使用Floyd算法将距离矩阵中每个节点到每个节点的最短路径计算出来。最后，检查每个节点到自身的最短路径是否小于INF。如果小于INF，则说明存在循环路径。
以下是如何使用Floyd算法来检测示例网格中的循环：
cycleDetected = hasCycleFloyd(grid)
print("Floyd算法检测到循环：", cycleDetected)
输出：
Floyd算法检测到循环： True
我们可以看到，上述代码正确地检测到了示例网格中的循环。
结论
通过本篇文章，我们了解了如何用DFS算法、BFS算法和Floyd算法来检测2D网格中的循环。这些方法基本涵盖了在Python中检测2D网格中循环的方法。当我们需要检测循环时，可以根据实际情况选择合适的算法来进行处理。