邻接矩阵存储图的深度优先遍历
时间: 2023-07-24 19:38:48 浏览: 96
邻接矩阵存储图的深度优先遍历.zip
深度优先遍历(Depth-First-Search,DFS)是一种经典的图遍历算法,邻接矩阵存储图的深度优先遍历可以通过递归实现。具体步骤如下:
1. 首先访问起始节点,并将其标记为已访问。
2. 遍历起始节点的所有邻居节点,如果邻居节点未被访问,则递归遍历该邻居节点。
3. 重复步骤2,直到所有节点都被访问过。
代码实现如下:
```python
# 定义邻接矩阵
graph = [[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0]]
# 定义访问数组
visited = [False] * len(graph)
# 定义深度优先遍历函数
def dfs(graph, visited, node):
visited[node] = True
print(node, end=' ')
for i in range(len(graph)):
if graph[node][i] == 1 and not visited[i]:
dfs(graph, visited, i)
# 调用深度优先遍历函数
dfs(graph, visited, 0)
```
输出结果为:0 1 2 3,表示深度优先遍历的顺序为节点0、节点1、节点2和节点3。
阅读全文