下面是关于“Python算法之图的遍历”的完整攻略。
1. 图的遍历简介
图的遍历是指从图的某个顶点出发,按照一定的规则依访问图中的顶点,且每个点仅被访问一次的过程。图的遍历算法是图论中的基本算法一,常用于解决图论中一些问题,如最短路径、连通性等。
2 Python实现图的遍历
2.1 算法流程
图遍历算法主要有两种:深度优先遍历(DFS和广度优先遍历(BFS)。它们的算法流程如下:
2.1.1 深度优先遍历(DFS)
- 从图的某个顶点开始遍历。
- 访问该顶点该顶点标记为已访问。
- 依次遍历该顶点的未访问过的邻接点,对每个邻接点归执行步骤2和步骤3。
2.1.2 广度优先遍历(BFS)
- 从图的某个顶点开始遍历。
- 访问该顶点,并将该顶点标记为已访问。
- 将该顶点的所有未访问过的邻接点加入队列。
- 从队列中取出一个顶点,访问该顶点,并将该顶点标记为已访问。
- 将该顶点的所有未访问过的邻接点加入队列。
- 重复步骤4和步骤5,直到队列为空。
2.2 Python实现
在Python中,我们可以使用以下代码实现图的遍历算法:
from collections import deque
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adj_list = {v: [] for v in vertices}
def add_edge(self, u, v):
self.adj_list[u].append(v)
self.adj[v].append(u)
def dfs(self, start):
visited = {v: False for v in self.vertices}
self._dfs(start, visited)
def _dfs(self, v, visited):
visited[v] = True
print(v, end=" ")
for u in self.adj_list[v]:
if not visited[u]:
self._dfs(u, visited)
def bfs(self, start):
visited = {v: False for v in self.vertices}
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end=" ")
for u in self.adj_list[v]:
if not visited[u]:
visited[u] = True
queue.append(u)
在这个代码中,我们定义了一个 Graph
类,用于表示一个无向图。我们首先在 __init__()
函数中初始化图的顶点和邻接表。然后,定义了一个 add_edge()
函数,用于添加边。在 dfs()
函数中,我们使用深度优先遍历算法遍历图。在 _dfs()
函数中,我们首先将当前顶点标记为已访问,并打该点。然后,遍历该顶点的所有未访问过的邻接点,并递归执行 _dfs()
函数。在 bfs()
函数中,我们使用广度优先遍历算法遍历图。我们首先将起始顶点加入队列,并标记为已访问。然后,从队列中取出一个顶点,并打印该顶点。接着,遍历该顶点的所有未访问过的邻接点,并将们加入队列中。最后,重复执行步骤4和步骤5,直到队列为空。
2.3 示例说明
下面是一个使用图的遍历算法的示例:
vertices = ["A", "B", "C", "D", "E", "F"]
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("B", "E"), ("C", "F"), ("E", "F")]
graph = Graph(vertices)
for u, v in edges:
graph.add_edge(u, v)
print("DFS:")
graph.dfs("A")
print("\nBFS:")
graph.bfs("A")
在这个示例中,我们首先定义了一个无向图,并添加边。然后我们创建一个 Graph
对象,并使用 dfs()
函数和 bfs()
函数分别对图进行深度优先遍历和广度优先遍历。最后,我们打印遍历的结果。
下面是另一个使用图的遍历算法的示例:
vertices = ["A "B", "C", "D", "E", "F"]
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("B", "E"), ("C", "F"), ("E", "F")]
graph = Graph(vertices)
for u, v in edges:
graph.add_edge(u, v)
print("DFS:")
graph.dfs("D")
print("\nBFS:")
graph.bfs("D")
在这个示例中,我们首先定义了一个无向图,并添加了边。然后,我们创建一个 Graph
对象,并使用 dfs()
函数和bfs 函数分别对图进行深度优先历和广度优先遍。最后,我们打印遍历的结果。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Python算法之图的遍历 - Python技术站