用C语言代码编写函数,构造以邻接表表示的图;
时间: 2023-05-20 20:01:45 浏览: 90
邻接表表示的图算法(示例代码)
4星 · 用户满意度95%
可以使用以下代码来构造以邻接表表示的图:
```
#include <stdio.h>
#include <stdlib.h>
#define MAXV 1000
typedef struct edgenode {
int y;
int weight;
struct edgenode *next;
} edgenode;
typedef struct {
edgenode *edges[MAXV + 1];
int degree[MAXV + 1];
int nvertices;
int nedges;
int directed;
} graph;
void initialize_graph(graph *g, int directed) {
int i;
g->nvertices = 0;
g->nedges = 0;
g->directed = directed;
for (i = 1; i <= MAXV; i++) {
g->degree[i] = 0;
g->edges[i] = NULL;
}
}
void insert_edge(graph *g, int x, int y, int weight, int directed) {
edgenode *p;
p = malloc(sizeof(edgenode));
p->weight = weight;
p->y = y;
p->next = g->edges[x];
g->edges[x] = p;
g->degree[x]++;
if (directed == 0) {
insert_edge(g, y, x, weight, 1);
} else {
g->nedges++;
}
}
void read_graph(graph *g, int directed) {
int i, m, x, y, weight;
initialize_graph(g, directed);
scanf("%d %d", &(g->nvertices), &m);
for (i = 1; i <= m; i++) {
scanf("%d %d %d", &x, &y, &weight);
insert_edge(g, x, y, weight, directed);
}
}
void print_graph(graph *g) {
int i;
edgenode *p;
for (i = 1; i <= g->nvertices; i++) {
printf("%d: ", i);
p = g->edges[i];
while (p != NULL) {
printf(" %d(%d)", p->y, p->weight);
p = p->next;
}
printf("\n");
}
}
int main() {
graph g;
read_graph(&g, 0);
print_graph(&g);
return 0;
}
```
这个代码使用了邻接表来表示图,其中 `edgenode` 结构体表示一条边,`graph` 结构体表示整个图。在 `initialize_graph` 函数中,初始化了图的各个属性;在 `insert_edge` 函数中,插入了一条边;在 `read_graph` 函数中,读入了图的信息;在 `print_graph` 函数中,输出了图的邻接表表示。
阅读全文