Today I noticed some interesting facts about dfs and bfs algorithms.
Let's consider a complete graph consisting of N vertices. Do bfs and dfs algorithms over this graph. You may be surprised but the spanning tree formed by BFS algorithm looks like a sun so I called this tree "Solnyshko-tree" while the tree formed by DFS algorithms looks like a line so I called it "Bamboooo-tree".
For a better understanding I suggest you to have a look at provided pictures.
Hope you find this topic interesting and useful. Thanks for attention and good luck on the upcoming contest!
Спасибо, кэп!
Почему я так ору
"Solnyshko-tree" is called star graph. http://mathworld.wolfram.com/StarGraph.html
Some japanese call star graph "Uni"(ウニ). Uni is a Japanese word for sea urchins. (cf: http://agc009.contest.atcoder.jp/tasks/agc009_d#)
Oh, sorry, I didn't know about the star graph. But I think my discovery is still useful for science.
Anyway thanks for informing about the star graph
:|
This is the answer to our everyday questions.
Are you joking ? :/
You see sth funny there, huh?
WOW. I never noticed that. Thanks for sharing your wisdom!!!!!
Is this fact correct about the graphs with more than 7 vertices too?
Of course yes, it is correct for every integer N > 0. You can prove it by induction
Man, for N=1 it looks like a put out sun, I'm not buying this.
This is neither about sun nor line, it is about the structure of the spanning tree formed by bfs or dfs in a complete graph. N=1 is a special case
Ok but for N=2 the so-called sun looks like a bamboo. What u gonna say now? Is every single N a special case of its own? Why am I even trusting you?!?!?!
Hmm, I don't see anything wrong here. For example, in my country bamboo is associated with the Sun. No Sun — no bamboo
I don't care about the zodiac, we are talking about competitive programming here.
I don't mention any astrology here. As I said before, my topic is not about suns, lines, bamboos etc. I've just wanted to share with codeforces community my observations about the structure of these trees (not about pictures), but these comments are killing me
Nice drawing!
Clear explanations!
Very exciting topic!
Well done.
No!!.
He/She copied this topic from this strong judge!!.
Thanks.
Cmon guys, what's wrong with this post? Sorry if it is a well-known fact but I didn't see it yet. Can you provide a link with this fact if it exists or explain your downvotes otherwise?
It's too advanced and complicated for this website
I don't see it complicated and some coders understand my observation. So guys, why are you laughing at me?
if this blog wasn't a new idea, but it was a new perspective! so it was appreciable! thanks for writing this blog! keep up writing your new thoughts on cf :)
Ohh man, thank you! I've already thought I'm shitposting here :(
Wrong observation. That is a new moon, not line.
how is bambooa a tree its a grass