Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 32, средняя оценка - 4.88
amor1k
Студент
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
#1

Центр графа - C++

09.11.2011, 17:04. Просмотров 4640. Ответов 22
Метки нет (Все метки)

Дана матрица смежности. Найти максимальное расстояние в графе.
Пол дня уже мучаюсь, искал в гугле, сам пытался, но ничего не получается... просто тупик...
Код вылаживать не буду, так как он не правильный. Просто расскажу, как я хочу сделать.
Беру первую вершину, и делаю ее текущей. Если существует ребро между текущей и другой вершиной, делаю ее текущей и иду дальше. При этом считаю все расстояния, а в конце сравниваю и ищу максимум. Но что-то все равно не получается...
Помогите сделать программу, или хотя бы объясните подробно что и как делать!!!

Добавлено через 1 час 40 минут
помогите
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.11.2011, 17:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Центр графа (C++):

заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь - C++
Задание: заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь. Помогите написать...

Центр тяжести - C++
Горю! По координатам вершин многоугольника требуется найти координаты его центра тяжести. Стороны многоугольника друг с другом не...

Центр симметрии - C++
Совсем не могу написать код. Проверить или известный квадратный массив имеет центр симметрии. подскажите

Центр тяжести - C++
Система из n материальных точек в пространстве задана с помощью последовательности действительных чисел x1, y1, z1, p1, x2, y2, z2, p2,...

Центр орграфа, классы - C++
помогите с конструктором и деструктором) Дан файл, первой строкой в файле является размерность матрицы, остальное является самой...

Определить радиус и центр окружности.... - C++
Здравстуйте!!!! Помогите пожалуйста..... Задача: Определить радиус и центр окружности, проходящей по крайней мере через три различные...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
LosAngeles
Заблокирован
09.11.2011, 18:01 #2
1) с помощью алгоритма флойда найди расстояния между вершинами
2) найди вершины с минимальным эсцентриситетом. То есть в полученной таблице в каждой строке ищешь наибольшую циферку, а среди них находишь минимум
насколько я понимаю все вершины с минимальными эксцентриситетами - центральные, их совокупность является центром графа. Алгоритм флойда наверняка можно на вики подсмтореть, только это непоное накзвание, там ещё один мужик через дефис, флойда-маршала кажись алгоритм. Ну а матрицу просмотреть это азы, надеюсь тут нет затруднений

Добавлено через 3 минуты
вот он собственно, в конце даже ссылка есть на С++ реализацию, так что тебе и писать нечего не придётся)
http://ru.wikipedia.org/wiki/%D0%90%...B8.D1.82.D0.BC
0
amor1k
Студент
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
09.11.2011, 21:38  [ТС] #3
сделал тип такого... дальше незнаю что делать... помогите
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int **d = new int *[n];
    for(int i = 0; i < n; i++)
        d[i] = new int [n];
    for (int k=0; k<n; ++k)
    for (int i=0; i<n; ++i)
        for (int j=0; j<n; ++j)
            d[i][j] = min(a[i][j], a[i][k] + a[k][j]);
    int *deg = new int [n];
    int mam;
    for (int i=0; i<n; ++i)
    {
        deg[i] = 0;
        mam = d[i][0];
        for (int j=0; j<n; ++j)
        {
            if(d[i][j] > mam)
            {
                mam = d[i][j];
                deg[i] = mam;
            }
        }
    }
    int mim = deg[0];
    for(int i = 0; i < n; i++)
    {
        if(deg[i] < mim)
        {
            mim = deg[i];
        }
    }
    return mim;
Добавлено через 49 минут
ответьте кто-нибудь

Добавлено через 1 час 33 минуты
ну что, нет никого знающего????
0
DKOI
24 / 24 / 1
Регистрация: 08.09.2010
Сообщений: 136
09.11.2011, 21:56 #4
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <stdlib.h>
 
#define MIN(x,y) ((x)<(y)?(x):(y))
 
int main()
{
    int ** edge;
    int n;
    int i;
    int j;
    int k;
    printf("Set size > ");
    scanf("%d", &n);
    edge = (int**)calloc(n, sizeof(int*));
    for (i = 0; i < n; i++)
        edge[i] = (int*)calloc(n, sizeof(int));
    printf("Set array > \n");
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            scanf("%d", &edge[i][j]);
            if (!edge[i][j]) 
                edge[i][j] = 10000;
        }
    for (k = 0; k < n; k++)
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
                if (i != j)
                    edge[i][j] = MIN(edge[i][j], edge[i][k]+edge[k][j]);
    printf("\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (edge[i][j] == 10000) 
                edge[i][j] = 0;
            printf("%d ", edge[i][j]);
        }
        printf("\n");
    }
    return 0;
}
1
amor1k
Студент
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
10.11.2011, 12:58  [ТС] #5
Спасибо большое. Но есть еще вопрос, я хочу по этой программе найти центр. Написал как смог, помоему вершины не верны.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int **edge = new int *[n];
    for (int i = 0; i < n; i++)
        edge[i] = new int [n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            edge[i][j] = a[i][j];
            if (!edge[i][j]) 
                edge[i][j] = 10000;
        }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (i != j)
                    edge[i][j] = MIN(edge[i][j], edge[i][k]+edge[k][j]);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (edge[i][j] == 10000) 
                edge[i][j] = 0;
            cout << edge[i][j] << " ";
        }
        cout << endl;
    }
    int min, max;
    int *ecc = new int [n];
    int *rad = new int [n];
    int *deg = new int [n];
    for (int i = 0; i < n; i++) {
        rad[i] = ecc[i] = 0;
        min = edge[i][1];
        max = edge[i][1];
        deg[i] = 0;
        for (int j = i+1; j < n; j++) {
            if(edge[i][j] < min)
            {
                min = edge[i][j];
            }
            if(edge[i][j] > max)
                max = edge[i][j];
        }
        deg[i] = min;
        ecc[i] = max;
    }
    
    int j = 0;
    for(int i = 0; i < n; i++)
    {
        if(deg[i] == ecc[i])
                rad[j++] = i;
    }
    cout << "Центры графа: ";
    for(int i = 0; i < j; i++)
        cout << rad[i]+1 << " ";
