我想知道在 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++的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持跟版网!