<small id='mk8Wb'></small><noframes id='mk8Wb'>

  • <legend id='mk8Wb'><style id='mk8Wb'><dir id='mk8Wb'><q id='mk8Wb'></q></dir></style></legend>

      <tfoot id='mk8Wb'></tfoot>
      <i id='mk8Wb'><tr id='mk8Wb'><dt id='mk8Wb'><q id='mk8Wb'><span id='mk8Wb'><b id='mk8Wb'><form id='mk8Wb'><ins id='mk8Wb'></ins><ul id='mk8Wb'></ul><sub id='mk8Wb'></sub></form><legend id='mk8Wb'></legend><bdo id='mk8Wb'><pre id='mk8Wb'><center id='mk8Wb'></center></pre></bdo></b><th id='mk8Wb'></th></span></q></dt></tr></i><div id='mk8Wb'><tfoot id='mk8Wb'></tfoot><dl id='mk8Wb'><fieldset id='mk8Wb'></fieldset></dl></div>
          <bdo id='mk8Wb'></bdo><ul id='mk8Wb'></ul>

        图实现 C++

        时间:2023-06-29

        <small id='d6p6S'></small><noframes id='d6p6S'>

        <legend id='d6p6S'><style id='d6p6S'><dir id='d6p6S'><q id='d6p6S'></q></dir></style></legend>

          1. <tfoot id='d6p6S'></tfoot>

            <i id='d6p6S'><tr id='d6p6S'><dt id='d6p6S'><q id='d6p6S'><span id='d6p6S'><b id='d6p6S'><form id='d6p6S'><ins id='d6p6S'></ins><ul id='d6p6S'></ul><sub id='d6p6S'></sub></form><legend id='d6p6S'></legend><bdo id='d6p6S'><pre id='d6p6S'><center id='d6p6S'></center></pre></bdo></b><th id='d6p6S'></th></span></q></dt></tr></i><div id='d6p6S'><tfoot id='d6p6S'></tfoot><dl id='d6p6S'><fieldset id='d6p6S'></fieldset></dl></div>

              <bdo id='d6p6S'></bdo><ul id='d6p6S'></ul>
                    <tbody id='d6p6S'></tbody>
                  本文介绍了图实现 C++的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着跟版网的小编来一起学习吧!

                  问题描述

                  我想知道在 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;
                  };
                  

                  换句话说,每个节点都有一个传入链接的双向链表和一个传出链接的双向链表.每个链接都知道fromto 节点,并且同时位于两个不同的双向链表中:来自同一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_fromnext_same_from 用于跟踪来自同一节点来自的所有链接的链;当管理指向同一节点的所有链接的链时,改为使用指针prev_same_tonext_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++的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持跟版网!

                • <small id='x2ILf'></small><noframes id='x2ILf'>

                  <tfoot id='x2ILf'></tfoot>
                  • <bdo id='x2ILf'></bdo><ul id='x2ILf'></ul>

                        <legend id='x2ILf'><style id='x2ILf'><dir id='x2ILf'><q id='x2ILf'></q></dir></style></legend>

                            <tbody id='x2ILf'></tbody>
                        1. <i id='x2ILf'><tr id='x2ILf'><dt id='x2ILf'><q id='x2ILf'><span id='x2ILf'><b id='x2ILf'><form id='x2ILf'><ins id='x2ILf'></ins><ul id='x2ILf'></ul><sub id='x2ILf'></sub></form><legend id='x2ILf'></legend><bdo id='x2ILf'><pre id='x2ILf'><center id='x2ILf'></center></pre></bdo></b><th id='x2ILf'></th></span></q></dt></tr></i><div id='x2ILf'><tfoot id='x2ILf'></tfoot><dl id='x2ILf'><fieldset id='x2ILf'></fieldset></dl></div>