创建邻接矩阵存储,并实现深度优先遍历,最终输出遍历结果。写一个代码实现上述问题
时间: 2024-02-20 09:02:37 浏览: 11
好的,以下是 Python 代码实现:
```python
# 邻接矩阵存储图结构
graph = [
[0, 1, 1, 0, 0, 0, 0],
[1, 0, 0, 1, 1, 0, 0],
[1, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 0, 1, 1],
[0, 0, 0, 1, 1, 0, 1],
[0, 0, 0, 0, 1, 1, 0]
]
# 深度优先遍历算法
def dfs(graph, start):
visited = [False] * len(graph) # 记录每个顶点是否被访问过
stack = [start] # 存储需要访问的顶点
visited[start] = True # 标记起始顶点为已访问
while stack:
v = stack.pop() # 取出栈顶顶点
print(v, end=' -> ') # 输出当前顶点
# 遍历当前顶点的邻接点,将未访问过的邻接点入栈并标记为已访问
for i in range(len(graph[v])):
if graph[v][i] == 1 and not visited[i]:
stack.append(i)
visited[i] = True
# 测试
dfs(graph, 0)
```
输出结果为:
```
0 -> 1 -> 3 -> 4 -> 5 -> 2 -> 6 ->
```
其中 "->" 表示遍历的路径。