Implementation of an adjacency list graph representation

Question

I have just started with the graph theory. I can't figure out how to code adjacency list using linked lists. for example, if I have this graph (undirected):

A--------B
|       /|\
|      / | \  
|     /  |  \
|    /   |   \
|   /    |    \
|  /     |     \
| /      |      \
C        E-------D

How do I code it? I know how to do it using adjacency matrix, but how to code it using adjacency list and linked lists (c++)?

Solution 1

An adjacency list is just a vector/array of lists. Each element in the graph is an element in the array, and any edge is added to the it's adjacency list. Thus it looks something like:

A -> {B, C}

B -> {A, C, D, E}

C -> {A, B}

D -> {B, E}

E -> {B, D}

So we start with something like std::vector<std::list<vertex>>. However, we can do better than this, because verticies are unique, hence we can utilize a map. Furthermore, a vertex can only appear in an edge list once, so we modify it to std::map<vertex, std::set<vertex>>.

So to start with, something like:

struct vertex
{
   //
};

class undirected_graph
{
private:
    std::map<vertex, std::set<vertex>> graph_container;
public:
    void add_vertex(const vertex& v) { //add a vertex to the map }
    void add_edge(const vertex& v, const vertex& u) { //look up vertex in map and add to the vertex adjacency list }
    //Other methods
    //...
 };

Solution 2

An adjacency list would just be a set of objects representing the edges of the graph.

struct edge {
    node *nodes[2];

    edge( node *a, node *b ) {
        if ( a < b ) { // define canonical order of edges for undirected graph
            nodes[0] = a;
            nodes[1] = b;
        } else {
            nodes[0] = b;
            nodes[1] = a;
        }
    }
};

A linked list doesn't sound particularly practical; usually you would define an ordering of edges and put them in a std::set or std::map.

bool operator< ( edge const &lhs, edge const &rhs ) {
    if ( lhs.nodes[0] < rhs.nodes[0] ) return true;
    if ( rhs.nodes[0] < lhs.nodes[0] ) return false;
    return lhs.nodes[1] < rhs.nodes[1];
}

typedef std::set< edge > graph;

There are many ways to do this, it's hard to suggest anything more without knowing what you intend to do with the graph.

Comments

[Potatoswatter]

From Wikipedia: "In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list." What you've implemented is maybe an optimization of that, but the fundamental concept is a bit obscured.

[Yuushi]

@PushkarMishra Sure. If you're trying to implement this for the first time, use whatever is easiest.

[Somebody]

is vectors an efficient option?

[Yuushi]

Well, the whole point of adjacency lists vs adjacency matricies is that they are more memory efficient for graphs that do not have too many edges. The map/set implementation will likely be faster, but for any graphs that aren't quite large, the difference will probably be minimal.

[Kaushik Acharya]

using std::map for adjacency list will lead to O(|V|*log(|V|)+|E|) complexity for bfs/dfs traversal where |V|,|E| are the size of vertices and edges respectively. Hence for sparse matrix, it will lead to higher time complexity.

[Yuushi]

@KaushikAcharya HIgher time complexity as compared to what? If you mean as compared to an undordered_map, then yes, you can reduce it to O(|V| + |E|) (given amortized O(1) lookup).