图的邻接表c语言实现

邻接表是一种表示图的数据结构，可以用于存储有向图或无向图。它采用链表的方式来存储每个顶点所对应的边集，因此比邻接矩阵更适用于表示稀疏图。以下是邻接表的C语言实现：

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

#define MAXVEX 100  // 最大顶点数

typedef char VertexType; // 顶点类型
typedef int EdgeType;    // 边权值类型

// 边表结构体
typedef struct EdgeNode {
    int adjvex;             // 邻接点域，存储该顶点对应的下标
    EdgeType weight;        // 存储权值，对于非网图可以不需要
    struct EdgeNode *next;  // 链域，指向下一个邻接点
} EdgeNode;

// 顶点表结构体
typedef struct VertexNode {
    VertexType data;       // 顶点信息
    EdgeNode *firstedge;   // 边表头指针
} VertexNode, AdjList[MAXVEX];

// 图结构体
typedef struct {
    AdjList adjList;       // 邻接表
    int numVertexes;       // 顶点数
    int numEdges;          // 边数
} GraphAdjList;

// 建立图的邻接表结构
void CreateALGraph(GraphAdjList *G) {
    int i, j, k;
    EdgeNode *e;
    printf("请输入顶点数和边数：\n");
    scanf("%d %d", &G->numVertexes, &G->numEdges);
    getchar();  // 把换行符取走

    printf("请输入顶点信息：\n");
    for (i = 0; i < G->numVertexes; i++) {
        scanf("%c", &G->adjList[i].data);
        G->adjList[i].firstedge = NULL;
        getchar();  // 把换行符取走
    }

    printf("请输入边的信息：\n");
    for (k = 0; k < G->numEdges; k++) {
        printf("输入边（vi,vj）上的顶点序号：\n");
        scanf("%d %d", &i, &j);

        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->next = G->adjList[i].firstedge;
        G->adjList[i].firstedge = e;

        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = i;
        e->next = G->adjList[j].firstedge;
        G->adjList[j].firstedge = e;
    }
}

// 输出邻接表存储的图
void PrintALGraph(GraphAdjList G) {
    int i;
    EdgeNode *p;
    printf("邻接表存储的图：\n");
    for (i = 0; i < G.numVertexes; i++) {
        printf("%d %c：", i, G.adjList[i].data);
        p = G.adjList[i].firstedge;
        while (p != NULL) {
            printf("%d ", p->adjvex);
            p = p->next;
        }
        printf("\n");
    }
}

int main() {
    GraphAdjList G;
    CreateALGraph(&G);
    PrintALGraph(G);
    return 0;
}