编程实现邻接表生成逆邻接表
时间: 2023-11-05 22:20:53 浏览: 46
好的,下面是邻接表生成逆邻接表的 Python 代码:
```python
def adjacency_list_to_inverse(adj_list):
inverse = {}
for node in adj_list:
for neighbor in adj_list[node]:
if neighbor not in inverse:
inverse[neighbor] = set()
inverse[neighbor].add(node)
return inverse
```
其中,`adj_list` 是邻接表,`inverse` 是逆邻接表,两者都是用 Python 字典实现的。对于每个节点 `node` 的邻居 `neighbor`,将 `node` 加入 `neighbor` 的邻居列表中即可。
需要注意的是,如果邻接表中存在孤立节点(即没有任何邻居的节点),则在生成逆邻接表时应该考虑将其加入逆邻接表中,并将其邻居列表初始化为空集合。
相关问题
编程实现邻接表生成逆邻接表。
假设有一个有向图,邻接表表示如下:
```python
graph = {
1: [2, 3],
2: [3, 4],
3: [4],
4: [1]
}
```
生成逆邻接表的代码如下:
```python
reverse_graph = {}
for node in graph:
for neighbor in graph[node]:
if neighbor not in reverse_graph:
reverse_graph[neighbor] = [node]
else:
reverse_graph[neighbor].append(node)
```
生成的逆邻接表如下:
```python
reverse_graph = {
2: [1],
3: [1, 2],
4: [2, 3],
1: [4]
}
```
其中,reverse_graph 中的每个 key 表示原图中的节点,对应的 value 则表示指向该节点的节点。
用C语言编程实现邻接表生成逆邻接表。
好的,以下是实现邻接表生成逆邻接表的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 邻接表的结构体
typedef struct ArcNode {
int adjvex; // 邻接顶点的位置
struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VNode {
int data; // 顶点信息
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 生成邻接表
void CreateGraph(ALGraph *G) {
int i, j, k;
ArcNode *p;
printf("请输入顶点数和边数:\n");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入顶点信息:\n");
for (i = 0; i < G->vexnum; i++) {
scanf("%d", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
}
printf("请输入边的信息(起点 终点):\n");
for (k = 0; k < G->arcnum; k++) {
scanf("%d%d", &i, &j);
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
}
}
// 生成逆邻接表
void Inverse(ALGraph *G, ALGraph *GR) {
int i;
ArcNode *p;
GR->vexnum = G->vexnum;
GR->arcnum = G->arcnum;
for (i = 0; i < G->vexnum; i++) {
GR->vertices[i].data = G->vertices[i].data;
GR->vertices[i].firstarc = NULL;
}
for (i = 0; i < G->vexnum; i++) {
p = G->vertices[i].firstarc;
while (p != NULL) {
ArcNode *q = (ArcNode *)malloc(sizeof(ArcNode));
q->adjvex = i;
q->nextarc = GR->vertices[p->adjvex].firstarc;
GR->vertices[p->adjvex].firstarc = q;
p = p->nextarc;
}
}
}
// 主函数测试逆邻接表生成
int main() {
ALGraph G, GR;
CreateGraph(&G);
Inverse(&G, &GR);
printf("邻接表:\n");
for (int i = 0; i < G.vexnum; i++) {
printf("%d -> ", G.vertices[i].data);
ArcNode *p = G.vertices[i].firstarc;
while (p != NULL) {
printf("%d -> ", G.vertices[p->adjvex].data);
p = p->nextarc;
}
printf("NULL\n");
}
printf("逆邻接表:\n");
for (int i = 0; i < GR.vexnum; i++) {
printf("%d -> ", GR.vertices[i].data);
ArcNode *p = GR.vertices[i].firstarc;
while (p != NULL) {
printf("%d -> ", GR.vertices[p->adjvex].data);
p = p->nextarc;
}
printf("NULL\n");
}
return 0;
}
```
在这个程序中,我们首先定义了邻接表的结构体,其中`VNode`表示一个顶点,`ArcNode`表示一个邻接点,`AdjList`是邻接表的类型,用于存储所有顶点的信息和它们的邻接点信息。然后,我们实现了两个函数来生成邻接表和逆邻接表。最后,在主函数中,我们使用`CreateGraph`函数生成邻接表,并使用`Inverse`函数生成逆邻接表,然后分别输出它们的信息。
注意,这里的逆邻接表是由原来的邻接表生成的,因此逆邻接表的顶点信息和边数与原来的邻接表相同。不同之处在于,对于每个顶点,逆邻接表中存储的是指向该顶点的所有边,而不是该顶点指向的所有边。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)