C语言图的邻接表存储

1.邻接表法

邻接表有两个部分：顶点节点、边节点

（1）顶点节点

建立一个顺序表，用来存储图中所有顶点。每个顶点为表中一个元素，每个元素包含：数据域和指针域（firstedge）

数据域：存储节点信息，如节点名称

指针域：指向顶点的第一个邻接点

存储结构如下：

#define MAX_VERTEX_NUM 100  /* 图中最大节点数 */
typedef struct vnode        /* 顶点结构 */
{
    VertexType vex;         /* 存储顶点名 */
    EdgeNode * firstedge;   /* 边表头指针，指向顶点第一个邻接点 */
}VertexNode, AdjList[MAX_VERTEX_NUM];

（2）边节点

为顺序表中每个顶点建立一个单链表，单链表中每个节点都是顶点的临界点。每个边节点包含：数据域和指针域（next）

数据域：存储节点信息，如节点名称

指针域：指向顶点的下一个邻接点

有时还会增加一个域，用来存储边上的信息，如权值（此项不需要时可以不加）

存储结构如下：

typedef char VertexType;
typedef struct node         /* 边表节点 */
{
    VertexType adjvex;      /* 与顶点相连的邻接点下标(adjoin：邻接) */
    struct node * next;     /* 指向顶点的下一个邻接点 */
}EdgeNode;

（3）图示

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

#define MAX_VERTEX_NUM 100  /* 图中最大节点数 */
typedef char VertexType;
typedef struct node         /* 边表节点 */
{
    VertexType adjvex;      /* 与顶点相连的邻接点下标(adjoin：邻接) */
    struct node * next;     /* 指向顶点的下一个邻接点 */
}EdgeNode;

typedef struct vnode        /* 顶点结构 */
{
    VertexType vex;         /* 存储顶点名 */
    EdgeNode * firstedge;   /* 边表头指针，指向顶点第一个邻接点 */
}VertexNode, AdjList[MAX_VERTEX_NUM];

typedef struct
{
    AdjList adjlist;        /* 描述图结构的邻接表 */
    int vexnum;             /* 节点的数目 */
    int edgenum;            /* 边的数目 */
}ALGraph;                   /* adjacency list：邻接表 */

void LocateVex(ALGraph ALG, VertexType vertex);/* 若图ALG中存在节点vertex，则返回该节点下标 */
void CreateALG(ALGraph * ALG);  /* 邻接表法创建图 */
void TraverseALG(ALGraph ALG);  /* 遍历图ALG */

int main(void)
{
    ALGraph g;

    CreateALG(&g);
    printf("------------------------------\n");
    printf("vexnum = %d ; edgenum = %d\n", g.vexnum, g.edgenum);
    printf("------------------------------\n");
    LocateVex(g, '0');
    printf("------------------------------\n");
    TraverseALG(g);

    return 0;
}
void CreateALG(ALGraph * ALG)
{
    VertexType ch;
    int i = 0, count = 0;
    EdgeNode * temp;

    printf("请输入图的顶点：");
    while ((ch = getchar()) != '\n')/* 建立顶点表 */
    {
        ALG->adjlist[i].vex = ch;
        ALG->adjlist[i].firstedge = NULL;
        i++;
    }
    ALG->vexnum = i;/* 顶点数 */

    for (i = 0; i < ALG->vexnum; i++)/* 头插法建立顶点的邻接边表 */
    {
        printf("请输入顶点 %c 的邻接顶点：", ALG->adjlist[i].vex);
        while ((ch = getchar()) != '\n')/* 按下回车结束邻接点的创建 */
        {
            temp = (EdgeNode *)malloc(sizeof(EdgeNode));
            temp->adjvex = ch;
            temp->next = ALG->adjlist[i].firstedge;
            ALG->adjlist[i].firstedge = temp;
            count++;
        }
    }
    ALG->edgenum = count / 2;   
    // 无向图中每条边连接两个顶点，故：节点总度数 = 边数 * 2
}
void TraverseALG(ALGraph ALG)
{
    int i;
    EdgeNode * temp;

    if (ALG.vexnum == 0)
    {
        printf("图为空\n");
        return;
    }

    for (i = 0; i < ALG.vexnum; i++)/* 遍历图 */
    {
        printf("顶点 %c ：", ALG.adjlist[i].vex);
        temp = ALG.adjlist[i].firstedge;
        while (temp)                /* 输出图的信息 */
        {
            printf("[ %c ] -> ", temp->adjvex);
            temp = temp->next;
        }
        printf("NULL\n");

        /* 以另一种方式输出图的信息
        while (temp) 
        {
            printf("(%c, %c) ", ALG.adjlist[i].vex, temp->adjvex);
            temp = temp->next;
        }
        printf("\n"); */
    }    
}

void LocateVex(ALGraph ALG, VertexType vertex)
{
    int i;

    for (i = 0; i < ALG.vexnum; i++)
    {
        if (ALG.adjlist[i].vex == vertex)
        {
            printf("节点下标：%d\n", i);
            return;
        }
    }
    printf("该节点不存在！\n");
}