逆邻接表和邻接表的区别
时间: 2024-05-22 20:09:41 浏览: 20
邻接表和逆邻接表是图的两种常见存储方式。
邻接表是指通过一个顶点列表和一个相邻顶点的边列表来表示图的一种数据结构。在邻接表中,每个顶点都有一条与之相连的边链表,链表中存储的是该顶点的所有邻接点。邻接表适用于表示稀疏图。
逆邻接表是指记录每个节点有哪些节点指向它的一种数据结构。在逆邻接表中,每个顶点都有一条指向它的边链表,链表中存储的是所有指向该顶点的顶点。逆邻接表适用于需要快速查找一个点的所有入度的场合,比如计算拓扑排序和强连通分量等。
两者的区别可以简单概括为:邻接表是按照出度来存储边,而逆邻接表是按照入度来存储边。
相关问题
邻接表 逆邻接表怎么求
邻接表和逆邻接表是一种常用的图的存储结构,用于表示有向图或无向图的边关系。下是求邻接表和逆邻接表的方法:
1. 邻接表:
邻接表是一种链式存储结构,用于表示图的边关系。对于有向图,邻接表中的每个顶点都有一个链表,链表中存储了该顶点指向的其他顶点。具体求邻接表的步骤如下:
- 创建一个数组,数组的大小为图中顶点的个数。
- 遍历图中的每个顶点,对于每个顶点,创建一个链表,链表中存储该顶点指向的其他顶点。
- 遍历图中的每条边,将边的起始顶点添加到对应顶点的链表中。
2. 逆邻接表:
逆邻接表是邻接表的一种变形,用于表示有向图中每个顶点的入边关系。具体求逆邻接表的步骤如下:
- 创建一个数组,数组的大小为图中顶点的个数。
- 遍历图中的每个顶点,对于每个顶点,创建一个链表,链表中存储指向该顶点的其他顶点。
- 遍历图中的每条边,将边的终点添加到对应顶点的链表中。
下面是一个示例,展示如何求解邻接表和逆邻接表:
```python
# 邻接表
adj_list = [[] for _ in range(num_vertices)] # 创建一个空的邻接表
for edge in edges:
start, end = edge # 边的起始顶点和终点
adj_list[start].append(end) # 将终点添加到起始顶点的链表中
# 逆邻接表
reverse_adj_list = [[] for _ in range(num_vertices)] # 创建一个空的逆邻接表
for edge in edges:
start, end = edge # 边的起始顶点和终点
reverse_adj_list[end].append(start) # 将起始顶点添加到终点的链表中
```
实现邻接表生成逆邻接表
实现邻接表生成逆邻接表的方法如下:
1. 创建一个空的逆邻接表,其中包含与原始邻接表相同数量的链表。
2. 遍历原始邻接表中的每个节点,对于每个节点,遍历其出边表中的每个边,将该边的终点节点添加到逆邻接表中对应的链表中。
3. 重复步骤2,直到遍历完原始邻接表中的所有节点和边。
下面是一个Python实现的例子:
```python
# 定义邻接表
adj_list = {
'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F'],
'F': ['C']
}
# 初始化逆邻接表
reverse_adj_list = {node: [] for node in adj_list}
# 遍历邻接表,生成逆邻接表
for node in adj_list:
for neighbor in adj_list[node]:
reverse_adj_list[neighbor].append(node)
# 输出逆邻接表
for node in reverse_adj_list:
print(node, reverse_adj_list[node])
```
输出结果为:
```
B ['A']
C ['A', 'B', 'D', 'F']
D ['B', 'C']
F ['E']
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)