You are not logged in. Please login at www.codechef.com to post your questions!

×

Graph Theory Tutorials

0
1

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.

asked 26 Jun '14, 21:36

theshubhamgoel's gravatar image

3★theshubhamgoel
718111925
accept rate: 5%


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

link

answered 27 Jun '14, 00:00

the65bit's gravatar image

4★the65bit
1.1k101328
accept rate: 13%

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

(27 Jun '14, 10:20) theshubhamgoel3★

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 .

(27 Jun '14, 14:30) the65bit4★

Thanks man

question no 5)

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

(27 Jun '14, 14:56) theshubhamgoel3★

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 .

(27 Jun '14, 15:29) the65bit4★
1

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

(27 Jun '14, 15:31) grayhathacker5★
1

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

(27 Jun '14, 15:44) the65bit4★
(27 Jun '14, 16:26) achaitanyasai5★
showing 5 of 7 show all

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!

link

answered 27 Jun '14, 18:25

codegagu's gravatar image

2★codegagu
3191925
accept rate: 0%

edited 27 Jun '14, 18:26

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,287
×1,212
×1,197
×703

question asked: 26 Jun '14, 21:36

question was seen: 7,320 times

last updated: 27 Jun '14, 21:43