Performing an adjacency list graph view

Question

I just started with graph theory. I cannot figure out how to copy an adjacency list using linked lists. for example, if I have this graph (non-oriented):

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

How do I encode it? I know how to do this using an adjacency matrix, but how to encode it using an adjacency list and linked lists (C ++)?

Answer 1

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

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 it better because the verticals are unique, so we can use map . In addition, a vertex can only appear in the list of edges once, so we change it to std::map<vertex, std::set<vertex>> .

So, for starters, 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 //... }; 

Answer 2

An adjacency list will simply be a collection 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; } } }; 

The linked list does not seem particularly practical; usually you define the ordering of the edges and put them in 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 is hard to suggest anything else without knowing what you are going to do with the schedule.