图形实现C++

Question

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

你能建议这样的DS(主要结构或类别以及将在其中的内容).我知道邻接列表和邻接矩阵是主要的可能性,但我的意思是更详细的代码示例.

例如,上次我必须为DFS实现图形时,我想到了这个DS:

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

然后使用一个大小为n的数组,在第i个位置包含表示从第i个节点开始的边的边缘列表(struct Edge).

但是当在这个图上尝试DFS时,我不得不用大约10个while循环编写50行代码.

有什么'好'的实施？

Answer 1

下面是C++中图形数据结构作为邻接列表的实现.

我使用STL向量表示顶点,使用STL对表示边缘和目标顶点.

#include <iostream>
#include <vector>
#include <map>
#include <string>

using namespace std;

struct vertex {
    typedef pair<int, vertex*> ve;
    vector<ve> adj; //cost of edge, destination vertex
    string name;
    vertex(string s) : name(s) {}
};

class graph
{
public:
    typedef map<string, vertex *> vmap;
    vmap work;
    void addvertex(const string&);
    void addedge(const string& from, const string& to, double cost);
};

void graph::addvertex(const string &name)
{
    vmap::iterator itr = work.find(name);
    if (itr == work.end())
    {
        vertex *v;
        v = new vertex(name);
        work[name] = v;
        return;
    }
    cout << "\nVertex already exists!";
}

void graph::addedge(const string& from, const string& to, double cost)
{
    vertex *f = (work.find(from)->second);
    vertex *t = (work.find(to)->second);
    pair<int, vertex *> edge = make_pair(cost, t);
    f->adj.push_back(edge);
}

Answer 2

这实际上取决于你需要实现什么算法,没有灵丹妙药(这不应该是一个惊喜......关于编程的一般规则是没有一般规则;-)).

我经常最终使用带指针的节点/边结构来表示有向多图...更具体地说:

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节点的所有链路的列表以及到达同一to节点的所有链路的列表.

指针prev_same_from和next_same_from以下出来的所有链接的链,当使用从相同的节点; 指针prev_same_to和next_same_to管理所有指向的链接的链时代替被使用于相同的节点.

这是很多指针错综复杂(因此,除非你喜欢指针,否则只是忘记这一点)但查询和更新操作是有效的; 例如,添加节点或链接是O(1),删除链接是O(1)并且删除节点x是O(deg(x)).

当然,根据问题,有效载荷大小,图形大小,图形密度,这种方法可能过度使用或对内存要求过高(除了有效载荷,每个节点有4个指针,每个链接有6个指针).

可以在此处找到类似的结构完整实现.

Answer 3

这个问题很古老,但由于某种原因,我似乎无法理解它.

虽然所有解决方案都提供了图表的实现,但它们也非常冗长.它们根本不优雅.

你真正需要的是一种方法来告诉一个点与另一个点连接 - 而不是发明你自己的图类,std::map并且std::unordered_map工作得非常好.简单地说,将图形定义为节点和边缘列表之间的映射.如果您不需要边缘的额外数据,那么终端节​​点列表就可以了.

因此,C++中的简洁图可以像这样实现:

using graph = std::map<int, std::vector<int>>;

或者,如果您需要其他数据,

struct edge {
    int nodes[2];
    float cost; // add more if you need it
};

using graph = std::map<int, std::vector<edge>>;

现在你的图形结构将很好地插入到语言的其余部分,你不必记住任何新的笨重的界面 - 旧的笨重的界面将做得很好.

没有基准,但我有一种感觉,这也将超过其他建议.

注意:ints不是索引 - 它们是标识符.

Answer 4

最常见的表示可能是这两个:

• 邻接清单

• 邻接矩阵

在这两个中,邻接矩阵是最简单的,只要你不介意有一个(可能是巨大的)n * n数组,其中n是顶点的数量.根据阵列的基本类型,您甚至可以存储边缘权重,以用于例如最短路径发现算法.