Need Help (Binary Tree)

general
, ,
1

Hello,
i started on learning coding 2-3 months back…
So far i have never been able to solve many problems… only the easy ones in contests.
I think this is because i am able to solve only those problem which are straight forward and simple.
So I thought to learn various algorithm as i encounter their use in contest problem…
So at first i picked up the Kamehameha problem and want to learn the concepts and algorithm behind it.

I googled the Hopcroft-karp algorithm, read about it but it seemed too complicated at first, because of the use of BFS(breadth first search) DFS(Depth…) which i have no clue what they mean. Then i tried understanding them first with their use in Binary Tree. So i want to know

1)What does the BFS and DFS mean in Binary Tree and how to and where to use them?

2)Is the the same BFS DFS used in Hopcroft-karp algorithm?

3)In simple words/code, How the hopcroft -karp algorithm basically finds the max matching.

The Only thing i understood about Binary tree is how to implement it using structure…is there another better way?

If i am going off the topic for what is needed for kamehameha…please guide me

Thanks

2

Please help me out…I am stuck at this for 2 days now…just can’t understand it

3

Hello,

At last, a coder takes THE EXACT APPROACH I DID!!!

In my point of view you are doing it (almost) right, as you try to focus on concepts instead of specific problems, which is a great way to evolve.

I can help you with your first question:

BFS and DFS are graph traversal algorithms and binary trees can be seen as a particular kind of graph :smiley:

You can read more on a tutorial I wrote, [here][1].

About the Hopcroft-Karp, I still can’t help you out as I don’t know it myself (yet!)

Best regards,

Bruno
[1]: http://discuss.codechef.com/questions/17801/introduction-to-graphs-definitions-traversal-depth-first-search

1 Like
4

First of all I’ve read your short tutorial about graphs. Now i understand what is DFS , thank you very much.
Still wanna learn the HK algorithm if someone could explain that would be very helpful
Thanks

5

Can someone please explain me the hofcroft-karp algorithm…I can’t find proper explanation anywhere, all i can find is only the codes with no explanations of defined functions and variables used neither the proper method