Добавлено через 12 часов 56 минут
ответьте ктонибудь правильно ли я сделал??
0
LosAngeles
Заблокирован
10.11.2011, 13:08 #6
ну это же легко проверить. Возьми в руки карандаш и бумагу и посчитай! Ты чтоли целиком программу пишешь от начала до конца? Написал одну функцию которая выполняет одну небольшую задачу, проверил её работу, написал вторую и тд... Тогда никаких вопросов по поводу правильности работы алгоритма в конце не возникнет
0
amor1k
Студент
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
10.11.2011, 13:28  [ТС] #7
дело в том, что программа находит кратчайшие расстояния, а потом радиус и т.п.
А мне нужно найти максимальное расстояние каждой вершины, т.е. эксцентриситет.
Можно ли как-нибудь изменить эту программу на нужную мне?
0
LosAngeles
Заблокирован
10.11.2011, 13:51 #8
Цитата Сообщение от amor1k Посмотреть сообщение
int *ecc = new int [n];
а это чё, не эксцентриситеты разве?
0
amor1k
Студент
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
10.11.2011, 17:01  [ТС] #9
да, но я их ищу по кратчайшим расстояниям
C++
1
2
3
4
5
 for (int k = 0; k < n; k++)
                for (int i = 0; i < n; i++)
                        for (int j = 0; j < n; j++)
                                if (i != j)
                                        edge[i][j] = MIN(edge[i][j], edge[i][k]+edge[k][j]);
а мне нужно по максимальные расстояния. То есть в этой программе расстояние от точки 1 до точки 3 равно 3. А если подумать, то можно пройти по точкам 2,4,5,6,7 и получится другое расстояние. Вот мне нужно, чтобы программа высчитывала именно это другое расстояние
0
LosAngeles
Заблокирован
10.11.2011, 17:43 #10
эти твои расстояния никак не связаны ни с эксцентриситетом ни с радиусом, зачем их искать?
0
amor1k
Студент
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
10.11.2011, 17:49  [ТС] #11
эксцентриситет - максимальное расстояние.
радиус - минимальное расстояние.
Мне нужно найти центральные вершины (эксцентриситет = радиус)
Я говорю, что зашел в тупик...
0
LosAngeles
Заблокирован
10.11.2011, 18:18 #12
а причём тут максимальные расстояния о которых ты говорил в прошлом посте, они как то связаны с радиусом и эксцентриситетом? А тот листинг который ты же сам выложил не работает чтоли? Я же сказал нужно попробывать разбить задачу на подзадачии и тогда смотреть что именно не получается
0
amor1k
Студент
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
10.11.2011, 19:13  [ТС] #13
Цитата Сообщение от LosAngeles Посмотреть сообщение
А тот листинг который ты же сам выложил не работает чтоли?
он работает не так... я уже описал выше...

Центральная вершина(Center vertex)
- Вершина, эксцентриситет которой равен радиусу графа.
Эксцентриситет вершины(Eccentricity of a vertex)
- для данной вершины u величина
e(u) = max d(u,v)
где d(u,v) - расстояние между вершинами u и v
Радиус графа(Radius of a graph)
- минимальный из эксцентриситетов вершин связного графа; вершина, на которой достигается этот минимум называется центральной вершиной.

как мне переделать программу, чтобы она находила радиус графа. Все обдумал, и разбивал на подзадачи и т.д.
0
LosAngeles
Заблокирован
10.11.2011, 19:24 #14
Цитата Сообщение от amor1k Посмотреть сообщение
он работает не так... я уже описал выше...
ну визуально он выглядит правильно, только проверять i==j в алгоритме флойда нет нужды, это только замедлит его. Эсцентриситеты тоже вроде правильно находятся, надо видимо открыть деббагер и посмотреть где появляется ошибка
0
amor1k
Студент
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
10.11.2011, 19:42  [ТС] #15
вот смотрите
граф (рис. 1) матрица расстояний (рис. 2)
верно ли, что расстояние от 1 вершины до 3, может быть и 4 и 5?? Вот я наверно про эти максимальные расстояния говорю...

Не по теме:

Уже сам путаюсь)

0
Миниатюры
Центр графа  
Изображения
 
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.11.2011, 19:42
Привет! Вот еще темы с ответами:

Найти центр и радиус вписанной - C++
Дан треугольник с координатами вершин А(х1,у1), В(х2,у2), С(х3,у3). Найти центр и радиус вписанной в него окружность

Центр тяжести выпуклого многоугольника - C++
Итак народ , необходимо найти центр тяжести выпуклого многоугольника заданного своими вершинами в порядке обхода по часовой стрелке ...

Центр вписанного круга в треугольник - C++
Ребят, подскажите формулу для нахождения координат ценра вписаного круга, если известны координаты вершин триугольника

Определить радиус и центр окружности - C++
определить радиус и центр окружности, проходящей по крайней мере через­ три различные точки заданного множества точек ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
10.11.2011, 19:42
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru