Graph Theory Tutorials

theshubhamgoel · June 26, 2014, 9:36pm

Hello coders as i feel little uncomfort on graph theory problems So can u guys guide me . I prefer JAVA.

Please help me in these topic in Java if possible :-

1)How to represent graph in java in adjacency list ?

2)Searching a node in a graph.

3)BFS and DFS in JAVA.

4)Find all Path between 2 nodes in java.

5)And finally maximum flow problem in java.

I will be thankful if u help in some of these problem as these are the frequently asked problems in programming contests.

the65bit · June 27, 2014, 12:00am

There is a tutorial on Topcoder on Graph , u can go through this .

theshubhamgoel · June 27, 2014, 10:20am

As i need java program for these problem but topcoder will only give me sudo code which is in c . So please refer me to link for java program of these problem thanks

the65bit · June 27, 2014, 2:30pm

For the problem in the tutorial , you can go to the problem archive and then see the java solution . if u are still unable to find solution to a particular question , tell me the question name I`ll help u out in finding the solution .

theshubhamgoel · June 27, 2014, 2:56pm

Thanks man

question no 5)

and one more thing is there any advantage of using c++ over java in contest

the65bit · June 27, 2014, 3:29pm

I think u are asking for team builder here is solution : http://community.topcoder.com/stat?c=problem_solution&cr=159530&rd=4740&pm=2356
I haven`t used java , but C++ uses less time , that may be a benefit .

grayhathacker · June 27, 2014, 3:31pm

Can you provide link of some graph based problems on codechef…

the65bit · June 27, 2014, 3:44pm

U can use this site http://code-utils.appspot.com/ and search for graph in tags .

achaitanyasai · June 27, 2014, 4:26pm

@grayhathacker

Of course you can search any category(graphs,trees,dp,greedy,…) using this format :-

codegagu · June 27, 2014, 6:25pm

This is how I do it. I’m still a novice so it might not be very efficient but it works. Please correct me if I’m wrong anywhere and suggestions for improving my methods will be extremely helpful and appreciated

1. How to represent graph in java in adjacency list ?

One way:

Let u be a node in a graph G and say {v1,v2,v3...vn} be its neighbours. So u must be linked to all its neighbours.

u-->{v1,v2,v3...vn} .

To make the link we can use a Map<K,V> which will hold every individual vertex as its keys and the value corresponding to each key will be a list that will contain all the neighbouring vertices of the present key/node u. So we can make an ArrayList to hold all the neighbouring vertices {v1,v2,v3...vn} and then we will make the current vertex u point towards this list (making the link) in our map. So adjacency list has been made for every node and declaration can be done in the following way.

HashMap<Integer,ArrayList<Integer>> my_map = new HashMap<Integer,ArrayList<Integer>>();

This is when all the nodes of the graph are integers,change the type according to your needs.

Another way:

Representation can also be done in this way. Its like an array of lists.

List<Integer> graph[];

The i’th index of the array (graph[]) holds a list which contains all the nodes in the graph that the i’th node is connected to. If there are say N nodes,initialize the graph with empty lists.

for(int i = 0; i < N; i++) {
		graph[i] = new ArrayList<Integer>();
	}

2. Searching a node in a graph.

This can be done by bfs/dfs. Which one to use can be determined by the depth of the graph. In short,if depth is very large,dfs is preferable otherwise bfs will be better. Here is a very neat code that will help you to understand how it is being done. If you don’t prefer to make new node class for the purpose as shown in the link,in that case*(it will get lengthy)* create a method like int get_unvisited_childnodes_of_node(int root_node) which will traverse through the adjacency list of root_node and will return its unvisited child nodes/neighbours.

Graph Theory Tutorials

Suggested problems