数据结构之邻接表
数据结构之邻接表
邻接表是图论中一种常用的存储结构，特别适用于表示稀疏图。它结合了顺序分配和链式分配的特点，通过数组和链表的组合来存储图的信息。下面将详细介绍邻接表的基本概念、结构、构建方式以及应用场景。
一、基本概念
邻接表由两部分组成：顶点表和边表（或邻接链表）。
顶点表：一个一维数组，用于存储图中的顶点信息。数组中的每个元素对应图中的一个顶点，同时包含一个指向该顶点邻接链表的指针（或引用）。
边表（邻接链表）：对于顶点表中的每个顶点，都有一个链表与之对应，链表中存储的是与该顶点相邻的所有顶点。在无向图中，每条边在邻接表中出现两次（两个顶点各指向对方一次）；在有向图中，则只出现一次，表示有向边的方向。
二、结构
以C++为例，邻接表的基本结构可以定义如下：
#include <vector>
#include <list>struct EdgeNode {int adjvex; // 邻接点在图中的位置// 如果有权值，可以添加一个weight成员// int weight;EdgeNode* next; // 指向下一个邻接点
};struct VertexNode {int data; // 顶点信息EdgeNode* firstEdge; // 指向第一条邻接边的指针
};struct Graph {VertexNode adjList[MAX_VERTEX_NUM]; // 邻接表int numVertices, numEdges; // 图中顶点的数目和边的数目
};
注意：这里为了简化，没有包含权值信息。如果需要处理带权图，可以在EdgeNode结构体中添加一个weight成员。
三、构建方式
构建邻接表的过程主要包括以下步骤：
1、初始化顶点表：根据图的顶点数，分配顶点表的空间，并初始化每个顶点的邻接链表为空。
2、读入边信息：根据图的边信息（对于无向图，每条边读入两次；对于有向图，每条边读入一次），为每个顶点建立相应的邻接链表。
3、构建邻接链表：对于每条边，创建一个边表结点，并将其插入到对应顶点的邻接链表中。
四、应用场景
邻接表广泛应用于图的各种算法中，如图的遍历（深度优先搜索DFS、广度优先搜索BFS）、最短路径问题（如Dijkstra算法、Bellman-Ford算法）、拓扑排序、关键路径等。由于邻接表能够高效地表示稀疏图，因此在处理大规模稀疏图时尤为有效。
五、优缺点
1、优点：
节省空间：对于稀疏图，邻接表比邻接矩阵更节省存储空间。
灵活高效：在邻接表中，可以方便地添加或删除边，同时能够快速地访问某个顶点的所有邻接点。
2、缺点：
访问性较差：在邻接表中，要确定两个顶点之间是否存在边，需要遍历其中一个顶点的邻接链表，这比邻接矩阵的O(1)时间复杂度要慢。
依赖于顶点的存储顺序：在邻接表中，顶点的存储顺序可能会影响某些算法的效率。
综上所述，邻接表是图论中一种非常重要的存储结构，它结合了数组和链表的优点，能够高效地表示和处理稀疏图。