The central point of graph

Question

I'm having some trouble thinking about how to locate the central point of a graph; that is, a node on a graph which minimizes the maximal distance to all the other ones.

For example:

Lets say I have a graph with 3 nodes, arranged in a line (like 1-2-3).

Obviously, it's easy to see that the central point of this graph is 2. How would I get around to implementing something like that though?

The only algorithms that I know is BFS/DFS/Prim's/ and Kruskal's. Prim's and Kruskal's algorithms don't really apply in this case. I'm thinking that I need to use BFS here? The only issue is, doesn't BFS return a different order depending on which node you start at?

Answer 1

For rather dense graphs:

1. Build all shortest paths matrix with Floyd-Warshall algorthm
2. Find maximum value in each line - this is eccentricity of corresponding vertice (node)
3. Choose vertices with minimal eccentricity - they are central nodes (and minimal eccentricity is graph radius)

complexity O(V^3) (with small constants)

If graph is sparse, you can use BFS from each vertice or Johnson's algorithm

(O(V^2+ V*E), O(V^2*logV + V*E))

FYE:

0 1 2   //ecc = 2
1 0 1   //ecc = 1 - central point
2 1 0   //ecc = 2

If you work with tree (as MST has been mentioned in vanished comment) - there is faster method:

1. one BFS from any vertice
2. another BFS from the farthest vertice found
3. get middle vertice(s) in the longest path of the second BFS

O(V + E)