Thread: Implementing an adjacency list in C++?

ello all Today I am refining my skills on graph theory and data structures. I decided to do a small project in C++ because it's been a while since I've worked in C++.
I want to make an adjacency list for a directed graph. In other words, something which looks like:
0-->1-->3
1-->2
2-->4
3-->
4-->This would be a directed graph with V0 (vertex 0) having an edge to V1 and V3, V1 having an edge to V2, and V2 having an edge to V4, like this:
V0----->V1---->V2---->V4
|
|
v
V3

I know that in order to do this, I will need to create an adjacency list in C++. An adjacency list is basically an array of linked lists. Okay, let's see some pseudo C++ code:

Code:

#include <stdio>
#include <iostream>
using namespace std;

struct graph{
//The graph is essentially an array of the adjList struct.  
node* List[];

};

struct adjList{
//A simple linked list which can contain an int at each node in the list.

};

struct node {
int vertex;
node* next;
};

int main() {
//insert cool graph theory sorting algorithm here
}

As you can tell, this pseudocode is currently far from the mark. And that is what i wanted some help with -- pointers and structs in C++ have never been my strong suit. First of all, this takes care of the vertices that a vertex points to -- but what about the vertex itself? How can I keep track of that vertex? When I loop over the array, it will do me no good to only know what vertices are being pointed to, rather than also knowing what points to them. The first element in each list should probably be that vertex, and then the elements after that are the vertices it points to. But then, how can I access this first element of the list in my main program? (sorry if this is convoluted or confusing, I would happy to rephrase).
I would like to be able to loop over this adjacency list to do some cool things with graphs. For example, to implement some graph theory algorithms (sorts, shortest paths, etc) using the adjacency list representation.
(Also, I had a question about the adjacency list. What is different than just using a list of arrays? Why can't I just have a list with an array at each element in the list?)

(Also, I had a question about the adjacency list. What is different than just using a list of arrays? Why can't I just have a list with an array at each element in the list?)

You can.
It will be inefficient if the edges in your graph change a lot.


And btw, if this is not for homework, consider using standard containers.
That you you can focus on the algorithms instead of worrying about what you missed in the linked list implementation.

Code:

#include<vector>
#include<list>
//...
    std::vector<std::list<int>> graph;
//...

Whoa, I don't know nothin' 'bout no array of linked lists but why not just neighbour pointers in your data structure?