Python递归实现图的生成算法

2023-04-16 00:00:00 算法生成递归

递归实现图的生成算法通常采用深度优先搜索（DFS）和广度优先搜索（BFS）两种方法。

深度优先搜索从起点开始搜索到底部（或达到终点），然后回溯到最近未访问的节点，继续搜索，直到所有节点都被访问。

广度优先搜索从起点开始，首先访问所有直接相邻的节点，然后再访问它们的相邻节点，直到所有节点都被访问。

以下为深度优先搜索的Python代码实现示例，使用字符串作为节点：

# 使用DFS生成一个图
def dfs(graph, node, visited):
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

# 测试代码
graph = {
    'p': ['i', 'd', 'a', 'n'],
    'i': ['p', 'a', 'n', 'd', 'a', 'c', 'o', 'm', '.'],
    'd': ['p', 'a', 'n', 'd', 'a', 'c', 'o', 'm', '.'],
    'a': ['p', 'i', 'd', 'n', 'a', 'c', 'o', 'm', '.'],
    'n': ['p', 'i', 'd', 'a', 'c', 'o', 'm', '.'],
    'c': ['i', 'a', 'm', 'o', 'n', 'p', 'd', '.'],
    'o': ['i', 'a', 'm', 'n', 'p', 'd', '.'],
    'm': ['a', 'c', 'o', 'n', 'i', 'd', 'p', '.'],
    '.': ['p', 'i', 'd', 'a', 'n', 'c', 'o', 'm']
}
visited = set()
dfs(graph, 'p', visited)

输出结果：

p
i
a
n
c
o
m
d

以上代码采用递归算法实现DFS。通过每次访问节点的时候，再递归访问与当前节点相邻的节点，同时记录已经访问过的节点集合，避免重复访问。

实际应用中，一般将图的邻接表表示为字典，其中每个键表示一个节点，对应的值为该节点的所有相邻节点列表。

BFS的实现方式与DFS类似，只是采用队列而不是栈来保存待访问的节点。以下为BFS的示例代码：

# 使用BFS生成一个图
def bfs(graph, start):
    visited = {start}
    queue = [start]
    while queue:
        node = queue.pop(0)
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 测试代码
graph = {
    'p': ['i', 'd', 'a', 'n'],
    'i': ['p', 'a', 'n', 'd', 'a', 'c', 'o', 'm', '.'],
    'd': ['p', 'a', 'n', 'd', 'a', 'c', 'o', 'm', '.'],
    'a': ['p', 'i', 'd', 'n', 'a', 'c', 'o', 'm', '.'],
    'n': ['p', 'i', 'd', 'a', 'c', 'o', 'm', '.'],
    'c': ['i', 'a', 'm', 'o', 'n', 'p', 'd', '.'],
    'o': ['i', 'a', 'm', 'n', 'p', 'd', '.'],
    'm': ['a', 'c', 'o', 'n', 'i', 'd', 'p', '.'],
    '.': ['p', 'i', 'd', 'a', 'n', 'c', 'o', 'm']
}
bfs(graph, 'p')

输出结果：

p
i
d
a
n
c
o
m

以上BFS算法通过队列保存待访问的节点，并使用visited记录已访问的节点，避免重复访问。从起点开始，每次访问队首节点，按照其相邻节点的顺序加入队列并标记已访问，直到队列为空。

相关文章