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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 32, средняя оценка - 4.88
amor1k
Студент
 Аватар для amor1k
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
09.11.2011, 17:04     Центр графа #1
Дана матрица смежности. Найти максимальное расстояние в графе.
Пол дня уже мучаюсь, искал в гугле, сам пытался, но ничего не получается... просто тупик...
Код вылаживать не буду, так как он не правильный. Просто расскажу, как я хочу сделать.
Беру первую вершину, и делаю ее текущей. Если существует ребро между текущей и другой вершиной, делаю ее текущей и иду дальше. При этом считаю все расстояния, а в конце сравниваю и ищу максимум. Но что-то все равно не получается...
Помогите сделать программу, или хотя бы объясните подробно что и как делать!!!

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

Добавлено через 3 минуты
вот он собственно, в конце даже ссылка есть на С++ реализацию, так что тебе и писать нечего не придётся)
http://ru.wikipedia.org/wiki/%D0%90%...B8.D1.82.D0.BC
amor1k
Студент
 Аватар для 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 минуты
ну что, нет никого знающего????
DKOI
 Аватар для 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;
}
amor1k
Студент
 Аватар для 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 минут
ответьте ктонибудь правильно ли я сделал??
LosAngeles
Заблокирован
10.11.2011, 13:08     Центр графа #6
ну это же легко проверить. Возьми в руки карандаш и бумагу и посчитай! Ты чтоли целиком программу пишешь от начала до конца? Написал одну функцию которая выполняет одну небольшую задачу, проверил её работу, написал вторую и тд... Тогда никаких вопросов по поводу правильности работы алгоритма в конце не возникнет
amor1k
Студент
 Аватар для amor1k
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
10.11.2011, 13:28  [ТС]     Центр графа #7
дело в том, что программа находит кратчайшие расстояния, а потом радиус и т.п.
А мне нужно найти максимальное расстояние каждой вершины, т.е. эксцентриситет.
Можно ли как-нибудь изменить эту программу на нужную мне?
LosAngeles
Заблокирован
10.11.2011, 13:51     Центр графа #8
Цитата Сообщение от amor1k Посмотреть сообщение
int *ecc = new int [n];
а это чё, не эксцентриситеты разве?
amor1k
Студент
 Аватар для 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 и получится другое расстояние. Вот мне нужно, чтобы программа высчитывала именно это другое расстояние
LosAngeles
Заблокирован
10.11.2011, 17:43     Центр графа #10
эти твои расстояния никак не связаны ни с эксцентриситетом ни с радиусом, зачем их искать?
amor1k
Студент
 Аватар для amor1k
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
10.11.2011, 17:49  [ТС]     Центр графа #11
эксцентриситет - максимальное расстояние.
радиус - минимальное расстояние.
Мне нужно найти центральные вершины (эксцентриситет = радиус)
Я говорю, что зашел в тупик...
LosAngeles
Заблокирован
10.11.2011, 18:18     Центр графа #12
а причём тут максимальные расстояния о которых ты говорил в прошлом посте, они как то связаны с радиусом и эксцентриситетом? А тот листинг который ты же сам выложил не работает чтоли? Я же сказал нужно попробывать разбить задачу на подзадачии и тогда смотреть что именно не получается
amor1k
Студент
 Аватар для 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)
- минимальный из эксцентриситетов вершин связного графа; вершина, на которой достигается этот минимум называется центральной вершиной.

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

Не по теме:

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

Миниатюры
Центр графа  
Изображения
 
LosAngeles
Заблокирован
10.11.2011, 20:48     Центр графа #16
Пути длиной 4 и 5 наверно есть, только они никак не влияют на нахождение эксцентриситетов или радиуса, нас интересует кратчайшее расстояние, то есть 2, в таблице 2, всё ок.
Эсцентриситеты -3323222
amor1k
Студент
 Аватар для amor1k
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
10.11.2011, 21:04  [ТС]     Центр графа #17
центральная вершина графа это когда эксцентриситет вершины равен ее радиусу, так?
и посмотри пожалуйста на код в конце, там я ищу центр. Но ответы не верны. Какие по твоему вершины есть центральные?
LosAngeles
Заблокирован
11.11.2011, 05:34     Центр графа #18
3567 - цетнральные

Добавлено через 7 минут
я не понял зачем нужен и этот цикл и переменная deg

Цитата Сообщение от amor1k Посмотреть сообщение
for(int i = 0; i < n; i++)
{
if(deg[i] == ecc[i])
rad[j++] = i;
}
в переменную min лучше отложить минимальный эксцентриситет сразу, и потом в цикле if (min == ecc[i]) cout << ecc[i]+1 << " - central vertex" << endl; и всё
amor1k
Студент
 Аватар для amor1k
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
11.11.2011, 23:45  [ТС]     Центр графа #19
можно и так) но программа выдает мне только центральные вершины 6,7... почему 3 и 5 не показывают подскажите!

Добавлено через 12 часов 56 минут
......
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.11.2011, 06:46     Центр графа
Еще ссылки по теме:

Центр симметрии C++
Центр тяжести C++
C++ Найти центр масс N точек

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

Или воспользуйтесь поиском по форуму:
LosAngeles
Заблокирован
14.11.2011, 06:46     Центр графа #20
весь код выложи
Yandex
Объявления
14.11.2011, 06:46     Центр графа
Ответ Создать тему
Опции темы

Текущее время: 14:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru