Graph implementation C++

Question

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?

Answer 1

Below is a implementation of Graph Data Structure in C++ as Adjacency List.

I have used STL vector for representation of vertices and STL pair for denoting edge and destination vertex.

#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 << "
Vertex 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);
}