 # Graph Theory Tutorials

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

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.

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

2 Likes

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

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 .

Thanks man

question no 5)

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

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 .

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

1 Like

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

1 Like

@grayhathacker

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

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.

## Suggested problems

I haven’t learnt max flow yet so can’t say anything about that. Its an advanced topic so before working on maxflow make sure that you know the basic graph algorithms well.

Good luck!

1 Like

thanks man provide me some problem on graph

//