有向图的邻接二维矩阵再对该图进行深度优先搜索,按顺序输出所访问的顶点
时间: 2024-01-21 10:17:48 浏览: 86
实现有向图的深度优先搜索算法
4星 · 用户满意度95%
假设有向图的邻接二维矩阵为adj_matrix,可以使用深度优先搜索算法遍历该图并输出所访问的顶点的顺序。
具体实现过程如下:
1. 创建一个栈,用于存储待访问的顶点。
2. 从任意一个未被访问的顶点开始进行深度优先搜索。将该顶点标记为已访问并将其加入到栈中。
3. 从栈中取出一个顶点,输出其值,并将其所有未被访问的邻居顶点加入到栈中。
4. 重复第3步,直到栈为空。
下面是一份示例代码,其中visited数组用于记录每个顶点是否已经被访问过,dfs函数用于实现深度优先搜索:
```python
def dfs(adj_matrix, start):
stack = [start]
visited = [False] * len(adj_matrix)
visited[start] = True
while stack:
curr = stack.pop()
print(curr)
for i in range(len(adj_matrix)):
if adj_matrix[curr][i] == 1 and not visited[i]:
stack.append(i)
visited[i] = True
```
使用该函数可以对邻接二维矩阵进行深度优先搜索并输出所访问的顶点:
```python
adj_matrix = [
[0, 1, 1, 0],
[0, 0, 1, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
]
dfs(adj_matrix, 0) # 0 1 2 3
```
阅读全文