用以邻接表作为图的存储结构

邻接表是一种常用的图的存储结构，它是基于链表实现的。对于一个无向图，邻接表存储结构的每个节点都包含两个信息：顶点信息和与其相邻的顶点信息。对于一个有向图，邻接表存储结构的每个节点包含三个信息：顶点信息、指向该顶点的边信息和由该顶点指向的边信息。

具体来说，邻接表的实现方式是将每个顶点所连向的所有顶点都存储在一个单独的链表中，每个链表的头节点就是该顶点。这样，对于一个无向图，每个顶点会对应一个链表，链表中存储该顶点相邻的所有顶点；对于一个有向图，每个顶点会对应两个链表，一个存储指向该顶点的边信息，另一个存储该顶点指向的边信息。

使用邻接表作为存储结构的优点是：

1. 对于稀疏图，邻接表能够节省空间，因为只有存在边的顶点才会被存储；
2. 邻接表能够快速地查找一个顶点的所有相邻顶点；
3. 邻接表支持并行计算，因为每个链表可以作为一个独立的任务进行计算。

当然，邻接表也有一些缺点，比如对于需要查找两个顶点之间的路径的操作会比较耗时。但是在大多数情况下，邻接表是一种非常实用的图的存储结构。

相关问题

以邻接矩阵作为存储结构

邻接矩阵是一种常用的图的存储结构，它使用二维数组来表示图中各个节点之间的连接关系。具体来说，邻接矩阵的行和列分别表示图中的节点，矩阵中的元素表示节点之间是否存在边。如果节点i和节点j之间存在边，则邻接矩阵中第i行第j列的元素为1，否则为0。

使用邻接矩阵作为存储结构的优点是可以快速地判断两个节点之间是否有边相连。同时，邻接矩阵也非常适合存储稠密图，因为它可以用一个二维数组直接表示所有节点之间的连接关系。

但是，邻接矩阵也有一些缺点。首先，邻接矩阵需要占用大量的内存空间，特别是在存储稀疏图时。其次，如果需要遍历整个图，邻接矩阵的效率可能不如其他数据结构，比如邻接表。

用C语言代码实现邻接表的存储，输出存储结构示意图

下面是使用C语言实现邻接表存储的示例代码：

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

#define MAX_VERTEX_NUM 20

// 邻接表中的边结构体
typedef struct ArcNode {
    int adjvex;             // 该边所指向的顶点的位置
    struct ArcNode *next;   // 指向下一条边的指针
    // 边的其他信息可以在这里添加
} ArcNode;

// 邻接表中的顶点结构体
typedef struct VNode {
    int data;               // 顶点的数据
    ArcNode *firstarc;      // 指向第一条依附该顶点的边的指针
    // 顶点的其他信息可以在这里添加
} VNode, AdjList[MAX_VERTEX_NUM];

// 邻接表结构体
typedef struct {
    AdjList vertices;       // 邻接表的顶点数组
    int vexnum, arcnum;     // 顶点数和边数
    // 图的其他信息可以在这里添加
} ALGraph;

// 创建邻接表
void CreateALGraph(ALGraph *G) {
    int i, j, k;
    ArcNode *arc;
    printf("请输入图的顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请输入%d个顶点的数据：", G->vexnum);
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;     // 初始化链表头指针
    }
    printf("请输入%d条边的顶点对应的序号（如：i j）：\n", G->arcnum);
    for (k = 0; k < G->arcnum; k++) {
        scanf("%d%d", &i, &j);
        arc = (ArcNode *)malloc(sizeof(ArcNode));
        arc->adjvex = j;                    // 该边所指向的顶点的位置
        arc->next = G->vertices[i].firstarc;// 头插法插入边结点
        G->vertices[i].firstarc = arc;
        // 无向图还需要插入一条从j指向i的边
        arc = (ArcNode *)malloc(sizeof(ArcNode));
        arc->adjvex = i;
        arc->next = G->vertices[j].firstarc;
        G->vertices[j].firstarc = arc;
    }
}

// 输出邻接表的存储结构
void PrintALGraph(ALGraph G) {
    int i;
    ArcNode *arc;
    printf("邻接表的存储结构如下：\n");
    for (i = 0; i < G.vexnum; i++) {
        printf("%d -> ", G.vertices[i].data);
        arc = G.vertices[i].firstarc;
        while (arc != NULL) {
            printf("%d -> ", G.vertices[arc->adjvex].data);
            arc = arc->next;
        }
        printf("NULL\n");
    }
}

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

下面是该代码实现的邻接表的存储结构示意图，以无向图为例：

      2
    /   \
   /     \
  1-------3
 / \     / \
4---5---6---7

邻接表的存储结构如下：
1 -> 2 -> 5 -> 4 -> NULL
2 -> 1 -> 3 -> NULL
3 -> 2 -> 7 -> 6 -> NULL
4 -> 1 -> 5 -> NULL
5 -> 1 -> 4 -> 6 -> NULL
6 -> 3 -> 5 -> 7 -> NULL
7 -> 3 -> 6 -> NULL

其中，数字表示顶点的数据，箭头表示边的方向。从示意图可以看出，邻接表的存储结构保存了每个顶点的所有邻接点，对于无向图，每条边在邻接表中都会保存两次。