I am a novice in competitive programming and I do not know how I can implement an optimal graph in c++ ?. Use a code of geekforgeeks but I do not know how to modify it correctly (it throws me segmentation fault). So far I have not found a site in which to learn how to implement them :(
A graph is given as a collection of nodes and vertices. So let us assume you have
n
nodes andm
vertices.You can take a vector
vector<int> v[n]
. You can think of this like an array of vectors where each index behaves as a node and then the vector at that index will describe the edges.In order to make an edge use
v[parent_node].push_back(destination_node)
. If you have a directed graph then obviously this is sufficient. If this is a undirected graph then you also have to add one more entryv[destination_node].push_back(parent_node)
.You can run a loop to create a complete graph. (I am considering undirected here).
Now if you have to see all the vertices adjacent to a node you can do this
Note:- Keep in mind the nature of indexing. If the indexing is 1-based you will either have to convert it into 0-based indexing by subtracting 1 from each vertex or declare a vector of size n+1
vector<int> v[n+1]
Some time ago I also struggled with a nice graph implementation that was both intuitive and not messy. The idea behind the code that I'll post is to have a nice representation of a single node that we can then place on a vector and with that make an adjacency list (which is the kind of implementation you want for speed).
Let's think (assuming it's an undirected graph): A node has adjacent nodes, which are connected with the "Current" node we're in with these lines called vertices, right? We can represent this relation from node
A
toB
asA->B
&&A<-B
, and we can store these adjacent nodes with a vector. We also need to know if the node we're currently in has been visited or not; we just need a boolean value to represent that, therefore we could make astruct
of nameNode
that represents this idea.It's a simple implementation that doesn't require much effort, and it's a natural representation of a Node. To make a graph, we just need a
vector
with nodes of sizen
. This is how I read the input using this implementation:An example of DFS with this implementation is as follows:
To be honest, I don't think that implementing something like this is actually useful in a contest environment where you have limited time. Sure this code is cleaner and more readable but it's way harder to write and modify and thus more error-prone. Personally I prefer and use the method horcrux2301 suggested.