无向图邻接表的C语言实现

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

// 邻接表中的节点
typedef struct Node {
    int vertex;             // 顶点编号
    struct Node* next;      // 指向下一个节点的指针
} Node;

// 图的邻接表
typedef struct Graph {
    int numVertices;        // 图中顶点的数量
    Node** adjLists;        // 存储邻接表的数组
} Graph;

// 创建一个新的节点
Node* createNode(int v) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 创建一个图
Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;

    // 创建存储邻接表的数组
    graph->adjLists = malloc(vertices * sizeof(Node*));

    // 初始化数组为空
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }

    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    // 添加从源顶点到目标顶点的边
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 添加从目标顶点到源顶点的边（因为是无向图）
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// 打印邻接表表示的图
void printGraph(Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        Node* temp = graph->adjLists[i];
        printf("顶点 %d 的邻接表：", i);
        while (temp) {
            printf(" -> %d", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    int vertices = 5;
    Graph* graph = createGraph(vertices);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printGraph(graph);

    return 0;
}