和邻接表相比,逆邻接表的主要作用
时间: 2023-11-24 08:51:07 浏览: 37
逆邻接表是邻接表的一种变形,它存储的是指向每个顶点的边的集合,即与邻接表存储的边的方向相反。逆邻接表的主要作用是用于快速查找每个顶点的入度,因为对于一个有向图,入度表示指向该顶点的边的数量,而邻接表只能快速查找每个顶点的出度,即从该顶点出发的边的数量。使用逆邻接表可以避免在邻接表中遍历整个图来查找每个顶点的入度,从而提高了效率。
下面是一个使用逆邻接表查找每个顶点入度的示例代码:
```python
定义一个有向图的逆邻接表
graph = {
'A': set(),
'B': {'A', 'C'},
'C': {'A'},
'D': {'B', 'C'},
'E': {'D'},
'F': {'D', 'E'}
}
# 初始化每个顶点的入度为0
in_degree = {v: 0 for v in graph}
# 遍历逆邻接表,统计每个顶点的入度
for v in graph:
for u in graph[v]:
in_degree[u] += 1
# 输出每个顶点的入度
for v in in_degree:
print(f'{v}的入度为{in_degree[v]}')
```
相关问题
用邻接表表示法编写有向图的邻接表和逆邻接表,并输出邻接表和逆邻接表。再用邻接表表示法编写无向图的邻接表和逆邻接表,并输出邻接表和逆邻接表。
邻接表是图的一种存储方式,它利用数组和链表相结合的方式来表示图。邻接表存储有向图和无向图的方式略有不同。
首先我们来看有向图的邻接表。假设有n个顶点和m条边,我们可以用一个数组a来存储所有的边,a[i]表示顶点i的出边集合,每个出边用一个结构体存储,包含指向的顶点和边的权值等信息。具体实现代码如下:
```
const int N = 100010;
struct Edge {
int v, w; // v表示指向的顶点编号,w表示边的权值
};
Edge a[N]; // 存储所有的边
int h[N], e[N], ne[N], idx; // h表示邻接表头,e表示边集合,ne表示指向下一条边的指针,idx表示当前边的编号
void add(int a, int b, int c) { // 添加一条从a到b权值为c的边
e[idx] = b, ne[idx] = h[a], h[a] = idx ++; // 将边插入邻接表中
}
int main() {
int n, m;
cin >> n >> m;
memset(h, -1, sizeof h); // 初始化邻接表头为-1
for (int i = 0; i < m; i ++ ) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c); // 添加一条从a到b权值为c的边
}
for (int i = 1; i <= n; i ++ ) { // 输出邻接表
printf("Vertex %d: ", i);
for (int j = h[i]; j != -1; j = ne[j]) {
printf("-> %d(w=%d) ", e[j], a[j].w);
}
puts("");
}
return 0;
}
```
接下来我们再看有向图的逆邻接表。逆邻接表存储每个顶点的入边集合。具体实现代码如下:
```
const int N = 100010;
struct Edge {
int v, w; // v表示指向的顶点编号,w表示边的权值
};
Edge a[N]; // 存储所有的边
int rh[N], re[N], rne[N], ridx; // rh表示逆邻接表头,re表示边集合,rne表示指向下一条边的指针,ridx表示当前边的编号
void add(int a, int b, int c) { // 添加一条从a到b权值为c的边
re[ridx] = b, rne[ridx] = rh[a], rh[a] = ridx ++; // 将边插入逆邻接表中
}
int main() {
int n, m;
cin >> n >> m;
memset(rh, -1, sizeof rh); // 初始化逆邻接表头为-1
for (int i = 0; i < m; i ++ ) {
int a, b, c;
cin >> a >> b >> c;
add(b, a, c); // 添加一条从a到b权值为c的边
}
for (int i = 1; i <= n; i ++ ) { // 输出逆邻接表
printf("Vertex %d: ", i);
for (int j = rh[i]; j != -1; j = rne[j]) {
printf("<- %d(w=%d) ", re[j], a[j].w);
}
puts("");
}
return 0;
}
```
接下来我们再来看无向图的邻接表。和有向图相比,无向图的邻接表要多存储一份反向边。具体实现代码如下:
```
const int N = 100010;
struct Edge {
int v, w; // v表示指向的顶点编号,w表示边的权值
};
Edge a[N]; // 存储所有的边
int h[N], e[N], ne[N], idx; // h表示邻接表头,e表示边集合,ne表示指向下一条边的指针,idx表示当前边的编号
void add(int a, int b, int c) { // 添加一条从a到b权值为c的边
e[idx] = b, ne[idx] = h[a], h[a] = idx ++; // 将正向边插入邻接表中
e[idx] = a, ne[idx] = h[b], h[b] = idx ++; // 将反向边插入邻接表中
}
int main() {
int n, m;
cin >> n >> m;
memset(h, -1, sizeof h); // 初始化邻接表头为-1
for (int i = 0; i < m; i ++ ) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c); // 添加一条从a到b权值为c的边
}
for (int i = 1; i <= n; i ++ ) { // 输出邻接表
printf("Vertex %d: ", i);
for (int j = h[i]; j != -1; j = ne[j]) {
printf("-> %d(w=%d) ", e[j], a[j].w);
}
puts("");
}
return 0;
}
```
最后我们再看无向图的逆邻接表。和有向图相比,无向图的逆邻接表也要多存储一份反向边。具体实现代码如下:
```
const int N = 100010;
struct Edge {
int v, w; // v表示指向的顶点编号,w表示边的权值
};
Edge a[N]; // 存储所有的边
int rh[N], re[N], rne[N], ridx; // rh表示逆邻接表头,re表示边集合,rne表示指向下一条边的指针,ridx表示当前边的编号
void add(int a, int b, int c) { // 添加一条从a到b权值为c的边
re[ridx] = b, rne[ridx] = rh[a], rh[a] = ridx ++; // 将正向边插入逆邻接表中
re[ridx] = a, rne[ridx] = rh[b], rh[b] = ridx ++; // 将反向边插入逆邻接表中
}
int main() {
int n, m;
cin >> n >> m;
memset(rh, -1, sizeof rh); // 初始化逆邻接表头为-1
for (int i = 0; i < m; i ++ ) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c); // 添加一条从a到b权值为c的边
}
for (int i = 1; i <= n; i ++ ) { // 输出逆邻接表
printf("Vertex %d: ", i);
for (int j = rh[i]; j != -1; j = rne[j]) {
printf("<- %d(w=%d) ", re[j], a[j].w);
}
puts("");
}
return 0;
}
```
最小生成树Prim算法(邻接矩阵和邻接表)
Prim算法是一种用于寻找加权无向连通图的最小生成树的算法。它的基本思想是,从一个顶点出发,每次将一个未被访问的且与当前已被访问的点集相连的权值最小的边加入生成树中,直到所有的顶点都被访问。
Prim算法有两种实现方式:邻接矩阵和邻接表。
邻接矩阵实现:
首先,我们需要用一个二维数组来表示图的邻接矩阵。其中,第i行第j列的元素表示顶点i和顶点j之间的边的权值。如果两个顶点之间没有边,则相应的元素为无穷大。我们还需要用一个一维数组来记录每个顶点是否已被访问,以及每个顶点的最小权值边。
算法流程如下:
1.初始化:将起始顶点加入已被访问的点集中,将该点的所有邻接边的权值存入最小权值数组中,将该点的最小权值设置为0。
2.重复以下步骤,直到所有顶点都被访问:
a.从未访问的点集中选择一个顶点u,使得u的最小权值最小。
b.将u加入已访问的点集中。
c.对于u的每个邻接顶点v,如果v未被访问且u到v的边的权值小于v的最小权值,则更新v的最小权值为u到v的边的权值。
邻接表实现:
与邻接矩阵相比,邻接表的实现方式更加节省空间。我们可以用一个数组来表示所有的顶点,每个顶点对应一个链表,存储该顶点与其他顶点之间的边及其权值。
算法流程如下:
1.初始化:将起始顶点加入已被访问的点集中,将该点的所有邻接边的权值存入最小堆中。
2.重复以下步骤,直到所有顶点都被访问:
a.从最小堆中取出一个权值最小的边。
b.如果该边的两个顶点都已被访问,则舍弃该边。
c.如果该边的一个顶点已被访问,则将另一个顶点加入已访问的点集中,并将该点的所有邻接边的权值存入最小堆中。
d.如果该边的两个顶点都未被访问,则将任意一个顶点加入已访问的点集中,并将该点的所有邻接边的权值存入最小堆中。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)