邻接表的深度优先遍历非递归
时间: 2023-11-20 11:57:05 浏览: 85
邻接表的深度优先遍历非递归可以使用栈来实现。具体步骤如下:
1. 创建一个栈,将起始节点入栈,并将其标记为已访问。
2. 当栈不为空时,取出栈顶元素,输出该节点的值。
3. 遍历该节点的所有邻居节点,如果邻居节点未被访问,则将其入栈并标记为已访问。
4. 重复步骤2和3,直到栈为空。
下面是C++代码实现:
```cpp
void DFS_non_recursive(Graph &g, VNode vNode) {
stack<VNode> s;
s.push(vNode);
g.vNode[vNode.index].visited = true;
while (!s.empty()) {
VNode v = s.top();
s.pop();
cout << v.data << " ";
ArcNode* p = v.firstArc;
while (p != NULL) {
if (!g.vNode[p->adjvex].visited) {
s.push(g.vNode[p->adjvex]);
g.vNode[p->adjvex].visited = true;
}
p = p->next;
}
}
}
```
相关问题
邻接表非递归深度优先遍历
邻接表非递归深度优先遍历可以使用栈来实现。具体步骤如下:
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`,如果它没有被访问过,则打印它,并将它所有未访问的邻居节点入栈。
需要注意的是,这种非递归实现的深度优先遍历并不能保证遍历顺序与递归实现相同,但它可以避免递归带来的函数调用栈溢出问题,因此在实际应用中具有一定的优势。
图的深度优先遍历非递归
图的深度优先遍历可以使用栈来实现非递归算法。
具体实现步骤如下:
1. 创建一个栈,并将起始节点入栈。
2. 创建一个 visited 集合,记录已经访问过的节点。
3. 当栈不为空时,取出栈顶节点,如果该节点没有被访问过,则将其标记为已访问,并将其所有未访问过的邻居节点入栈。
4. 重复步骤3,直到栈为空。
以下是示例 Python 代码实现:
```python
def dfs_iterative(graph, start):
stack = [start]
visited = set()
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
return visited
```
其中,graph 表示图的邻接表表示方式,start 表示起始节点。函数返回已经访问过的节点集合。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)