2回答

liuyubobobo

2021-12-04

已采纳

先说说我对这类数据结构的看法：

整体上，我不喜欢这类数据结构，实际上，我连前向星都不愿意使用。原因是：

1）

这类数据结构语义复杂了。相信你明白；

2）

使用这类数据结构其实不会带来复杂度级别的变化。当然，使用 map 各项操作是 O(logn) 的；使用 unordered_map 会产生哈希值的计算的开销；但是，对于不同的应用，我们是可以进行调整的。比如大多数图算法只需要遍历各个节点的邻接点，此时只要使用 vector<vector> 的结构就 ok 了。

但是，如果你需要删边的话，前向星或者链式前向星也是 O(n) 级别的。因为链式前向星的本质就是基于链表的邻接表。只不过使用数组模拟链表而已（next 是索引而非指针）。链表的删除操作就是线性的。如果有删除边的操作，就应该使用 vector<map> 或者 vector<unordered_map>

（但其实，很多问题看似有删除边的操作，但可以避免“实际”的删边。比如通过逆向的过程，把删边的动作转换成添边的动作；或者比如在缩点操作中，使用 uf 等结构来表示缩点的结构，而非真正的删掉图中的边。）

3）

另一方面，你给出的链式前向星的代码，和 vector<vector> 比性能是不公平的。因为你的代码是使用了固定大小的数组。真要比性能，或者把你的代码改成 vector<ty> edge 和 vector<int> head，或者把 vector<vector> 结构改成 vector[MAXV] 或者 list[MAXV]。

其实，这也是我不喜欢很多竞赛代码的原因。edge[MAXM] 这样的写法在实际工程中毫无意义，开一个固定的大空间已经很过分了，还要让这么大的空间是全局变量，完全是为了竞赛而竞赛的写法，本质是为了获得常数级别的性能优势，同时也是“欺负”OJ 只判断代码的正确性，而不看代码的结构，可维护性，扩展性，等等方面。如果真正在生产环境做 code review，这种代码肯定打走重写。

但尽管如此，链式前向星还是性能快的，原因在于：

1）把图本身的二维结构，压缩成了一维结构，使得每次访问少了至少一次寻址；

2）由于是一维结构，所以即使使用 vector<ty>，数组的扩容操作也少了。相比 vector[MAXV]，在每一个点的 vector 都可能面对扩容操作，引起性能的下降；

3）至于你的代码本身使用静态数组，根本就不涉及扩容的问题，前面已经分析了。

==========

综上，如果你注重逻辑的语义性，我不建议使用这类数据结构；

但如果你当前的程序对性能的要求特别高，你自己又理解，不排斥，那么可以使用。

至于应用场景，请把链式前向星就像成是基于链表的邻接表。基于链表的邻接表可以做的，链式前向星都能做；基于链表的邻接表不能做的，链式前向星也不能做。（有一个例外，下面提。）

比如，基于链表的邻接表可以处理重边，那么链式前向星也可以（相较而言，使用 map 或者 unordered_map 不能处理重边。但其实也能使用 multiset）

比如，基于链表的邻接表不能快速删除边，那么链式前向星也不能快速的删除边（相较而言，使用 map 或者 unordered_map 可以快速删边。）

我说的一个例外是什么？是反向边。

因为如果 i 是偶数，则 i^1 = i + 1；如果 i 是奇数，则 i^1 = i - 1。

所以，我们可以把一条边和其反向边成对存储，这样找到一条边，就能迅速找到它的反向边。这是一个小 trick，并且在大量使用反向边的应用中（比如网络流更新残差网络的时候）可以得到不小的性能提升。（但实际上，这个 trick 在成对存储数据的时候，都可以使用，而不仅仅是链式前向星的一个应用）。

但是，这个操作也并非是一定要使用前向星不可的。（否则所有的图论算法书都必须介绍这种数据结构。但实际上，很少有书籍或者文章介绍这种数据结构。）

由于我的课程中的图使用 vector<map> 的方式，所以可以快速定位反向边，但代价是 O(logn) 的，不多说了；

如果对性能有要求，这件事情的解决方案应该是：在 Edge 结构中添加一个 Edge 的指针，指向这条边的反向边，这样，就可以用 O(1) 的时间拿到任意一条边的反向边。

比如，我自己实现的 dinic 算法，其中的边的定义是这样的：

class Edge{
public:
    int u, v;
    T c;
    bool is_residual;
    Edge* counter_edge; // 指向反向边
        
    // 其他省略
};

==========

最后，对于链式前向星这种算法，比赛有用吗？我的看法是：

看你参加的是什么比赛。如果卡常卡的厉害，使用链式前向星肯定是性能有优势的。但是，其实我没有见过哪个比赛中哪个问题必须使用链式前向星解决，非链式前向星不可的。

值得一提的是，我个人认为，

高中阶段的信息学比赛（比如 NOIP），会比大学及以后的比赛（比如 ACM），卡常卡得更厉害（实际上我觉得 ACM 很少卡常）;

国内的比赛，会比国际的比赛（或者国内的 OJ，会比国际的 OJ），卡常卡得厉害（国内更卷？hhhhh）；

但尽管如此，依然是，很少有一个问题，必须使用链式前向星解决，非链式前向星不可。（说实话，我没见过。但我确实也很少研究国内的比赛）

最重要的是，这类数据结构维护相对困难，debug 也困难，所以比赛的时候，维护这种数据结构其实是吃亏的。

当然，如果你是像 dinic 算法这样封装成一个模板直接用，你自己不维护，那也没啥问题。但其实越是高水平的比赛，模版的意义越小。所以，在估算时间复杂度整体问题不大的情况下，我的第一选择绝对不会是链式前向星的。（实在需要优化再说。）

==========

最后：

其实使用数组模拟链式结构也并不是一个特别稀奇的思路。这一点在树结构上经常使用。

最典型的，堆由于是一棵完全二叉树，就可以直接使用数组存储，这是堆的标准实现（而非使用链式结构。）

线段树也是一个好例子。一个典型的线段树的实现，使用大小为 4n 的数组，也是这个思想。

Trie，或者半持久化，持久化数据结构，都可以使用这个思路。

可能有一些问题，使用这样的思路思考，会柳暗花明。比如在一个排列中寻找一个循环组（循环群），也可以用每个数组的元素当做下一个元素的索引，来进行查询。

整体，我不认为链式前向星是一个必须掌握或者使用的数据结构，但是这个思想是值得了解学习的。

继续加油！：）

0

0

慕斯卡8072790

提问者

2021-12-03

我看到有人在知乎的总结，但我水平还不到，不是很理解。

听他的意思是：链式前向星的邻接表可以处理重边，删边快；`map<int, int>[]` 的邻接表可以处理反向边

0

0