Creating an adjacency list in C ++ for a directed graph

Question

Hi everyone :) Today I am improving my skills in graph theory and data structures. I decided to make a small project in C ++, because it has been a while since I worked in C ++.

I want to make an adjacency list for a directed graph. In other words, something similar:

0-->1-->3 1-->2 2-->4 3--> 4--> 

This will 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, for example:

 V0----->V1---->V2---->V4 | | v V3 

I know that for this I will need to create an adjacency list in C ++. An adjacency list is basically an array of linked lists . Ok, look at some C ++ pseudo-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 pseudo code is currently far from the label. And this is what I wanted to get with help - C ++ pointers and structures have never been my strong suit. First of all, this applies to the vertices that the vertex points to, but what about the vertex itself? How can I track this peak? When I loop over an array, it’s not good for me to know only what the vertices point to, and not to know what points to them. The first element in each list should probably be this 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 confusing or confusing, I will rephrase with pleasure).

I would like to be able to get hung up on this adjacency list to do cool things with graphs. For example, to implement some graph theory algorithms (sortings, shortest paths, etc.) using the adjacency list view.

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

Answer 1

You can use vector in node as an adjacency list.

 class node { int value; vector<node*> neighbors; }; 

If the graph is known at compile time, you can use array , but it is "a bit" more complicated. If you only know the size of the graph (at compile time), you can do something like this.

 template<unsigned int N> class graph { array<node, N> nodes; } 

To add a neighbor, you do something like this (don't forget numbering from scratch):

 nodes[i].neighbors.push_back(nodes+j); //or &nodes[j] 

Of course, you can make a non-pointer adjacency list and work on a table. Than you have a vector<int> in node and you click on the number of neighbors. With both representations of the graph, you can implement all the algorithms that use the adjacency list.

And finally, I could add. Some use list instead of a vector because deletion happens in O (1) . Mistake. For most algorithms, the order in the adjacency list is not important. Thus, you can erase any element from a vector in O (1) . Just replace it with the last element, pop_back is O (1) complexity. Something like that:

 if(i != number_of_last_element_in_list) //neighbors.size() - 1 swap(neighbors[i], neighbor.back()); neighbors.pop_back(); 

---

Concrete example (you have a vector in node, C ++ 11 (!)):

 //creation of nodes, as previously constexpr unsigned int N = 3; array<node,N> nodes; //or array<node, 3> nodes; //creating edge (adding neighbors), in the constructor, or somewhere nodes[0].neighbors = {&nodes[1]}; nodes[1].neighbors = {&nodes[0], &nodes[1]}; //adding runtime, i,j from user, eg. i = 2, j = 0 nodes[i].neighbors.push_back(&nodes[j]); //nodes[2].neighbors = {&nodes[0]}; 

I think this is understandable. From 0 you can go to 1 , from 1 to 0 and to yourself, and (as, for example) from 2 to 0 . He oriented the count. If you want to redirect, you must add node addresses to both nodes. You can use numbers instead of pointers. vector<unsigned int> in the class node and discarding the return numbers, with no addresses.

---

As we know, you do not need to use pointers. Here is an example of this.

When the number of vertices can change, you can use a vector of nodes ( vector<node> ) instead of an array and just resize . The rest remains unchanged. For example:

 vector<node> nodes(n); //you have n nodes nodes.emplace_back(); //you added new node, or .resize(n+1) //here is place to runtime graph generate //as previously, i,j from user, but now you have 'vector<unsigned int>' in node nodes[i].neighbors.push_back(j); 

But you cannot erase a node, this breaks the numbering! If you want to erase something, you should use a list of ( list<node*> ) pointers. Otherwise, you must save non-existent vertices. Here, order matters!

---

Regarding the string nodes.emplace_back(); //adding node nodes.emplace_back(); //adding node , it is safe with a chart without pointers. If you want to use pointer pointers, you should mainly not resize the graph. You can accidentally change the address of some nodes by adding a vertex when vector is copied to a new location (out of space).

One way to handle this is to use reserve , although you need to know the maximum chart size! But in fact, I urge you not to use vector to store vertices when you use pointers. If you do not know the implementation, managing your own memory (smart pointers like shared_ptr or just new ) can be safer.

 node* const graph = new node[size]; //<-- It is your graph. //Here no address change accidentally. 

Using vector as an adjacency list is always great ! There is no way to change the node address.

Answer 2

This may not be a very general approach, but that is how I handle the adjacency list in most cases. C ++ has an STL library that supports a data structure for a linked list called list .

Assuming there are N nodes in the graph, create a linked list for each node.

 list graph[N]; 

Now graph[i] represents neighbors from node i. For every edge I'm in j do

 graph[i].push_back(j); 

The best comfort is the lack of pointer handling, since segmentation errors are errors.

Read more http://www.cplusplus.com/reference/list/list/

Answer 3

I suggest you add an Adjacency List to the node structure. And define the graph structure as a List of nodes, not a List of adjacency lists :)

 struct node { int vertex; node* next; adjList m_neighbors; }; struct graph{ //List of nodes }; 

Answer 4

I would recommend a more general and simpler approach to using vector and pairs: #include #include

 typedef std::pair<int, int> ii; /* the first int is for the data, and the second is for the weight of the Edge - Mostly usable for Dijkstra */ typedef std::vector<ii> vii; typedef std::vector <vii> WeightedAdjList; /* Usable for Dijkstra -for example */ typedef std::vector<vi> AdjList; /*use this one for DFS/BFS */ 

Or alias style (> = C ++ 11):

 using ii = std::pair<int,int>; using vii = std::vector<ii>; using vi = std::vector<int>; using WeightedAdjList = std::vector<vii>; using AdjList = std::vector<vi>; 

From here: using vector and pairs (from tejas answer)

For more information, you can refer to a very good topcoder summary: Enable C ++ with STL

Answer 5

My approach is to use a hash map to store a list of nodes in a graph

 class Graph { private: unordered_map<uint64_t, Node> nodeList; ... } 

The symbol value is node ID, and node itself is used. Thus, you can search for a node in the graph at a constant time.

node contains an adjacency list, in this case as a C ++ 11 vector. It can also be a linked list, although for this use case I would not see a difference in efficiency. Maybe a list would be better if you want it sorted in some way.

 class Node{ uint64_t id; // Node ID vector<uint64_t> adjList; ... } 

With this approach, you need to go through the adjacency list, and then find the map on the identifier to get the node.

Alternatively, you could have a vector of pointers to neighboring nodes. This will give you direct access to neighboring nodes, but then you would not be able to use the map to keep all your nodes in the graph, and you would lose the ability to easily search for entries in your graph.

As you can see, when implementing the schedule, you need to take into account a lot of compromise decisions, it all depends on your use cases.