Efficiently find the depth of a graph from every node
algorithm, graph, graph-algorithm
Solution
To find the graph centre/center of an undirected tree graph you could:
- Do a DFS to find a list of all leaf nodes O(n)
- Remove all these leaf nodes from the graph and note during the deletion which new nodes become leaf nodes
- 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).
Problem
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.