用C语言链表写一个有向图。有向图中包含n个顶点,编号为0至n-1。 输入格式: 输入第一行为两个正整数n和e,分别表示图的顶点数和边数,其中n不超过20000,e不超过20000。接下来e行表示每条边...
时间: 2024-03-26 14:39:20 浏览: 155
以下是使用C语言链表实现有向图的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int vertex;
struct node *next;
} Node;
int main() {
int n, e;
scanf("%d %d", &n, &e);
Node *graph[n];
for (int i = 0; i < n; i++) {
graph[i] = NULL;
}
for (int i = 0; i < e; i++) {
int u, v;
scanf("%d %d", &u, &v);
Node *new_node = (Node*) malloc(sizeof(Node));
new_node->vertex = v;
new_node->next = graph[u];
graph[u] = new_node;
}
// Print adjacency list
for (int i = 0; i < n; i++) {
printf("Vertex %d: ", i);
Node *temp = graph[i];
while (temp != NULL) {
printf("%d ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
return 0;
}
```
在这个代码中,我们首先定义了一个 `Node` 结构体,它包含了一个 `vertex` 成员变量表示节点编号和一个 `next` 成员变量表示下一个节点的指针。
然后我们读入顶点数 `n` 和边数 `e`,并定义一个 `graph` 数组,其中每个元素是一个链表的头节点。我们将所有链表的头节点初始化为 `NULL`。
接下来,我们读入每条边 `(u, v)`,并将节点 `v` 添加到节点 `u` 的链表头。具体地,我们创建一个新节点 `new_node`,将 `new_node->vertex` 设置为 `v`,将 `new_node->next` 设置为 `graph[u]`,然后将 `graph[u]` 指向 `new_node`。
最后,我们遍历整个 `graph` 数组,对于每个节点 `i`,输出它的链表内容。
注意,这里的实现是使用邻接表来存储有向图。如果需要使用邻接矩阵来存储,则可以用一个二维数组 `int matrix[n][n]` 来表示,其中 `matrix[i][j]` 表示从节点 `i` 到节点 `j` 是否存在边。
阅读全文