邻接表转化为逆邻接表
时间: 2023-11-05 11:20:40 浏览: 35
将邻接表转化为逆邻接表的过程如下:
1. 创建一个空的逆邻接表,用于存储转化后的数据结构。
2. 遍历邻接表中的每个节点,对于每个节点,进行以下操作:
- 获取当前节点的邻居节点列表。
- 遍历邻居节点列表,对于每个邻居节点,进行以下操作:
- 在逆邻接表中查找是否存在该邻居节点的条目。
- 如果该邻居节点的条目不存在,则创建一个新的条目,并将当前节点添加到邻居节点的列表中。
- 如果该邻居节点的条目已存在,则直接将当前节点添加到邻居节点的列表中。
3. 返回转化后的逆邻接表。
这样,通过上述步骤,可以将邻接表转化为逆邻接表。
相关问题
邻接表转化为逆邻接表c代码
下面是将邻接表转化为逆邻接表的C代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 邻接表节点
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// 邻接表
struct AdjList {
struct AdjListNode* head;
};
// 图
struct Graph {
int num_vertices;
struct AdjList* adj_list;
};
// 创建邻接表节点
struct AdjListNode* create_adj_list_node(int dest) {
struct AdjListNode* new_node = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
new_node->dest = dest;
new_node->next = NULL;
return new_node;
}
// 添加边
void add_edge(struct Graph* graph, int src, int dest) {
struct AdjListNode* new_node = create_adj_list_node(dest);
new_node->next = graph->adj_list[src].head;
graph->adj_list[src].head = new_node;
}
// 创建图
struct Graph* create_graph(int num_vertices) {
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->num_vertices = num_vertices;
graph->adj_list = (struct AdjList*) malloc(num_vertices * sizeof(struct AdjList));
for (int i = 0; i < num_vertices; i++) {
graph->adj_list[i].head = NULL;
}
return graph;
}
// 逆邻接表节点
struct InvAdjListNode {
int src;
struct InvAdjListNode* next;
};
// 逆邻接表
struct InvAdjList {
struct InvAdjListNode* head;
};
// 创建逆邻接表节点
struct InvAdjListNode* create_invadj_list_node(int src) {
struct InvAdjListNode* new_node = (struct InvAdjListNode*) malloc(sizeof(struct InvAdjListNode));
new_node->src = src;
new_node->next = NULL;
return new_node;
}
// 将邻接表转化为逆邻接表
struct InvAdjList* convert_adjlist_to_invadjlist(struct Graph* graph) {
struct InvAdjList* invadj_list = (struct InvAdjList*) malloc(graph->num_vertices * sizeof(struct InvAdjList));
// 初始化逆邻接表
for (int i = 0; i < graph->num_vertices; i++) {
invadj_list[i].head = NULL;
}
// 遍历邻接表中的每个顶点和相邻顶点
for (int i = 0; i < graph->num_vertices; i++) {
struct AdjListNode* curr_node = graph->adj_list[i].head;
while (curr_node != NULL) {
// 添加该顶点到相邻顶点的逆邻接表中
struct InvAdjListNode* new_node = create_invadj_list_node(i);
new_node->next = invadj_list[curr_node->dest].head;
invadj_list[curr_node->dest].head = new_node;
curr_node = curr_node->next;
}
}
return invadj_list;
}
// 打印逆邻接表
void print_invadjlist(struct InvAdjList* invadj_list, int num_vertices) {
for (int i = 0; i < num_vertices; i++) {
printf("顶点 %d 被以下顶点相邻:", i);
struct InvAdjListNode* curr_node = invadj_list[i].head;
while (curr_node != NULL) {
printf("%d ", curr_node->src);
curr_node = curr_node->next;
}
printf("\n");
}
}
int main() {
// 创建图
struct Graph* graph = create_graph(4);
add_edge(graph, 0, 1);
add_edge(graph, 0, 2);
add_edge(graph, 1, 2);
add_edge(graph, 2, 0);
add_edge(graph, 2, 3);
add_edge(graph, 3, 3);
// 将邻接表转化为逆邻接表
struct InvAdjList* invadj_list = convert_adjlist_to_invadjlist(graph);
// 打印逆邻接表
print_invadjlist(invadj_list, graph->num_vertices);
return 0;
}
```
这个代码实现了邻接表和逆邻接表的创建以及将邻接表转化为逆邻接表的操作。最后将逆邻接表打印出来,以验证转化是否正确。
有向图的邻接表转化为逆邻接表,用C语言实现
好的,以下是一个简单的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义邻接表中的节点
typedef struct Node {
int val;
struct Node* next;
} Node;
// 定义邻接表
typedef struct AdjList {
int size;
Node** head;
} AdjList;
// 定义有向图
typedef struct Graph {
int numVertices;
AdjList* adjList;
} Graph;
// 创建节点
Node* createNode(int val) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 添加边
void addEdge(Graph* graph, int src, int dest) {
// 添加正向边
Node* newNode = createNode(dest);
newNode->next = graph->adjList[src].head;
graph->adjList[src].head = newNode;
graph->adjList[src].size++;
// 添加反向边
newNode = createNode(src);
newNode->next = graph->adjList[dest].head;
graph->adjList[dest].head = newNode;
graph->adjList[dest].size++;
}
// 创建有向图
Graph* createGraph(int numVertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->numVertices = numVertices;
// 创建邻接表
graph->adjList = (AdjList*)malloc(numVertices * sizeof(AdjList));
for (int i = 0; i < numVertices; i++) {
graph->adjList[i].size = 0;
graph->adjList[i].head = NULL;
}
return graph;
}
// 打印邻接表
void printGraph(Graph* graph) {
for (int i = 0; i < graph->numVertices; i++) {
Node* currentNode = graph->adjList[i].head;
printf("节点 %d 的邻居: ", i);
while (currentNode != NULL) {
printf("%d ", currentNode->val);
currentNode = currentNode->next;
}
printf("\n");
}
}
int main() {
// 创建有向图
Graph* graph = createGraph(4);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 0);
addEdge(graph, 2, 3);
addEdge(graph, 3, 3);
// 打印邻接表
printf("原始邻接表:\n");
printGraph(graph);
// 转化为逆邻接表
Graph* inverseGraph = createGraph(4);
for (int i = 0; i < graph->numVertices; i++) {
Node* currentNode = graph->adjList[i].head;
while (currentNode != NULL) {
addEdge(inverseGraph, currentNode->val, i);
currentNode = currentNode->next;
}
}
// 打印逆邻接表
printf("逆邻接表:\n");
printGraph(inverseGraph);
return 0;
}
```
该代码中,我们首先定义了邻接表的节点结构体和邻接表结构体。然后定义了有向图的结构体和一些操作函数,包括创建节点、添加边、创建有向图、打印邻接表等。
在 `main` 函数中,我们先创建了一个有向图,然后打印出原始的邻接表。接着,我们创建了一个空的逆邻接表,并且遍历原始的邻接表,将每条边转化为逆邻接表中的反向边。最后,我们打印出转化后的逆邻接表。
希望能够帮到您!
相关推荐
![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)