Описание алгоритма поиска центра графа

Центром является любая вершина х с наименьшим значением МВВ (х) (максимальное расстояние вершина-вершина), т. е. центр — это любая вершина х, такая, что расстояние от нее до наиболее отдаленной вершины минимально.

МВВ (х) =min{МВВ (i)}.

Центр отыскивается как один из элементов матрицы DN, значение i, j-го элемента которой — di, j есть кратчайшее расстояние от вершины i к вершине j. Элементы матрицы могут быть вычислены с помощью алгоритма Флойда или алгоритма Данцига.

Опишем их:

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

Алгоритм Данцига — этот алгоритм отличается от алгоритма Флойда последовательностью выполнения действий. Перенумеруем все вершины графа от 1 до n целыми числами и обозначим через di, jm длину пройденного пути из i в j где в качестве промежуточных использованы первые m вершин графа. Матрица Dm длин кратчайших путей имеет здесь размерность m*m.

Вернемся теперь к описанию алгоритма поиска центра графа:

Максимальное расстояние МВВ (i) от вершины i до любой вершины графа является элементом i-й строки матрицы DN, имеющим максимальное значение. Центром является произвольная вершина х с наименьшим среди всех вершин графа значением МВВ (х), т. е. центр — это произвольная вершина х, которой соответствует строка матрицы DN, содержащая элемент с наименьшим максимальным значением.

Если описать алгоритм поиска центра коротко, то он будет выглядеть следующим образом.

• 1. находим D0 — матрицу, элементами которой являются ai, j — длины кратчайших дуг.
• 2. Ищем DN — матрицу длин кратчайших расстояний по Флойду или Данцегу.
• 3. Определяем МВВ (i) для каждой вершины графа.
• 4. Из всех МВВ (i) выбираем минимальное соответствующая вершина и будет центром.

Пример:

Допустим нам необходимо найти центр графа представленного на рисунке:

Рис 1. Исходный граф

Составим матрицу длин кратчайших дуг между каждой парой вершин — D0, в случае, если дуги между вершиной i и j не существует, элементу ai, j матрицы присваивается значение ?. Матрица D0:

C помощью алгоритма Флойда или Данцега получаем матрицу длин кратчайших путей между каждой парой вершин графа:

Теперь, основываясь на полученной нами матрице длин кратчайших путей, найдем МВВ (i) для каждой вершины графа МВВ (i)=max{di, j}.

МВВ (1)=max{d (1, j)}=152.

МВВ (2)=max{d (2, j)}=122.

МВВ (3)=max{d (3, j)}=145.

МВВ (4)=max{d (4, j)}=133.

МВВ (5)=max{d (5, j)}=197.

МВВ (6)=max{d (6, j)}=197.

МВВ (7)=max{d (7, j)}=104.

МВВ (8)=max{d (8, j)}=200.

Центром графа является такая вершина x, для которой МВВ (x)=min{МВВ (i)}. Минимальное значение имеет МВВ (7)=104, а это значит, что вершина 7 является центром графа.

Описание исходного кода программы

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

Кроме созданных самостоятельно классов были использованы также классы, находящиеся в стандартной библиотеке, среди которых:

java.io.* - который содержит классы для работы с потоком ввода/вывода.

java.util.Scanner — который содержит классы для работы с вводом/выводом чтением из файла и работы с ним.

Приведем весь исходный код программы:

файл GraphCenterFinder.java

public class GraphCenterFinder {.

//Метод должен принимать в качестве параметра имя файла.

//с матрицей расстояний исходного графа.

//вызов: java GraphCenterFinder имя_файла.txt.

public static void main (String[] args) {.

//Проверка правильности указания параметров.

switch (args.length) {.

case 0:

System.out.println («Ошибка! Не указано имя файла.»);

System.exit (-1);

break;

case 1:

break;

default: граф множество вершина код.

System.out.println («Неверно указаны параметры для запуска программы.»);

System.exit (-1);

break;

}.

String fileName = args[0];

Graph graph = new Graph («Graph», fileName);

graph.findGraph ();

graph.getGraph ();

graph.floydAlgorithm ();

graph.CenterFinder ();

}.

}.

файл Graph.java

