Hello 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>
V0>V1>V2>V4


v
V3
#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
}
You may use a vector in node, as a adjacency list.
class node {
int value;
vector<node*> neighbors;
};
If the graph is known at compile time, you can use array, but it's "a little bit" harder. If you know just size of graph (at compile time) you can do something like that.
template<unsigned int N>
class graph {
array<node, N> nodes;
}
To add a neighbor, you doing something like that (do not forget numbering from zero):
nodes[i].neighbors.push_back(nodes+j); //or &nodes[j]
Of course, you can do nopointer adjacency list and work "above" a table. Than you have vector<int>
in node and you pushing number of neighbour. With both representation of the graph, you can realize all algorithms which use adjacency list.
And finally, I might add. Some use a list instead of a vector, because the removal is in O(1) time. Mistake. For most algorithms, the order in the adjacency list is not important. So you can erase any element from vector in O(1) time. Just swap it with 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();
Specific example (you have 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 believe it's clear. From 0
you can go to 1
, from 1
to 0
and to itself, and (as in eg.) from 2
to 0
. It's directed graph. If you want undirected, you should add to both nodes neighbourâ€™s addresses. You can use numbers instead of pointers. vector<unsigned int>
in class node
and pushing back numbers, no addresses.
As we know, you do not need to use pointers. Here is an example of it, too.
When the number of vertexes may change, you can use vector of nodes (vector<node>
) instead array, and just resizing. 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 can't erase a node, this breaches numbering! If you want to erase something, you should use list (list<node*>
) of pointers. Otherwise you must keep nonexistent vertexes. Here, the order matters!
Regarding the line nodes.emplace_back(); //adding node
, It is safe with graph without pointers. If you want use pointers, you predominately shouldn't change size of graph.
You can accidentally change address of some nodes, while adding vertex, when vector
will be copied to new place (out of space).
One way to deal with it is using reserve, although you have to know maximal size of graph! But in fact I encourage you not to use vector
to keep vertexes, when you are using pointers. If you don't know implementation, more safe could be self memory management (smart pointers eg. shared_ptr or just new).
node* const graph = new node[size]; //< It is your graph.
//Here no address change accidentally.
Using vector
as adjacency list is always fine! There's no chance to change node's address.