博客

Python算法之图的遍历

  • Post category:Python

下面是关于“Python算法之图的遍历”的完整攻略。

1. 图的遍历简介

图的遍历是指从图的某个顶点出发，按照一定的规则依次访问图中的所有顶点，且每个点仅被访问一次的过程。图的遍历算法是图论中的基本算法之一，常用于解决图论中一些问题，如最短路径、连通性等。

2. Python实现图的遍历

2.1 算法流程

图遍历算法主要有两种：深度优先遍历（DFS）和广度优先遍历（BFS）。它们的算法流程如下：

2.1.1 深度优先遍历（DFS）

  1. 从图的某个顶点开始遍历。
  2. 访问该顶点，并将该顶点标记为已访问。
  3. 依次遍历该顶点的所有未访问过的邻接点，对每个邻接点递归执行步骤2和步骤3。

2.1.2 广度优先遍历（BFS）

  1. 从图的某个顶点开始遍历。
  2. 访问该顶点，并将该顶点标记为已访问。
  3. 将该顶点的所有未访问过的邻接点加入队列。
  4. 从队列中取出一个顶点，访问该顶点，并将该顶点标记为已访问。
  5. 将该顶点的所有未访问过的邻接点加入队列。
  6. 重复步骤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()` 函数分别对图进行深度优先遍历和广度优先遍。最后，我们打印遍历的结果。

Tags: ,