写出邻接表的创建算法C语言

邻接表是一种图的表示方法，其中每个顶点对应一个链表，链表中存储与该顶点直接相邻的顶点。

邻接表的创建算法可以分为以下几个步骤：

1. 定义邻接表中的结构体和链表节点结构体：

// 邻接表中的结构体
typedef struct {
    int num_vertices;   // 图中顶点数
    int num_edges;      // 图中边数
    int *vertex;        // 存储顶点信息的数组
    struct node **adj_list; // 存储邻接表的数组
} graph;

// 链表节点结构体
typedef struct node {
    int vertex;         // 存储邻接点的编号
    struct node *next;  // 指向下一个邻接点的指针
} node;

2. 初始化邻接表，为每个顶点创建一个链表：

graph *create_graph(int num_vertices) {
    int i;
    graph *g = (graph *) malloc(sizeof(graph));
    g->num_vertices = num_vertices;
    g->num_edges = 0;
    g->vertex = (int *) malloc(num_vertices * sizeof(int));
    g->adj_list = (node **) malloc(num_vertices * sizeof(node *));

    for (i = 0; i < num_vertices; i++) {
        g->vertex[i] = i;
        g->adj_list[i] = NULL;
    }

    return g;
}

3. 添加边，将每个顶点的链表中添加相邻的顶点：

void add_edge(graph *g, int src, int dest) {
    node *new_node = (node *) malloc(sizeof(node));
    new_node->vertex = dest;
    new_node->next = g->adj_list[src];
    g->adj_list[src] = new_node;

    new_node = (node *) malloc(sizeof(node));
    new_node->vertex = src;
    new_node->next = g->adj_list[dest];
    g->adj_list[dest] = new_node;

    g->num_edges++;
}

完整代码如下：

#include <stdio.h>
#include <stdlib.h>

// 邻接表中的结构体
typedef struct {
    int num_vertices;   // 图中顶点数
    int num_edges;      // 图中边数
    int *vertex;        // 存储顶点信息的数组
    struct node **adj_list; // 存储邻接表的数组
} graph;

// 链表节点结构体
typedef struct node {
    int vertex;         // 存储邻接点的编号
    struct node *next;  // 指向下一个邻接点的指针
} node;

// 创建邻接表
graph *create_graph(int num_vertices) {
    int i;
    graph *g = (graph *) malloc(sizeof(graph));
    g->num_vertices = num_vertices;
    g->num_edges = 0;
    g->vertex = (int *) malloc(num_vertices * sizeof(int));
    g->adj_list = (node **) malloc(num_vertices * sizeof(node *));

    for (i = 0; i < num_vertices; i++) {
        g->vertex[i] = i;
        g->adj_list[i] = NULL;
    }

    return g;
}

// 添加边
void add_edge(graph *g, int src, int dest) {
    node *new_node = (node *) malloc(sizeof(node));
    new_node->vertex = dest;
    new_node->next = g->adj_list[src];
    g->adj_list[src] = new_node;

    new_node = (node *) malloc(sizeof(node));
    new_node->vertex = src;
    new_node->next = g->adj_list[dest];
    g->adj_list[dest] = new_node;

    g->num_edges++;
}

int main() {
    int i, src, dest;
    int num_vertices = 5;
    graph *g = create_graph(num_vertices);

    // 添加边
    add_edge(g, 0, 1);
    add_edge(g, 0, 4);
    add_edge(g, 1, 2);
    add_edge(g, 1, 3);
    add_edge(g, 1, 4);
    add_edge(g, 2, 3);
    add_edge(g, 3, 4);

    // 输出邻接表
    for (i = 0; i < num_vertices; i++) {
        node *temp = g->adj_list[i];
        printf("顶点 %d 的邻接表：", i);
        while (temp) {
            printf("%d ", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }

    return 0;
}