深度优先遍历邻接矩阵邻接矩阵转化为邻接链表
时间: 2024-06-05 17:04:46 浏览: 22
深度优先遍历是一种图遍历算法,它从某个顶点开始,递归地访问该顶点的所有邻接顶点,直到所有顶点都被访问为止。具体实现可以使用栈来存储访问过的节点,每次取出栈顶元素并将其未访问的邻居节点入栈,直到栈为空。
邻接矩阵是一种表示图的数据结构,它是一个二维数组,数组元素表示两个节点之间是否有边相连。邻接链表是另一种表示图的数据结构,它由若干个链表组成,每个链表表示一个节点以及与它相连的所有边。将邻接矩阵转化为邻接链表可以通过遍历邻接矩阵,将每个节点以及与它相连的边添加到对应的链表中。
具体步骤如下:
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
邻接链表的深度优先遍历唯一吗
邻接链表的深度优先遍历并不唯一。深度优先遍历是一种图遍历算法,其过程中会按照某种规则访问图中的节点,其中邻接链表是一种常用的存储图结构的方式。在深度优先遍历邻接链表时,可以采用递归或者栈的方式实现。不同的实现方式可能会导致遍历的顺序不同,但是只要保证每个节点都能被访问到且不重复,就可以达到深度优先遍历的目的。
相关推荐
![](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)