领接表和链式前向星哪个更好

领接表和链式前向星都是图数据结构的存储方式，用于表示稀疏图，特别是用于处理网络、社交关系等场景。两者各有优劣：

**领接表**（Adjacency List）：
1. **优点**：
- 空间效率高：对于稀疏图，大部分节点之间没有边，所以占用的空间较少。
- 插入和删除操作更快：只需要修改单个节点的邻接列表，时间复杂度通常为O(1)。
- 支持动态添加和删除节点及其连接。

**缺点**：
- 查询某个顶点的所有邻居时需要遍历整个列表，时间复杂度为O(deg(v))，其中deg(v)是该顶点的度数。

**链式前向星**（Singly Linked Edge List or Forward Star）：
1. **优点**：
- 对于经常查询某个节点所有邻居的情况，通过单链表可以直接到达其所有邻居，无需遍历整个列表，查询效率相对较高。
- 结构简单，易于理解。

2. **缺点**：
- 空间开销可能较大，特别是当图很密集，每个节点都有大量邻接点时，可能会比领接表浪费更多空间。
- 插入和删除操作如果涉及邻接表的话，不是直接操作，会涉及到指针移动，效率略低于领接表。

总的来说，领接表适合频繁插入和删除，同时对查询性能要求不太高的情况；而链式前向星则更适合对查询性能有较高要求，尤其是对特定节点的所有邻居进行查询的场景。选择哪种取决于实际应用的具体需求。

相关问题

邻接矩阵，邻接表和链式前向星的区别

在图论中，数据结构用于表示图有三种常见的方法：邻接矩阵、邻接表和链式前向星。

1. **邻接矩阵**：这是一种二维数组（或矩阵）的表示法，其中行代表图中的顶点，列也代表顶点，每个元素（通常是布尔值或整数）表示两个顶点之间是否存在边。如果(i, j)位置的值为1或非零，表示顶点i和j相连；反之则表示不连接。邻接矩阵存储空间占用大，但查找任意两点间是否有边的时间复杂度是O(1)，对于稠密图效率高。

2. **邻接表**：这是一种基于链表的数据结构，每个顶点都有一个链表，列表中的节点包含与该顶点相邻的所有其他顶点。这样，对于稀疏图来说，节省了大量空间，因为只存储实际存在的边。查找某个顶点的邻居需要遍历链表，时间复杂度为O(degree)，其中degree是顶点的度（即相邻顶点的数量），对查找速度不利。

3. **链式前向星**：这是一种特殊的邻接表，通常用于构建树形图或有向无环图(DAG)的拓扑排序。在这种结构中，每个顶点有一条指向其子节点的链，形成一棵树状结构，且所有指向同一个顶点的边都是从父节点到子节点的。相比于一般的邻接表，链式前向星更直观地反映了图的层次关系，但查找路径可能需要沿着链逐级向前，时间复杂度取决于目标节点的位置。

总结一下，邻接矩阵适合于稠密图，查询速度快，但空间消耗较大；邻接表适用于稀疏图，节省空间，但查找慢；链式前向星则常用于特定类型图的快速搜索，并能体现拓扑结构。选择哪种数据结构主要看图的具体特征和应用需求。

邻接表与链式前向星例题

### 关于邻接表和链式前向星的数据结构例题实现

#### 使用邻接表表示图并解决最短路径问题

对于给定的一个无权有向图，使用邻接表来表示该图，并求解从源点到其他各顶点的最短距离。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 1e5 + 7;
int dist[MAXN];
bool vis[MAXN];

// 定义边结构体
struct Edge {
    int to, next;
} edge[MAXN * 2]; // 假设最多有MAXN*2条边

int head[MAXN], cnt; // head数组记录每个节点的第一条出边编号；cnt用于计数当前已有的边数量

void addEdge(int from, int to) { // 添加一条from->to方向上的边
    edge[++cnt].to = to;
    edge[cnt].next = head[from];
    head[from] = cnt;
}

void bfs(int startNode) {
    queue<int> q;
    memset(dist, -1, sizeof(dist));
    dist[startNode] = 0;
    q.push(startNode);
    
    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        for (int i = head[cur]; ~i; i = edge[i].next) {
            int v = edge[i].to;
            if (dist[v] == -1) {
                dist[v] = dist[cur] + 1;
                q.push(v);
            }
        }
    }
}

这段代码展示了如何利用邻接表构建一张简单的无权有向图以及通过广度优先搜索算法计算起始节点到达其余各个节点之间的最小步数[^1]。

#### 利用链式前向星处理加权图中的最短路问题

下面的例子说明了怎样运用链式前向星存储带权重的边信息，并借助Dijkstra算法找出单源最短路径：

#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;

typedef pair<int,int> PII;

const int N=1e5+10,M=N<<1;

int n,m,S,T,d[N];
PII e[M];
int h[N],ne[M],w[M],idx;

bool st[N];

inline void add(int a,int b,int c){
    e[idx]=make_pair(b,c),ne[idx]=h[a],h[a]=idx++;
}

void dijkstra(){
    memset(d,INF,sizeof d);
    priority_queue<PII,vector<PII>,greater<>> heap;
    d[S]=0;
    heap.push({d[S],S});
    
    while(heap.size()){
        auto t=heap.top(); heap.pop();
        
        int ver=t.second,dis=t.first;
        if(st[ver]) continue;
        st[ver]=true;
        
        for(int i=h[ver];~i;i=ne[i]){
            int j=e[i].first;
            if(d[j]>dis+w[i]){
                d[j]=dis+w[i];
                heap.push({d[j],j});
            }
        }
    }
}

此部分实现了基于链式前向星的方式保存每条边上附带的成本值，并且采用了堆优化版迪杰斯特拉(Dijkstra)算法去查找由指定起点出发至其它任意终点间的最优路线长度[^2]。