VPF::Алгоритм поиска радиуса, центра, диаметра в графе

bobbyserf

Дата 15.4.2015, 11:48 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 4.12.2014

Репутация: нет
Всего: нет

Код


void Graph::PrintAdjacencyMatrix(){       //вывод матрицы смежности
    wcout << L"Матрица смежности:" <<endl;
    for (int i = 0; i < countNodes_; i++)
    {
        for (int j = 0; j < countNodes_; j++)
        {
            int h = adjacencyMatrix_[i][j];
            cout << adjacencyMatrix_[i][j] << " ";
        }
        wcout << endl;
    }
}

Graph::~Graph(void){   //удаляем из памяти 

    for (int i = 0 ; i < countNodes_; i++)
                 delete[] adjacencyMatrix_[i];
    delete[] adjacencyMatrix_;
}

void Graph::CenterRadiusDiameter()
{
    ofstream offile("of.txt");
    int **edge = new int *[countNodes_];  //преобразуем матрицу смежности в расстояния
    for (int i = 0; i < countNodes_; i++)
        edge[i] = new int [countNodes_];
    for (int i = 0; i < countNodes_; i++)
        for (int j = 0; j < countNodes_; j++) {
            edge[i][j] = adjacencyMatrix_[i][j];
            if (!edge[i][j]) 
                edge[i][j] = 100000;//машинная бесконечность
        }//Находим кратчайшие расстояния между всеми парами вершин
        for (int k = 0; k < countNodes_; k++)           //алгоритм Флойда
            for (int i = 0; i < countNodes_; i++)
                for (int j = 0; j < countNodes_; j++)
                    if (i != j)
                        edge[i][j] = Min(edge[i][j], edge[i][k] + edge[k][j]); //На каждом шаге алгоритм генерирует матрицу 
        //мат. содержит длины кратчайших путей между всеми вершинами графа. Перед работой алгоритма матрица заполняется длинами рёбер графа.
        wcout << L"Расстояния: " << endl;     
        for (int i = 0; i < countNodes_; i++) {
            for (int j = 0; j < countNodes_; j++) {
                if (edge[i][j] == 100000) 
                    edge[i][j] = 0;
                cout << edge[i][j] << " ";    //вывод матрицы расстояния
            }
            cout << endl;
        }
        int radius, max, diameter;
        int *ecc = new int [countNodes_];//эксцентриситет
        int *rad = new int [countNodes_];
        radius = 100000;
        diameter = -1;
        for (int i = 0; i < countNodes_; i++) {
            rad[i] = ecc[i] = 0;
            max = -1;
            for (int j = 0; j < countNodes_; j++) {
                if (i!=j)
                {
                    if(edge[i][j] > max)//если ребро > max
                    {
                        max = edge[i][j];//то max присваиваем значение ребра
                    }
                    if(edge[i][j] > diameter)//если ребро > диаметра
                        diameter = edge[i][j];//то диаметру присваиваем значение ребра
                }
            }
            ecc[i] = max;    //расстояние от этой (т.е. от центра) вершины до самой удаленной
            if (max<radius)
            {
                radius  = max; // присваиваем значение радиусу
            }
        }//Если эксцентриситет вершины равен радиусу графа то эта вершина центр графа, выводим её.
        int j = 0;   //кол-во вершин центра
        for(int i = 0; i < countNodes_; i++)
        {
            if(radius == ecc[i])
                rad[j++] = i;
        }

Часть кода, помогите в ней разобраться. Проврьте правильно я понял и описал.
Особенно вот эту часть обьясните пожалуйста.

Код


 ecc[i] = max;    //расстояние от этой (т.е. от центра) вершины до самой удаленной
            if (max<radius)
            {
                radius  = max; // присваиваем значение радиусу
            }

rudolfninja

Дата 15.4.2015, 12:12 (ссылка)

(голосов:1)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 341
Регистрация: 19.2.2013
Где: г. Минск

Репутация: 1
Всего: 6

Цитата

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

В данном случае max - это максимальное расстояние от центра до вершины. Поэтому определяется наименьшее расстаяние из максимальных.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »