CODEWITHSUNDEEP
algorithmgraph
docaholic
docaholic

Reputation: 625

The central point of graph

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?

Upvotes: 5

Views: 2512

Answers (2)

SparkAndShine
SparkAndShine

Reputation: 18007

The Python module NetworkX provide such API center(G, e=None). Refer to its source code here for the implementation.

Take the Florentine families graph as an example, the center nodes are colored in red.

enter image description here

import networkx as nx

G = nx.florentine_families_graph()
center_nodes = nx.center(G)

Upvotes: 0

MBo
MBo

Reputation: 80187

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)

Upvotes: 3

Related Questions