深度遍历邻接表存储的图
时间: 2023-11-05 08:13:20 浏览: 85
深度遍历邻接表存储的图的过程如下:
1. 选择一个起始顶点 v,将其标记为已访问。
2. 对于每个与顶点 v 相邻的未访问顶点 w,递归执行步骤 1。
3. 如果不存在未访问的相邻顶点,则回溯到上一级顶点,继续执行步骤 2。
具体实现可以使用递归或栈来实现。以下是使用递归实现深度遍历的伪代码:
```
DFS(v):
标记 v 为已访问
for each w in adjacent(v) do
if w is not visited then
DFS(w)
```
其中,`adjacent(v)` 表示与顶点 v 相邻的顶点集合,可以通过邻接表来获取。`is not visited` 表示判断顶点 w 是否已被访问过。
需要注意的是,如果图不是连通的,则需要对每个连通分量都执行一次深度遍历。可以通过遍历所有顶点,对未访问的顶点执行深度遍历来实现。
相关问题
深度优先遍历邻接矩阵邻接矩阵转化为邻接链表
深度优先遍历是一种图遍历算法,它从某个顶点开始,递归地访问该顶点的所有邻接顶点,直到所有顶点都被访问为止。具体实现可以使用栈来存储访问过的节点,每次取出栈顶元素并将其未访问的邻居节点入栈,直到栈为空。
邻接矩阵是一种表示图的数据结构,它是一个二维数组,数组元素表示两个节点之间是否有边相连。邻接链表是另一种表示图的数据结构,它由若干个链表组成,每个链表表示一个节点以及与它相连的所有边。将邻接矩阵转化为邻接链表可以通过遍历邻接矩阵,将每个节点以及与它相连的边添加到对应的链表中。
具体步骤如下:
1. 创建一个包含n个链表的数组,n为图的节点数。
2. 遍历邻接矩阵的每个元素,如果元素值为1,则将其对应的节点和与之相连的节点添加到对应的链表中。
3. 重复步骤2直到遍历完整个邻接矩阵。
邻接矩阵非递归深度遍历和邻接链表非递归层次遍历
以下是邻接矩阵非递归深度遍历和邻接链表非递归层次遍历的Python实现:
邻接矩阵非递归深度遍历:
```python
def DFS_iterative(graph, start):
visited = set() # 用集合存储已访问的节点
stack = [start] # 用栈存储待访问的节点
while stack:
vertex = stack.pop() # 取出栈顶节点
if vertex not in visited:
visited.add(vertex) # 将节点标记为已访问
print(vertex, end=' ')
# 将该节点的未访问过的邻居节点入栈
stack.extend([v for v in range(len(graph[vertex])) if graph[vertex][v] and v not in visited])
# 示例
graph = [[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]]
DFS_iterative(graph, 0) # 从节点0开始深度遍历
```
输出结果为:0 2 3 1
邻接链表非递归层次遍历:
```python
from collections import deque
def BFS_iterative(graph, start):
visited = set() # 用集合存储已访问的节点
queue = deque([start]) # 用队列存储待访问的节点
while queue:
vertex = queue.popleft() # 取出队首节点
if vertex not in visited:
visited.add(vertex) # 将节点标记为已访问
print(vertex, end=' ')
# 将该节点的未访问过的邻居节点入队
queue.extend([v for v in graph[vertex] if v not in visited])
# 示例
graph = {0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2]}
BFS_iterative(graph, 0) # 从节点0开始层次遍历
```
输出结果为:0 1 2 3