CODEWITHSUNDEEP
c++listpointersstlgraph-theory
dagwood
dagwood

Reputation: 409

nested lists to implement adjacency lists in c++

i was going through the code for topological sorting on this website.
i understood the code except for one part which is the declaration of the adjacency list (on line 15), which is 

list<int> *adj;

basically, to me, adj should be a pointer to a list of integers but in this case based on how they have used it, it is a list of lists ... so shouldn't a list of lists be

list <list<int> > adj;

can someone please explain this to me?

Upvotes: 0

Views: 254

Answers (2)

einpoklum
einpoklum

Reputation: 131515

It's important to note that the code you've linked to is rather unidiomatic. One prominent issue it has is exactly with that member you mentioned, list<int> *adj.

In modern C++, we tend to avoid using new and delete directly, when instead, we could use a smart pointer (e.g. std::unique_ptr) or a container. In this specific case, instead of:

list<int> *adj;
// ... etc. ...
Graph(int V) {
    adj = new std::list<int>[V]; 
}

it would indeed be better to use:

std::vector<std::list<int>> vertex_adjacencies;
// ... etc. ...
Graph(std::size_t num_vertices) : vertex_adjacencies(num_vertices) { }

Now, as for your suggestion of a list-of-lists - that's also possible:

std::list<std::list<int>> vertex_adjacencies;
// ... etc. ...
Graph(std::size_t num_vertices) : vertex_adjacencies() 
{
    auto empty_adjacencies = std::list<int>{};
    std::fill_n(
        std::front_inserter(vertex_adjacencies), 
        num_vertices,
        empty_adjacencies);
}

but it would require rewriting various other methods. Also note, that the graph is intended to have a fixed number of vertices, without vertices being added or removed, so placing the vertex-specific adjacency in a list does not make a lot of sense. (Not that a separate std::list for each vertex' adjacencies is such a good idea, performance-wise, anyway, but never mind that).

Upvotes: 1

ArrayIndexOutOfBounds
ArrayIndexOutOfBounds

Reputation: 366

You could also do it like that, however what this website is creating is an array of lists, not exactly a list of lists. I think this approach (array of lists) is the usual way to represent adjacency lists in lots of programming languages. In this way the vertices are numbered from 0 to V-1, and you can access the list of adjacents directly by using the index operator adj[i]

I don't really know the exact reason, but I imagine it's for efficiency purposes.

EDIT: Notice that lists are, according the C++ reference, double-linked lists, so if you want to access element i, an iteration through the linked nodes is needed until you reach element i. With an array, you access directly the list that you are interested in, without iterating and therefore more efficiently. In www.cplusplus.com we can read:

The main drawback of lists and forward_lists compared to these other sequence containers is that they lack direct access to the elements by their position; For example, to access the sixth element in a list, one has to iterate from a known position (like the beginning or the end) to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).

Upvotes: 2

Related Questions