图实现C ++ [英] Graph implementation C++

问题描述

我想知道如何在c ++中快速编写图形的实现。我需要的数据结构易于操作和使用图算法（如BFS，DFS，Kruskal，Dijkstra ...）。
我需要一个算法Olympiad的这个实现，所以更容易写数据结构更好。

你可以建议这样的DS（主结构或类和什么将在他们）。我知道邻接列表和邻接矩阵是主要的可能性，但我的意思是更详细的代码示例。

这个DS最后一次我必须为DFS实现一个图：

  struct Edge {
 int start; 
 int end; 
 struct Edge * nextEdge; 
} 
  

，然后使用一个大小为n的数组，表示从第i个节点开始的边的边列表（struct Edge）。

但是当尝试在这个图上的DFS时，我不得不写一个50行代码10 while循环。

有什么好的实现？

解决方案

p>这真的取决于你需要实现什么算法，没有银弹（这不应该是一个惊喜...关于编程的一般规则是没有一般规则;-)）。

我经常使用具有指针的节点/边缘结构来表示定向的多重图形...更具体地：

 code> 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; 
}; 
  

换句话说，每个节点都有一个双向链接的链接列表和一个双向链表输出链路。每个链接知道从和到节点，并且同时在两个不同的双向链表中：所有从从节点出来的链接以及到达同一到节点的所有链接的列表。 p>

这是一个很多指针twiddling（所以，除非你爱指针只是忘了这一点），但查询和更新操作是高效的;例如添加节点或链接是O（1），移除链接是O（1），并且移除节点x是O（deg（x））。

当然，根据问题，有效载荷大小，图大小，图密度这种方法可能是过度杀灭或对内存要求过高（除了有效载荷，每个节点有4个指针，每个链接有6个指针）。

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.

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.

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;
}

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.

but when trying to DFS on this graph I had to write a 50 line code with about 10 while loops.

What 'good' implementations are there?

解决方案

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;
};

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.

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)).

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).

这篇关于图实现C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！