问题描述
我想知道在 C++ 中快速编写图形的实现.我需要数据结构易于操作和使用图算法(例如 BFS、DFS、Kruskal、Dijkstra...).我需要在 Olympiad 算法中使用此实现，因此数据结构越容易编写越好.
I was wondering about a quick to write implementation of a graph in c++. I need the data structure to be easy to manipulate and use graph algorithms(such as BFS,DFS, Kruskal, Dijkstra...). I need this implementation for an algorithms Olympiad, so the easier to write the data structure the better.
您能否建议这样的 DS(主要结构或类以及其中的内容).我知道邻接列表和邻接矩阵是主要的可能性，但我的意思是更详细的代码示例.
Can you suggest such DS(main structs or classes and what will be in them). I know that an Adjacency list and Adjacency matrix are the main possibilities, but I mean a more detailed code sample.
例如，我上次不得不为 DFS 实现图形时就想到了这个 DS:
For example I thought about this DS last time I had to implement a graph for DFS:
struct Edge {
int start;
int end;
struct Edge* nextEdge;
}
然后使用一个大小为 n 的数组，在其第 i 个位置中包含表示从第 i 个节点开始的边的边列表(结构边).
and then used a array of size n containing in its i'th place the Edge List(struct Edge) representing the edges starting in the i'th node.
但是当我尝试在这个图上进行 DFS 时，我不得不编写一个 50 行的代码，其中包含大约 10 个 while 循环.
but when trying to DFS on this graph I had to write a 50 line code with about 10 while loops.
有哪些好的"实现?
推荐答案
这真的取决于你需要实现什么算法，没有灵丹妙药(这并不奇怪......编程的一般规则是没有一般规则;-) ).
It really depends on what algorithms you need to implement, there is no silver bullet (and that's shouldn't be a surprise... the general rule about programming is that there's no general rule ;-) ).
我经常最终使用带有指针的节点/边结构来表示有向多重图......更具体地说:
I often end up representing directed multigraphs using node/edge structures with pointers... more specifically:
struct Node
{
... payload ...
Link *first_in, *last_in, *first_out, *last_out;
};
struct Link
{
... payload ...
Node *from, *to;
Link *prev_same_from, *next_same_from,
*prev_same_to, *next_same_to;
};
换句话说，每个节点都有一个传入链接的双向链表和一个传出链接的双向链表.每个链接都知道from 和to 节点，并且同时位于两个不同的双向链表中:来自同一from<的所有链接的列表/code> 节点和到达同一 to 节点的所有链接的列表.
In other words each node has a doubly-linked list of incoming links and a doubly-linked list of outgoing links. Each link knows from and to nodes and is at the same time in two different doubly-linked lists: the list of all links coming out from the same from node and the list of all links arriving at the same to node.
指针prev_same_from 和next_same_from 用于跟踪来自同一节点来自的所有链接的链；当管理指向到同一节点的所有链接的链时，改为使用指针prev_same_to和next_same_to.
The pointers prev_same_from and next_same_from are used when following the chain of all the links coming out from the same node; the pointers prev_same_to and next_same_to are instead used when managing the chain of all the links pointing to the same node.
这是大量的指针操作(所以除非你喜欢指针，否则就忘记这一点)但是查询和更新操作是高效的；例如添加一个节点或一个链接是O(1)，删除一个链接是O(1)，删除一个节点x 是O(deg(x)).
It's a lot of pointer twiddling (so unless you love pointers just forget about this) but query and update operations are efficient; for example adding a node or a link is O(1), removing a link is O(1) and removing a node x is O(deg(x)).
当然，根据问题、有效载荷大小、图形大小、图形密度，这种方法可能会过度杀伤或对内存要求过高(除了有效载荷之外，每个节点有 4 个指针，每个链接有 6 个指针).
Of course depending on the problem, payload size, graph size, graph density this approach can be way overkilling or too much demanding for memory (in addition to payload you've 4 pointers per node and 6 pointers per link).
可以在此处找到类似结构的完整实现.
A similar structure full implementation can be found here.
这篇关于图实现 C++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！