有向图的邻接二维矩阵再对该图进行深度优先搜索,按顺序输出所访问的顶点用函数的方法
时间: 2024-01-21 14:17:51 浏览: 45
实现有向图的深度优先搜索算法
4星 · 用户满意度95%
以下是一个基于邻接矩阵的深度优先搜索实现(使用 Python):
```python
def dfs(graph, start):
# 记录已经访问过的节点
visited = set()
# 使用栈来存储待访问的节点
stack = [start]
while stack:
# 取出栈顶元素
vertex = stack.pop()
# 如果该顶点还没有被访问,则访问它
if vertex not in visited:
print(vertex)
visited.add(vertex)
# 将该顶点的邻居节点压入栈中
for neighbor_idx, has_edge in enumerate(graph[vertex]):
if has_edge:
stack.append(neighbor_idx)
```
其中,`graph` 是邻接矩阵,`start` 是起始节点的下标。在函数中,我们使用一个 `visited` 集合来记录已经访问过的节点,使用一个栈来存储待访问的节点。在循环中,每次取出栈顶元素,如果该顶点还没有被访问,则访问它,并将其邻居节点压入栈中。这样就可以实现深度优先搜索了。
下面是一个使用示例:
```python
# 构造邻接矩阵
graph = [
[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0]
]
# 对图进行深度优先搜索
dfs(graph, 0)
```
输出结果为:
```
0
1
2
3
```
阅读全文