A graph central nodes they have the shortest path to all other nodes. Therefore, they are useful in many scenarios including for example building the minimum height tree (assuming the graph is a tree!)
How to find the graph center:
- BFS
- Add the leaves (use the
in_degreematrix) - At each step, reduce the degree of the next nodes
- When a node has
in_degree0, add it to the queue
- When a node has
- When the queue is long 1 or 2, it contains the centers
Why only 1 or 2?
In a Tree there is exactly one path between any pair of nodes.
- Because of this unique path property, as you remove leaves layer by layer, the tree will collapse inward toward its center. The structure of the tree will always collapse into either:
- 1 central node if the tree has an odd number of levels.
- 2 adjacent central nodes if the tree has an even number of levels.
This is guaranteed by the fact that in a tree, each node has only one path connecting it to any other node. This ensures that as you peel away the leaves, the remaining structure will always shrink symmetrically toward the center, but it can never result in 3 or more equidistant central nodes.