Python算法之图的遍历

下面是关于“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技术站