邻接表非递归深度优先遍历
时间: 2023-07-18 18:06:18 浏览: 93
利用邻接表实现图的深度优先遍历
邻接表非递归深度优先遍历可以使用栈来实现。具体步骤如下:
1. 将起始节点入栈。
2. 如果栈非空,则取出栈顶元素,将其标记为已访问,并将其所有未访问的邻居节点入栈。
3. 重复步骤2,直到栈为空。
下面是一个示例代码实现:
```python
def dfs_iterative(adj_list, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node)
for neighbor in adj_list[node]:
if neighbor not in visited:
stack.append(neighbor)
```
其中,`adj_list` 是邻接表,`start` 是起始节点。在代码中,我们使用了一个集合 `visited` 来记录已经访问过的节点,使用一个栈 `stack` 存储待访问的节点。在每次循环中,我们取出栈顶元素 `node`,如果它没有被访问过,则打印它,并将它所有未访问的邻居节点入栈。
需要注意的是,这种非递归实现的深度优先遍历并不能保证遍历顺序与递归实现相同,但它可以避免递归带来的函数调用栈溢出问题,因此在实际应用中具有一定的优势。
阅读全文