public class Graph {.

//Имя файла, содержащего граф.

private String fileName;

private String name;

private int vertexCount; //Количество вершин в графе.

private int[][] graph; // Матрица с исходным графом.

private int[][] shortcut; //Матрица кратчайших расстояний.

/*eccentricity — Массив эксцентриситетов.

* в этом одномерном массиве опеределено значение от наиболее удаленной вершины графа.

* до текущей вершины.

* Сама удаленная вершина не так важна, неоходимо знать только расстояние.

* */.

private int eccentricity[];

/*переменная minEccentricity собственно и является искомой.

* величиной обозначающей радиус графа. Вершины, значение которых совпадает с данной переменной.

• * являются центрами графа.
• * */

private int minEccentricity;

//Конструктор

Graph (String nameParam, String fileNameParam){.

this.name = nameParam;

this.fileName = fileNameParam;

}.

public void findGraph () {.

char ch;

try (Scanner fileScanner = new Scanner (new File (fileName))) {.

do {.

ch = fileScanner. next ().charAt (0);

if (ch == '#') {.

if (fileScanner.hasNextInt ()) {.

vertexCount = fileScanner. nextInt ();

//Создание массива и его обнуление.

graph = new int[vertexCount][vertexCount];

for (int i = 0; i < vertexCount; i++).

for (int j = 0; j < vertexCount; j++).

graph[i][j] = 0;

//Чтение матрицы графа из файла.

for (int i = 0; i < vertexCount; i++){.

for (int j = 0; j < vertexCount; j++) {.

if (fileScanner.hasNextInt ()){.

graph[i][j] = fileScanner. nextInt ();

}.

else {.

if ('-' == fileScanner. next ().charAt (0)).

graph[i][j] = Integer. MAX_VALUE/100;//Примем бесконечность за сотую долю максимального значения, чтоб не иметь проблем при сложении максимальных чисел.

}.

}.

}.

}.

}.

} while (fileScanner.hasNext ());

} catch (FileNotFoundException e) {.

System.err.println («Ошибка! Данный файл не найден»);

System.exit (-1);

}.

}.

public void getGraph () {.

System.out.println («Исходный граф:»);

for (int i = 0; i < vertexCount; i++){.

for (int j = 0; j < vertexCount; j++){.

if (graph[i][j] == Integer. MAX_VALUE/100) {.

System.out.print («- «);

}.

else.

System.out.print (graph[i][j] + ««);

}.

System.out.println ();

}.

}.

//Алгоритм Флойда-Уоршера для нахождения минимального расстояния между всеми вершинами.

public void floydAlgorithm () {.

shortcut = new int[vertexCount][vertexCount];

for (int i = 0; i < vertexCount; i++).

for (int j = 0; j < vertexCount; j++).

shortcut[i][j] = graph[i][j];

for (int k = 0; k < vertexCount; k++).

for (int i = 0; i < vertexCount; i++).

for (int j = 0; j < vertexCount; j++).

if (shortcut[i][k] ≠ 0 && shortcut[k][j] ≠ 0 && i ≠ j).

if (shortcut[i][k] + shortcut[k][j] < shortcut[i][j] || shortcut[i][j] == 0).

shortcut[i][j] = shortcut[i][k] + shortcut[k][j];

System.out.println («Таблица кратчайших расстояний между вершинами, найденная согласно алгоритму Флойда-Уоршера»);

for (int i = 0; i < vertexCount; i++){.

for (int j = 0; j < vertexCount; j++).

System.out.print (shortcut[i][j] + ««);

System.out.println ();

}.

}.

//Функция нахождения наибольших расстояний от вершин.

public void CenterFinder () {.

int max;

eccentricity = new int[vertexCount];

System.out.println («Расстояние от каждой из вершин до другой наиболее удаленной (ых) вершин (ы)»);

for (int i = 0; i < vertexCount; i++){.

max = shortcut[i][0];

for (int j = 0; j < vertexCount; j++){.

if (shortcut[i][j] > max) {.

max = shortcut[i][j];

}.

}.

eccentricity[i] = max;

System.out.println («MBB (» + (i+1) + «) = «+ eccentricity[i]);

}.

minEccentricity = eccentricity[0];

for (int i = 0; i < vertexCount; i++){.

if (eccentricity[i] < minEccentricity).

minEccentricity = eccentricity[i];

}.

System.out.println («Расстояние от центра графа до наиболее удаленных (ой) вершин (ы) — «+ minEccentricity);

/*Минимальный эксцентриситет может быть не у одной вершины, а у нескольких.

• * В таком случае все вершины, которые имеют такое же значение являются центрами графа
• * */

System.out.print («Центром графа явля (ю)тся вершина (ы): «);

for (int i = 0; i < vertexCount; i++){.

if (eccentricity[i] == minEccentricity).

System.out.println ((i+1) + ««);

}.

}.

}.

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

В первой строке буква, которая определяет, что за ней действительно следует число. Во второй строке должно находится число, обозначающее количество вершин в матрице.

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

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