图的建立和广度优先搜索和深度优先搜素遍历完整代码
时间: 2024-04-30 11:17:55 浏览: 16
先来看看图的建立。以下是一个有向图的建立过程:
```python
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
```
这里使用了一个 defaultdict 来存储图的信息,每个节点对应一个列表,存储与该节点相邻的节点。
接下来是广度优先搜索的代码:
```python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
print(vertex)
queue.extend(graph[vertex] - visited)
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
bfs(g.graph, 2)
```
在广度优先搜索中,我们使用了一个队列来存储待处理的节点。我们从起始节点开始,将其加入队列中,然后遍历队列中的每个节点,将其相邻的节点加入队列中。在遍历过程中,我们还需要使用一个 visited 集合来记录已经遍历过的节点,避免重复遍历。
最后是深度优先搜索的代码:
```python
def dfs(graph, start):
visited = set()
def dfs_helper(vertex):
visited.add(vertex)
print(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs_helper(neighbor)
dfs_helper(start)
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
dfs(g.graph, 2)
```
在深度优先搜索中,我们使用了递归来遍历每个节点。我们从起始节点开始,遍历其相邻的节点,对于每个相邻的节点,如果它没有被访问过,就递归调用 dfs_helper 函数。在遍历过程中,我们同样需要使用一个 visited 集合来记录已经遍历过的节点,避免重复遍历。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)