怎么实现有向图邻接表存储结构
时间: 2023-11-05 16:08:31 浏览: 48
有向图邻接表是一种常用的存储有向图的数据结构,可以使用链表来实现。具体实现步骤如下:
1. 定义结构体表示图中的每个顶点,包括顶点编号、与该顶点相邻的顶点列表等信息。
```c
typedef struct Node {
int val; // 顶点编号
struct Node* next; // 指向下一个相邻顶点的指针
} Node;
typedef struct Vertex {
int val; // 顶点编号
Node* head; // 指向与该顶点相邻的第一个顶点的指针
} Vertex;
```
2. 定义一个数组来存储所有顶点,并初始化每个顶点的相邻顶点列表为空。
```c
Vertex graph[MAX_SIZE]; // 存储所有顶点的数组
int vertex_count = 0; // 顶点数量
for (int i = 0; i < MAX_SIZE; i++) {
graph[i].val = i; // 初始化每个顶点的编号
graph[i].head = NULL; // 初始化每个顶点的相邻顶点列表为空
}
```
3. 对于每条有向边 (u, v),在 u 的相邻顶点列表中添加一个指向 v 的指针。
```c
void add_edge(int u, int v) {
Node* node = (Node*) malloc(sizeof(Node));
node->val = v;
node->next = graph[u].head;
graph[u].head = node;
}
```
4. 根据需要遍历图时,可以通过遍历每个顶点的相邻顶点列表来访问相邻顶点。
```c
for (Node* node = graph[u].head; node != NULL; node = node->next) {
int v = node->val; // 访问相邻顶点 v
}
```
上述代码是一个简单的有向图邻接表存储结构的实现示例,开发者可以根据实际需求进行修改和优化。