How to implement a directed graph?

general
1

how do we implement directed graphs in competitions. I recently learned about the implementation of undirected graph from geeksforgeeks using vectors.Does implementation of directed graph is same as of undirected graph?
it would be helpful if someone attaches a link to their self written code of directed graphs.Thanks in advance

1 Like
2

There are 3 common ways to implement graphs (directed or undirected).

The most easiest one is the 2D matrix of size |V|*|V|. A cell (i, j) will contain 1 if there is an edge from vertex i to vertex j. If the graph is undirected then the cell (j, i) will also contain 1. Otherwise, the cells will contain 0. Also, note that if the graph is weighted, then we can just replace 1 with the weight of that edge. But this is not an efficient approach for Sparse graphs or graphs with large number of vertices. The complexity of this implementation is O(|V|^2).

The second way to represent graphs is Edge List representation. You can implement this in C++ by making a std::vector <std::pair <int, int> > edge_list (for an unweighted graph) where each element of vector will be a pair of vertices which are connected by an edge. If it is a weighted graph, then you can make a std::vector <std::tuple <int, int, int> > edge_list (std::tuple is available since C++11) where each element of vector is a tuple which contains both the vertices connected by an edge with their weight, i.e., <u, v, w(u, v)>. Here also, there isn’t much difference in the representation of directed/undirected graph. All you need to do is, if the graph is undirected, you need to add an additional tuple <v, u, w(v, u)>. The complexity of this representation is O(|E|).

Reference Code: http://ideone.com/9NMTBM

The third and most common type of representation is Adjacency List representation. This can be implemented in C++ using std::vector <std::vector <int> > graph if the graph is unweighted and std::vector <std::vector <std::pair <int, int> > > graph if the graph is weighted. Here, the size of the data structure equals the number of vertices in the graph and each vertex has an additional vector which contains its neighboring vertices. So, for example assume a weighted graph in which vertex u and v are connected by an edge having weight w(u, v). Then, if the graph is undirected, we would include both the edges, i.e.,

graph[u].push_back(make_pair(v, w(u, v));

graph[v].push_back(make_pair(u, w(v, u));  // w(u, v) = w(v, u)

and if the graph is directed, we would only include the directed part of the edge, i.e.,

graph[u].push_back(make_pair(v, w(u, v));

The complexity of this implementation is O(|V| + |E|).

Reference Code: http://ideone.com/0HSYlB

2 Likes
3

Thank you sir cleared all my doubts :slight_smile:

1 Like