图的深度优先搜索实现
时间: 2023-12-11 19:33:11 浏览: 32
以下是使用栈实现图的深度优先搜索的Python代码示例:
```python
def dfs(graph, start):
visited = set() # 用集合记录已经访问过的节点
stack = [start] # 将起始节点加入栈中
while stack:
vertex = stack.pop() # 取出栈顶节点
if vertex not in visited:
visited.add(vertex) # 将节点标记为已访问
stack.extend(graph[vertex] - visited) # 将该节点的未访问邻居节点加入栈中
return visited
```
其中,`graph`是一个字典,表示图的邻接表,`start`是起始节点。该算法使用了栈来实现深度优先搜索,每次取出栈顶节点,将其未访问的邻居节点加入栈中,直到栈为空。
相关问题
深度优先搜索Python实现
深度优先搜索(Depth-First Search,DFS)是一种常用的图遍历算法,它通过递归的方式从起始节点开始,沿着一条路径尽可能深入地搜索,直到无法继续为止,然后回溯到上一个节点,继续搜索其他路径。下面是深度优先搜索的Python实现:
```python
# 定义图的类
class Graph:
def __init__(self):
self.graph = {}
# 添加边
def add_edge(self, u, v):
if u in self.graph:
self.graph[u].append(v)
else:
self.graph[u] = [v]
# 深度优先搜索
def dfs(self, start):
visited = set() # 记录已访问的节点
self._dfs(start, visited)
def _dfs(self, node, visited):
visited.add(node)
print(node, end=" ") # 输出当前节点
neighbors = self.graph.get(node, [])
for neighbor in neighbors:
if neighbor not in visited:
self._dfs(neighbor, visited)
# 创建图对象
g = Graph()
# 添加边
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(2, 5)
g.add_edge(3, 6)
g.add_edge(3, 7)
# 从节点1开始进行深度优先搜索
print("深度优先搜索结果:")
g.dfs(1)
```
以上代码中,首先定义了一个`Graph`类来表示图,其中`add_edge`方法用于添加边,`dfs`方法用于进行深度优先搜索。在`_dfs`方法中,使用递归的方式进行深度优先搜索,并通过一个`visited`集合来记录已访问的节点,避免重复访问。
python实现图的深度优先搜索
以下是Python实现图的深度优先搜索的示例代码:
```python
# 定义图的类
class Graph:
def __init__(self, graph_dict=None):
if graph_dict is None:
graph_dict = {}
self.__graph_dict = graph_dict
# 添加顶点
def add_vertex(self, vertex):
if vertex not in self.__graph_dict:
self.__graph_dict[vertex] = []
# 添加边
def add_edge(self, edge):
edge = set(edge)
(vertex1, vertex2) = tuple(edge)
if vertex1 in self.__graph_dict:
self.__graph_dict[vertex1].append(vertex2)
else:
self.__graph_dict[vertex1] = [vertex2]
# 深度优先搜索
def dfs(self, start_vertex, visited=None):
if visited is None:
visited = set()
visited.add(start_vertex)
print(start_vertex)
for next_vertex in self.__graph_dict[start_vertex] - visited:
self.dfs(next_vertex, visited)
return visited
# 创建图的实例
graph = Graph()
# 添加顶点和边
graph.add_vertex('A')
graph.add_vertex('B')
graph.add_vertex('C')
graph.add_vertex('D')
graph.add_vertex('E')
graph.add_edge({'A', 'B'})
graph.add_edge({'B', 'C'})
graph.add_edge({'C', 'D'})
graph.add_edge({'D', 'E'})
graph.add_edge({'E', 'A'})
# 进行深度优先搜索
graph.dfs('A')
```
输出结果为:
```
A
B
C
D
E
```