图的链接矩阵深度遍历和广度遍历
时间: 2024-06-13 20:05:56 浏览: 15
邻接矩阵是一种表示图的方法,其中矩阵的行和列分别表示图中的节点,矩阵中的值表示两个节点之间是否有边。深度优先遍历和广度优先遍历是两种常见的图遍历算法。
深度优先遍历(DFS)是一种递归算法,它从图的某个节点开始遍历,沿着一条路径直到不能再继续为止,然后回溯到前一个节点,继续遍历下一条路径,直到遍历完整个图。下面是使用邻接矩阵表示法进行深度优先遍历的Python代码:
```python
def dfs(graph, start, visited):
visited[start] = True
print(start, end=' ')
for i in range(len(graph)):
if graph[start][i] == 1 and not visited[i]:
dfs(graph, i, visited)
# 示例
graph = [[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0]]
visited = [False] * len(graph)
dfs(graph, 0, visited)
```
广度优先遍历(BFS)是一种迭代算法,它从图的某个节点开始遍历,先访问它的所有邻居节点,然后再依次访问邻居节点的邻居节点,直到遍历完整个图。下面是使用邻接矩阵表示法进行广度优先遍历的Python代码:
```python
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
node = queue.popleft()
print(node, end=' ')
for i in range(len(graph)):
if graph[node][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
# 示例
graph = [[0,1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0]]
visited = [False] * len(graph)
bfs(graph, 0, visited)
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)