邻接矩阵、邻接表、链式前向星
时间: 2025-02-07 12:10:49 浏览: 51
### 不同图存储结构的特点及应用场景
#### 邻接矩阵特点及应用
邻接矩阵是一种二维数组表示方法,适用于稠密图。对于具有 \(n\) 个顶点的无向图而言,其大小为 \(n \times n\) 的布尔矩阵可以用来描述任意两个节点间是否存在边相连的情况[^1]。
优点在于查询两点之间是否有直接路径非常迅速;缺点则是当处理稀疏图时会浪费大量内存资源用于保存不存在的连接关系,并且增加或删除一条边的操作效率较低。
```cpp
// C++ code snippet for Adjacency Matrix representation of a graph.
const int MAXN = 105;
int adjMatrix[MAXN][MAXN];
void addEdge(int u, int v){
adjMatrix[u][v]=adjMatrix[v][u]=1; // For undirected graphs
}
```
#### 邻接表(Adjacency List)特点及应用
采用一维数组加指针的方式构建列表来记录每一个结点所关联的所有其他结点的信息。相较于邻接矩阵来说更加节省空间,在大多数情况下能够更高效地完成增删操作以及遍历工作[^2]。
特别适合于表达稀疏网络中的数据结构形式,因为只需要占用实际存在的边数目的额外储存单元即可满足需求。
```cpp
// C++ code snippet for Adjacency List (Vector Implementation).
vector<int> adjList[MAXN];
void addEdge(int u,int v){
adjList[u].push_back(v);
adjList[v].push_back(u); // If the graph is undirected
}
```
#### 链式前向星(Priority Star Chain)特点及应用
本质上是对传统邻接表的一种改进版本,通过预先分配好足够的连续内存块作为缓冲区以容纳所有的边信息并利用头插法依次填入每条边的具体情况从而达到快速定位的目的[^3]。
这种做法不仅保持了原有邻接表的优点——即良好的时空性能平衡特性外还进一步提高了访问速度,尤其在竞赛编程领域受到了广泛欢迎。不过初次接触可能会觉得难以掌握。
```cpp
// C++ code snippet for Priority Star Chain implementation.
struct Edge {
int to,w,next;
} edge[MAXM*2];
int head[MAXN],tot=0;
inline void addedge(int from ,int to ,int w ){
edge[++tot]=(Edge){to,w,head[from]};
head[from]=tot;
}
```
阅读全文
相关推荐


















