CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
user1372984
user1372984

Reputation:

Efficiently find the depth of a graph from every node

I have a problem where I am to find the minimum possible depth of a graph which implies that I have to find the maximum depth from each node and return the least of them all. Obviously a simple DFS from each node will do the trick but when things get crazy with extremely large input, then DFS becomes inefficient (time limit). I tried keeping the distance of each leaf to the node being explored in memory to but that didn't help much.

How do I efficiently find the minimum depth of a very large graph. It is worthy of note that the graph in question has no cycle.

Upvotes: 7

Views: 10157

Answers (2)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

To find the graph centre/center of an undirected tree graph you could:

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

The node/nodes deleted in the last stage of the algorithm will be the graph centres of your tree.

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

Upvotes: 10

Vincent van der Weele
Vincent van der Weele

Reputation: 13177

What you seem to be looking for is the diameter / 2. You could compute the diameter of a tree as below and call it as findDiameter(n, null), for an arbitrary node n of the 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's the max depth of the neighbors
    diameter = max(max(di), 1 + max(de) + oneButLargest(de))

All you need to do is in the loop over the neighbors keep track of the largest diameter and the 2 largest depths.

Upvotes: 2

Related Questions