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

×

please help me!!!(graphs and trees)

0
1

hello nowadays i am having a rough time learning graph because i face difficulty understanding adjacency matrix and list.I don't understand them very well.First help expecting from you all

1)am i the only one who faces this difficulty in these topics

2)can you drop a link to your dfs & bfs(or any other graph algorithm)implementation so that i can look upon it and try to implement them.(this will teach different ways to do same thing)

3)anyway to learn implementation effectively except geeksforgeeks(this website is good but i barely understand them :( )

PS: i have watched many video lectures but they don't teach implementation.my main point of concern is that i don't get good implementation source.

asked 31 Jan '15, 13:51

sneha6966's gravatar image

0★sneha6966
335
accept rate: 0%


I had the same problem a few months ago and I posted the same question here. I got many useful resources. Among them, my personal favorite is e-maxx.ru. This is a Russian web site, so use google translator.

A few pointers before you go there.
1) First learn adjacency matrix for undirected graph. It is a bit easier and easy to visualize as it considers all possibilities.
2) Implement breadth first search and depth first search on adjacency matrix and solve a few easy problems on it.
3) Most graph searching problems rely on connected components which is just a simple extension of regular traversal. (Ask if you are having trouble with it after learning dfs and bfs).
4) After that, learn a few problems that are basically just a bit extension of the bfs and dfs like connected components and few others(I can't recall right now, sorry).
5) Then learn these above for directed graph and try to understand topological sort, finding articulation points, bridges etc. (e-maxx.ru).
6) All the above will work if number of vertices are small. If not, you need adjacency matrix. So learn it now.
7) If you still have problem, just try to implement and then ask with your code. It is easier to understand when a fault is found in your own code, rather in some one else's code.

p.s. BFS requires a queue. You can implement it easily. But use STL as it provides list which is easy to use and is less prone to errors.

link

answered 31 Jan '15, 14:37

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

thanks...can you give a link to your dfs and bfs code along with problem link it will help me a lot..

(31 Jan '15, 15:05) sneha69660★

Try this problem and check out my solution

(31 Jan '15, 16:25) dragonemperor3★

Also This problem and this solution.

Both problems are similar and use BFS.

(31 Jan '15, 16:27) dragonemperor3★

I faced difficulty understanding graph(/trees) and everybody does.

you can see my solution to this problem. Its a very basic tree (or graph) problem.

For implementation of graph, best way is to see others solutions for graph problems from codechef and codeforces.

link

answered 31 Jan '15, 14:35

rajeevkgprk's gravatar image

4★rajeevkgprk
1493
accept rate: 17%

hey i am in the same boat :D but yeah i think i might be able to help you a bit.yo might google codechef tags and there you can find questions taged with bfs or dfs or whatever you want.as per implementation part i would recomend doing those question and see their editorial.i am posting a editorial of one good question as per implementation part in this editorial even code is given do see it as you will learn a lot from it.you might also see these tutorials http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs1 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs2 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs3 you might also search quora for this there are really really good answers for any coding problem. this is the editorial which i was saying
http://discuss.codechef.com/problems/DIGJUMP a link for the tagged problems of bfs http://www.codechef.com/tags/problems/bfs do some questions from here and do those which have more submission so it is to see the understandable code from others. hope this help as i said earlier i am in the same boat :D ..

link

answered 31 Jan '15, 14:41

rishabhjoshi93's gravatar image

2★rishabhjoshi93
161
accept rate: 100%

Hi @sneha6966.
Yes you are right. For beginners ( and sometimes for experienced coders also ) trees and graph theories are difficult to understand and comprehend.

  1. No, I'm sure you are not the only one facing such difficulty.
  2. Check this and this. Also go through the wiki articles about these topics and search online for codes/help but do not implement blindly. Understand/modify /alter to suit your needs. Go through the links in other answers. @dragonemperor provided some very good basic steps for your problem.
  3. Geekforgeeks is a good site but if you are facing difficulty then ask for help there or go through different sites. Read books on Algorithm by Cormen or any other author (as you like) and go through tutorials, editorials on codechef, topcoder, codeforces, spoj.
  4. Always practice what you have learnt. Implement your logic into code and evaluate them. Test your code in various graph/tree problems available on codechef ( or other places) and check if your implementations are correct. If wrong, try again. If TLE then use efficient approach. Practice is the key to understand such problems ( actually all problems) .

Enjoy.

link

answered 31 Jan '15, 14:45

mediocoder's gravatar image

3★mediocoder
1.1k313
accept rate: 36%

edited 31 Jan '15, 14:49

thanks...can you give a link to your dfs and bfs code along with problem link it will help me a lot..

(31 Jan '15, 15:04) sneha69660★
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:

×373

question asked: 31 Jan '15, 13:51

question was seen: 2,444 times

last updated: 31 Jan '15, 16:27