数据结构：图；邻接矩阵和邻接表

邻接矩阵： 1.概念：

邻接矩阵是图的存储结构之一，通过二维数组表示顶点间的连接关系。

2.具体例子 ： 一.无向图邻接矩阵示例：

示例图（顶点：A、B、C，边：A-B、B-C）：

邻接矩阵： A B C A 0 1 0 B 1 0 1 C 0 1 0

特点：

矩阵对称，主对角线为0（无自环边）。顶点B的度为2，对应第2行/列非零元素数量。非零元素总数=边数×2（无向图双向性）。 二、有向图邻接矩阵示例

示例图（顶点：V1→V2、V2→V3、V3→V1）：

邻接矩阵： V1 V2 V3 V1 0 1 0 V2 0 0 1 V3 1 0 0

特点：

矩阵不对称（边方向性）。V3的入度=1（第3列非零数），出度=1（第3行非零数）。 三、带权图（网）邻接矩阵示例

示例图（顶点：A、B、C，边：A-B权2，B-C权5）：

邻接矩阵（∞表示无穷）： A B C A 0 2 ∞ B 2 0 5 C ∞ 5 0

特点：

权值替代0/1，主对角线仍为0。对称性保留（无向网），稀疏图可能用压缩存储。 邻接表： 概念：

邻接表是图数据结构最常用的链式存储方式，通过数组与链表结合实现顶点与边的离散化存储。

组成结构 顶点表（头节点表）：一维数组存储顶点信息，每个元素包含顶点值和指向首个邻接点的指针。边表（链表节点）：每个顶点对应的链表，存储其所有邻接点的索引（或地址）及边权重（网图）。例如顶点A的链表包含C，表示存在边AC。 示例图结构：

假设存在无向图如下（顶点：A、B、C、D；边：A-B、A-C、B-C、B-D、C-D）：

A / \ B——C \ / D 邻接表存储实现 1. 顶点表（顺序存储）

顶点表使用数组存储，每个元素包含顶点信息和指向邻接链表的指针：

顶点表索引 | 顶点数据 | 边表头指针 --------------------------------- 0 | A | → 1 → 2 → NULL 1 | B | → 0 → 2 → 3 → NULL 2 | C | → 0 → 1 → 3 → NULL 3 | D | → 1 → 2 → NULL 2. 边表（链表存储）

每个顶点的边表以链表形式存储邻接顶点（本例使用头插法）：

顶点A的邻接链表：B（索引1）、C（索引2）顶点B的邻接链表：A（索引0）、C（索引2）、D（索引3）顶点C的邻接链表：A（索引0）、B（索引1）、D（索引3）顶点D的邻接链表：B（索引1）、C（索引2） // C语言实现（无向图） typedef struct ArcNode { // 边表节点 int adjvex; // 邻接顶点索引 struct ArcNode *next; // 指向下一邻接点 } ArcNode; typedef struct VNode { // 顶点表节点 char data; // 顶点数据 ArcNode *firstarc; // 指向第一个邻接点 } VNode, AdjList[MAX_VERTEX]; typedef struct { AdjList vertices; // 顶点表数组 int vexnum, arcnum; // 顶点数和边数 } ALGraph;