Given an acyclic undirected unweighted connected graph, find its representation as a tree with the least height. Brute force is O(n^2). Come up with an O(n) solution.
Approach:
1. All the edges are of weight "1" in the above graph.
2. Pick a random Node in the above Graph, Say we pick "C", now do BFS and calculate the farthest Node from C.
2. The Farthest Node from "C" would come to be "F" and "G" - Both of them "3" units away.
3. Lets Pick one of the Nodes from "F" & "G" above, say "F".
4. Now do BFS starting from "F" and calculate the farthest node from "F" - here we are calculating the "Diameter of the Graph".
5. After we are done with BFS above, the farthest Node from "F" would come out to be Node "B", which would be 4 units aways. - "4" is the diameter of the graph, lets call it D.
6. Now calculate d = D/2 = 4/2 = 2.
7. Find the nodes which are d (2 units) distance away from F along the route of F => B. Here we get Node "D" as the candidate which satisfies our criteria.
8. Now "D" is the root of the tree that we set out to create, do a BFS starting from D, nodes 1 unit away are its first level children and so on..
Finally, the tree would look like:
Terminologies:
Diameter of the Graph: maximum distance between any two vertices, here the distance is the length of the shortest walk; therefore, the diameter is the longest of the shortest walks.
Building binary tree with following random values:
30 38 4 32 14 9 42 2 85 6
Inorder traversal of the binary tree:
2 4 6 9 14 30 32 38 42 85
Diameter of BinaryTree: 8
Approach:
2. Pick a random Node in the above Graph, Say we pick "C", now do BFS and calculate the farthest Node from C.
2. The Farthest Node from "C" would come to be "F" and "G" - Both of them "3" units away.
3. Lets Pick one of the Nodes from "F" & "G" above, say "F".
4. Now do BFS starting from "F" and calculate the farthest node from "F" - here we are calculating the "Diameter of the Graph".
5. After we are done with BFS above, the farthest Node from "F" would come out to be Node "B", which would be 4 units aways. - "4" is the diameter of the graph, lets call it D.
6. Now calculate d = D/2 = 4/2 = 2.
7. Find the nodes which are d (2 units) distance away from F along the route of F => B. Here we get Node "D" as the candidate which satisfies our criteria.
8. Now "D" is the root of the tree that we set out to create, do a BFS starting from D, nodes 1 unit away are its first level children and so on..
Finally, the tree would look like:
Terminologies:
Diameter of the Graph: maximum distance between any two vertices, here the distance is the length of the shortest walk; therefore, the diameter is the longest of the shortest walks.
Diameter of a Tree
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).
The diameter of a tree T is the largest of the following quantities:
* the diameter of T’s left subtree
* the diameter of T’s right subtree
* the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)
* the diameter of T’s right subtree
* the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)
Code output:
Building binary tree with following random values:
30 38 4 32 14 9 42 2 85 6
Inorder traversal of the binary tree:
2 4 6 9 14 30 32 38 42 85
Diameter of BinaryTree: 8
Question says "Acyclic graph" and your example has a cycle! Am I not understanding it correctly?
ReplyDelete