有向图的邻接表转化为逆邻接表,用C语言实现
时间: 2023-11-05 07:14:47 浏览: 141
好的,以下是一个简单的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` 函数中,我们先创建了一个有向图,然后打印出原始的邻接表。接着,我们创建了一个空的逆邻接表,并且遍历原始的邻接表,将每条边转化为逆邻接表中的反向边。最后,我们打印出转化后的逆邻接表。
希望能够帮到您!
阅读全文
相关推荐

















