Format for graph programs.

general
,
1

I have been learning graphs from geeksforgeeks.org .I have understood what BFS,DFS etc. are,so the problem is not with the algorithm ,but the problem is with the format of their implementation. For every algorithm ,they have used some different format,so i cannot decide upon a single format , so can someone give proper implementation of these ?

Here is what i am thinking to implement(from geeksforgeeks)

class Graph
{
int V;    // No. of vertices
list<int> *adj;    // Pointer to an array containing adjacency lists
public:
Graph(int V);  // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void BFS(int s);  // prints BFS traversal from a given source s
};

Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}

So, does someone has a better implementation?.
Also, what will be the perks of using adjacency list over adjacency matrix,i mean what will be efficient in contests?

2

Using classes always limits you to the functions defined in the class itself.

While this is a good thing in terms of OOPS, coding problems on codechef requires you to do more than just simple BFS/DFS.

Many times you’ll need to modify your BFS function in order to solve the problem. Sometimes you may need to make an external function to do something. Now since you have to access the variable inside the class, you’ll need to add a prototype inside the class as well.

All this will severely affect the time taken in coding the problem. And it will lower your rank.

You want to put together a solution good enough that it works and it doesnt take you a lot of time to code.

I’d suggest you dont use classes and simply use a vector of vector or an array of vector.

Go through to implementation part in this tutorial Topcoder

And have a look at how other people code their graph problems :

Here’s my solution to FIRESC, the most easiest and straightforward problem on codechef about graph (Solve this as you first graph problem.)
http://www.codechef.com/viewplaintext/3236205

EDIT: Adjacency list v/s matrix.
In terms of space complexity, matrix will always take the same space regardless of number of edges in the graph.
However adjacency list will take space proportional to the number of edges in the graph.

So use adjacency lists whenever the number of nodes are large, while the number of nodes are small.

In terms of look up time, matrix will get you O(1) complexity. If you want to know if there’s an edge between two nodes, it will take O(1) time if you use matrix.
If you use Adjacency lists, you’ll have to go through all the edges from a particular edge, giving you a worst case complexity of O(n).

So if you want to make a lot of queries about whether there is an edge between two nodes or not, Use a matrix.

Happy coding!!

3 Likes