danger1200's blog

Graph Theory [Interesting Fact]
By danger1200, 8 years ago, In English

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!

  • Vote: I like it
  • -69
  • Vote: I do not like it

Comments Comments (25)
| Write comment?
»
8 years ago, # |
  Vote: I like it -25 Vote: I do not like it

"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#)

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it -26 Vote: I do not like it

    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

    → Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This is the answer to our everyday questions.

→ Reply
»
8 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Are you joking ? :/

→ Reply
»
8 years ago, # |
  Vote: I like it +47 Vote: I do not like it

WOW. I never noticed that. Thanks for sharing your wisdom!!!!!

→ Reply
»
8 years ago, # |
  Vote: I like it +83 Vote: I do not like it

Is this fact correct about the graphs with more than 7 vertices too?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Of course yes, it is correct for every integer N > 0. You can prove it by induction

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Man, for N=1 it looks like a put out sun, I'm not buying this.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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?!?!?!

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Hmm, I don't see anything wrong here. For example, in my country bamboo is associated with the Sun. No Sun — no bamboo

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I don't care about the zodiac, we are talking about competitive programming here.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                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

                → Reply
»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Nice drawing!

Clear explanations!

Very exciting topic!

Well done.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It's too advanced and complicated for this website

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't see it complicated and some coders understand my observation. So guys, why are you laughing at me?

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ohh man, thank you! I've already thought I'm shitposting here :(

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wrong observation. That is a new moon, not line.

→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

how is bambooa a tree its a grass

→ Reply