поиск "серверов" и краткий путь

Question

Я не могу найти решение этой проблемы. У меня есть список компонентов (серверов):
2 - 8
8 - 3
3 - 9
..... Таким образом, это означает, что эти серверы связаны, и вы можете посещать все серверы, начиная с любого другого - все связаны через другие серверы. Вопрос в том, как узнать, какие серверы имеют самый короткий путь (количество шагов) для посещения всех остальных. Каждая ссылка считается одним шагом.
Пример:
1 - 2
2 - 7
2 - 8
2 - 9
2 - 3
3 - 4
4 - 5
4 - 6
Ответ: серверу № 3 нужно максимум 2 шага, чтобы посетить все остальные серверы.

Какое решение лучше для этого? Какую структуру данных выбрать для сохранения / чтения данных из файла, в котором они перечислены, как в примере?

P.S Эта задача будет разработана на C ++

Answer 1

То, что вы хотите, это то, что называется центром графика.Ваш текст алгоритма, вероятно, обсуждает это вместе со всеми парами алгоритмов кратчайшего пути (алгоритм Флойда-Варшалла и Джонсона). Здесь - краткое обсуждение

Answer 2

Вы абсолютно хотите представить эти данные в виде графика.В частности, вам нужна матрица расстояний .

. Вы можете заполнить эту матрицу алгоритмом Флойда-Варшалла.

В основном для фиксированного числа серверов, N, do (вне совсем код):

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])

Тогда dist[i][j] содержит расстояние от сервера i до сервера j.С помощью заполненной матрицы расстояний тривиально определить центр графика.

Answer 3

Базовый граф, подобный этому, будет представлен двумерным массивом.Столбцы, представляющие каждый сервер, строки, представляющие расстояние до других, в вашем примере (инициализируйте -1, чтобы представить недостижимое состояние, спасибо Крису)

   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

Затем заполните двойки, например.для столбца 1 и строки 1 введите 2, где столбец 2 имеет единицу (без учета 1), то есть 3 7 8 и 9. Таким образом, для первого столбца / строки

   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

Повторите для трех.Посмотрите на столбцы, у которых есть расстояние 2 (3,7,8,9).Повторите полоскание.

Что касается формата файла, пары значений в строках должны быть в порядке.