Aspergillus's blog

Tree problem help
By Aspergillus, history, 11 months ago, In English

I am new to graph theory and need some help. I have an undirected tree with a few coloured nodes. My task is to calculate the minimum distance from each node to any of the coloured nodes in $$$O(N)$$$. N is the number of nodes. The number of coloured nodes may be up to N.

My solution: Initialise an array of size N with infinity as the elements, this will represent my min distance array, say $$$A$$$. Change $$$A[i] = 0$$$, if $$$i$$$ is a coloured node. Run a dfs from each coloured node and each recursive call of the dfs ends if it either reaches a leaf or a node with $$$A[i]$$$ less than or equal to that of the parent. Store the distances on A along the way.

But I suspect that the complexity of this approach is $$$O(N^2)$$$, consider a tree with a root and many children, and let these children have many more single child each, and let the leaves be coloured, kind of like a flower. Since I don't know of a problem that is based on this, I cannot verify anything.

If anyone can prove if it's $$$O(N)$$$ or $$$O(N^2)$$$ then please help me. If it has bad complexity or downright wrong then please help me with a solution.

Another approach I though of was to simultaneously run a dfs from all the coloured nodes and end a recursive call of each node if it's reached a previously reached node, kind of like a radiation from the coloured nodes. But I don't even know if that's possible for me to implement.

help pls

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You just need to run multisource bfs from the coloured node

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

    Thanks, I will read up on it. But I wonder if there is a dfs version to do a multi source start.

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your current implementation works in $$$O(n^2)$$$, indeed.
Consider the chain tree, where colored nodes are $$$(0, 1, \dots, n / 2)$$$.
If you run dfs sequentially from $$$0, 1, \dots, n - 2$$$, then $$$i$$$th dfs will visit $$$n - i$$$ nodes, which leads to $$$O(n^2)$$$.

What do you need is a multi-source bfs, which looks like: 

// Initializing variables for bfs:
for v in colored_nodes:
  distance[v] = 0
  queue.push(v)
// Ordinary bfs code
...

It is essentialy same as ordinary bfs, except of having more than one source node. But, obviously, it still works in $$$O(n)$$$

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

    Thank you for the detailed answer. I will read up on it. But I wonder if the same thing (multi source bfs) can be done using a dfs, which I didn't understand how to implement as I said the last paragraph.

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

      To be honest, I neither do know, how to do it with DFS, nor I see any benefits over BFS — the fact that problem requires computing the length of the shortest paths itself makes me to think about BFS.

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

        I don't see any benefit either, I was just wondering. Also I didn't understand the counterexample. If let's say the chain tree is 0 1 2 3 4 5, and the nodes 0 1 and 2 are coloured, and I dfs from 0, then 1 then 2, the dfs at 0 ends at 1, 1 ends at 2 and 2 runs till 5, didn't it run 5 times only? Also in the flower like tree example, I think the dfs visited only 2n nodes. When I encounter a node with smaller value stored, I'm leaving out its entire subtree. Did I miss anything?

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

          Well, talking about subtrees makes sense only if we talk about rooted trees. To understand your point of view: we assume that the tree is rooted on vertex $$$0$$$?

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

            We will arbitrarily root the tree, let's say at 0.

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

              Then the tree from the example above should look like:
              $$$n$$$
              ($$$0$$$, $$$1$$$)
              ($$$1$$$, $$$2$$$)
              $$$\dots$$$
              ($$$n / 2 - 1$$$, $$$n / 2$$$)
              ($$$n / 2$$$, $$$n - 1$$$)
              ($$$n - 1$$$, $$$n - 2$$$)
              ($$$n - 2$$$, $$$n - 3$$$) $$$\dots$$$
              ($$$n / 2 + 1$$$, $$$n / 2$$$)
              And colored nodes are ($$$n / 2 + 1, n / 2 + 2, \dots, n - 1$$$)
              So, if you do dfs sequentially from $$$n / 2 + 1, n /2 + 2, \dots, n - 1$$$, it will work in quadratic time because of the same argument as before — the difference is that skipping the entire subtree does not help, because all nodes which are visited more than once are ancestors of all colored nodes, not descendants.

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

                Got it. Skipping the subtree does not help in this case. I deeply appreciate your efforts. Thank you very much <3.

                → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can solve this problem by using BFS but instead of putting one root in your queue for start you can put all colored vertices in the queue for start and set the height of all of them to zero. we call this method multiBFS.

in this method, every color vertex that reaches an uncolored vertex first sets the uncolored vertex height.

You can do this method in Dijkstra too.

→ Reply