图实现C++

我想知道如何用 C++ 快速编写图的实现。我需要数据结构易于操作和使用图算法（例如 BFS、DFS、Kruskal、Dijkstra...）。 我需要这个实现来参加算法奥林匹克竞赛，因此编写数据结构越容易越好。

你能建议这样的DS（主要结构或类以及其中的内容）吗？我知道邻接列表和邻接矩阵是主要的可能性，但我的意思是更详细的code sample.

例如，上次我必须为 DFS 实现一个图时，我想到了这个 DS：

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

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

但是当尝试在该图上进行 DFS 时，我必须编写 50 行代码和大约 10 个 while 循环。

有哪些“好的”实现？

下面是 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);
}