All geek questions in one place

Effectively find chart depth from each node

I have a problem where I have to find the minimum possible depth of the graph, which means that I have to find the maximum depth from each node and return the smallest of all. Obviously, a simple DFS from each node will do the trick, but when everything gets crazy with an extremely large input, DFS becomes ineffective (time limit). I tried to keep the distance of each sheet to the node, which was studied in memory, but this did not help much.

How to effectively find the minimum depth of a very large chart. It is worth noting that the chart in question does not have a cycle.

+6
source share
2 answers

To find the center of a graph / center of an undirected tree, you can:

  • Make DFS to find the list of all leaf nodes O (n)
  • Remove all of these leaf nodes from the graph and note during deletion which new nodes become leaf nodes.
  • Repeat step 2 until the graph is completely deleted.

node / nodes removed at the last stage of the algorithm will be the centers of the graph of your tree.

Each node is deleted once, so this whole process can be performed in O (n).

+9
source

What you seem to be looking for is a diameter of / 2. You can calculate the diameter of the tree as shown below and call it findDiameter(n, null) for an arbitrary node n tree.

 public findDiameter(node n, node from) returns <depth, diameter> // apply recursively on all children foreach child in (neighbors(n) minus from) do <de, di> = findDiameter(child, n) // depth of this node is 1 more than max depth of children depth = 1 + max(de) // max diameter either uses this node, then it is 1 + the 2 largest depths // or it does not use this node, then it the max depth of the neighbors diameter = max(max(di), 1 + max(de) + oneButLargest(de))

All you have to do is loop over the neighbors, tracking the largest diameter and two greatest depths.

0
source

Source: https://habr.com/ru/post/952084/

More articles:


All Articles