search for "servers" and shortist path

I can't come up with a solution for this problem. I have list of components(servers):

2 - 8

8 - 3

3 - 9

..... so this mean that theese servers are linked and you can visit all servers starting from any other - all are linked through other servers. The question is how to find out which one/ones servers has the shortest way(step count) to visit all others. Each link is considered as 1 step.

Example:

1 - 2

2 - 7

2 - 8

2 - 9

2 - 3

3 - 4

4 - 5

4 - 6

Answer: server number 3 needs 2 steps max to visit all ot开发者_如何学Cher servers.

Which is the best solution for this? Which data structure to choose for saving/reading data from file where they are listed as in example?

P.S This task will be developed in C++

What you want is what is called the center of the graph. Your algorithm text probably discusses it along with all pairs shortest path algorithms (Floyd-Warshall and Johnson's algorithm). Here is a brief discussion

You absolutely want to represent this data as a graph. Specifically you want a distance matrix.

You can fill this matrix with the Floyd-Warshall algorithm.

Basically for a fixed number of servers, N, do (in not quite code):

int dist[N][N];
fill(dist, N + 1);

for (i = [0,N)) dist[i][i] = 0;

foreach (edge e) dist[e.first][e.second] = dist[e.second][e.first] = 1

for (k = [0,N))
for (j = [0,N))
for (i = [0,N))
    dist[j][i] = min(dist[j][i], dist[j][k] + dist[k][i])

Then dist[i][j] holds the distance from server i to server j. With the filled out distance matrix it is trivial to determine the center of the graph.

A basic graph like this would be represented by a two dimensional array. Columns representing each server, rows representing distance to others your example would be (initialize to -1 to represent an unreachable state, thanks Chris)

   1  2  3  4  5  6  7  8  9
1  0  1 -1 -1 -1 -1 -1 -1 -1 
2  1  0  1 -1 -1 -1  1  1  1
3 -1  1  0  1 -1 -1 -1 -1 -1
4 -1 -1  1  0  1  1 -1 -1 -1
5 -1 -1 -1  1 -1 -1 -1 -1 -1
6 -1 -1 -1  1 -1 -1 -1 -1 -1
7 -1  1 -1 -1 -1 -1 -1 -1 -1
8 -1  1 -1 -1 -1 -1 -1 -1 -1
9 -1  1 -1 -1 -1 -1 -1 -1 -1

Then fill in the twos, Eg. for column 1 and row 1, put in 2 where the column 2 has a one (disregard 1) i.e. 3 7 8 and 9. So for first column/row

   1  2  3  4  5  6  7  8  9
1  0  1  2 -1 -1 -1  2  2  2 
2  1  0  1 -1 -1 -1  1  1  1
3  2  1  0  1 -1 -1 -1 -1 -1
4 -1 -1  1  0  1  1 -1 -1 -1
5 -1 -1 -1  1 -1 -1 -1 -1 -1
6 -1 -1 -1  1 -1 -1 -1 -1 -1
7  2  1 -1 -1 -1 -1 -1 -1 -1
8  2  1 -1 -1 -1 -1 -1 -1 -1
9  2  1 -1 -1 -1 -1 -1 -1 -1

Repeat for three. Look at columns that has the distance 2 (3,7,8,9). Rinse repeat.

As for file format, value pairs in rows should be fine.