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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.65
_Колючий_
4 / 4 / 2
Регистрация: 05.08.2012
Сообщений: 109
#1

Поиск циклов в графе. Поиск центра взвешенного графа - C++

26.08.2013, 23:31. Просмотров 3050. Ответов 22
Метки нет (Все метки)

В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать статью/пособие, где было бы подробно об этом написано?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
27.08.2013, 17:51     Поиск циклов в графе. Поиск центра взвешенного графа #16
насчет центра взвешенного графа. вот здесь: http://ru.wikipedia.org/wiki/Глоссарий_теории_графов всё описано просто и понятно. как я понял надо найти кратчайшие пути между всеми парами вершин, т.е. составить матрицу кратчайших путей. затем посчитать максимальное значение в каждой строке матрицы (!!в орграфе не в строках а в столбцах, т.к. в статье сказано кратчайший путь В каждую вершину, а алгоритмы обычно ищут кратчайшие пути ИЗ каждой вершины). и затем найти минимальное из этих максимальных значений. та вершина, которая имеет это минимальное значение и есть центр графа.
могу ошибаться, но я так это понял.

Добавлено через 8 минут

Не по теме:

Цитата Сообщение от _Колючий_ Посмотреть сообщение
Дали билеты в зубы - сказали что бы за лето выучил
Цитата Сообщение от _Колючий_ Посмотреть сообщение
В интернете, к сожалению, по этим вопросам не так уж много нашел.
за всё лето ничего полезного не нашли или ... ?

iRomul
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 480
Завершенные тесты: 1
27.08.2013, 17:53     Поиск циклов в графе. Поиск центра взвешенного графа #17
ya_noob, есть метод Флойда-Уоршелла, который за O(n^3) даёт пути из всех вершин во все остальные.
А циклы в графе надо смотреть либо Эйлера, либо Гамильтона.

Рекомендую книгу Кормена по алгоритмам - там всё просто и понятно, с псевдокодами и иллюстрациями.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
27.08.2013, 18:14     Поиск циклов в графе. Поиск центра взвешенного графа #18
Цитата Сообщение от iRomul Посмотреть сообщение
есть метод Флойда-Уоршелла, который за O(n^3) даёт пути ...
а еще есть алгоритм Дейкстры (для случаев когда нет отрицательных весов ребер), который дает тот же результат за V*E*logV (V - кол-во вершин, E - кол-во ребер), а также алгоритм Беллмана-Форда (для случая когда есть отрицательные ребра, но нет отрицательных циклов) с примерно такой же оценкой времени. И какой из них выбирать зависит от насыщенности графа. Так что выбор конкретного алгоритма поиска путей пусть будет на совести ТСа.
Цитата Сообщение от iRomul Посмотреть сообщение
... из всех вершин во все остальные.
вот именно ИЗ (я же специально капсом написал), а нам надо В. а это уже другая история.
Цитата Сообщение от iRomul Посмотреть сообщение
Рекомендую книгу Кормена по алгоритмам - там всё просто и понятно, с псевдокодами и иллюстрациями.
а тут поддерживаю

Добавлено через 2 минуты
Цитата Сообщение от iRomul Посмотреть сообщение
А циклы в графе надо смотреть либо Эйлера, либо Гамильтона.
зачем? и простых будет достаточно, даже больше скажу: достаточно и необходимо
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
27.08.2013, 18:24     Поиск циклов в графе. Поиск центра взвешенного графа #19
iRomul, есть. Нейронные сети, муравьиные алгоритмы, метод ветвей и границ и другие.
Первые два - дают приближенные результаты, третий - точные.
_Колючий_
4 / 4 / 2
Регистрация: 05.08.2012
Сообщений: 109
28.08.2013, 00:01  [ТС]     Поиск циклов в графе. Поиск центра взвешенного графа #20
Цитата Сообщение от ya_noob Посмотреть сообщение
зачем? и простых будет достаточно, даже больше скажу: достаточно и необходимо
А это, так понимаю, как раз приведенный выше код?

Цитата Сообщение от ya_noob Посмотреть сообщение
Добавлено через 8 минут

Не по теме:


за всё лето ничего полезного не нашли или ... ?

Не по теме:

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

NurlashKO
87 / 87 / 14
Регистрация: 07.10.2012
Сообщений: 145
28.08.2013, 15:24     Поиск циклов в графе. Поиск центра взвешенного графа #21
2)
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
#include <iostream>
#include <cstdio>
 
using namespace std;
 
#define sz 1000
 
int n, a[sz][sz], d[sz], exc[sz], R, w;
 
int main()
{
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];           // Читаем матрицу смежности графа, если ребра между вершинами нет то а[i][j] = -1
 
    //Находим кратчайшие расстояния между всеми парами вершын
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (a[i][j] != -1 && a[i][k] != -1 && a[k][j] != -1)
                    a[i][j] = min(a[i][k] + a[k][j], a[i][j]);
    //
    //Находим радиус графа, за одно подсчитываем эксцентриситет для каждой вершины
    R = (int)1e9;
    for (int i = 1; i <= n; i++)
    {
        w = 0;
        for (int j = 1; j <= n; j++)
        {
            if (a[i][j] != -1)
                w = max(w, a[i][j]);
        }
        exc[i] = w;
        R = min(R, exc[i]);
    }
    //
    //Если эксцентриситет вершины равен радиусу графа то эта вершина центр графа, выводим её.
    cout << "Center :" << endl;
    for (int i = 1; i <= n; i++)
        if (exc[i] == R)
            cout << i << " ";
}
Добавлено через 15 минут
1)
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
#include <iostream>
#include <cstdio>
 
using namespace std;
 
#define sz 1000
 
int n, a[sz][sz], c, d[sz], cnt;
 
bool check(int p, int t)
{
    if (p == t)
        return a[d[t]][d[1]];
    if (!a[d[p]][d[p + 1]])
        return false;
    return check(p + 1, t);
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];   //Читаем матрицу смежности, если есть ребро а[i][j] = 1, иначе 0
 
 
    for (int mask = 1; mask < (1 << n); mask++)     //Перебираем все возможные комбинации вершин (2 ^ n)
    {
        c = 0;
        for (int i = 0; i < n; i++)    //Выписываем вершины из текущей комбинации
            if (mask & (1 << i))
                d[++c] = i + 1;
        if (check(1, c))        //Если данные вершины образуют цикл, сообщаем об этом.
        {
            cnt++;
            cout << "Cycl " << cnt << " :" << endl;
            for (int i = 1; i <= c; i++)
                cout << d[i] << " ";
            cout << endl;
        }
    }
    
}
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
28.08.2013, 19:44     Поиск циклов в графе. Поиск центра взвешенного графа #22
NurlashKO, у меня вопрос по программе 2): судя по 17 строке, работа будет идти с орграфом. в 34 строке ищется максимальное значение в i-ой строке, т.е. эксцентриситет вы ищите как:
максимальное расстояние из всех минимальных расстояний от данной вершины до других вершин.
в той статье из вики, что я приводил ранее, говорится про экцентриситет так:
максимальное расстояние из всех минимальных расстояний от других вершин до данной вершины.
так собственно вопрос: википедия обманывает или я чего-то непонял? просветите
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.08.2013, 19:51     Поиск циклов в графе. Поиск центра взвешенного графа
Еще ссылки по теме:
Реализация матрицы смежности и инцидентности, поиск циклов в графе C++
Поиск на графе C++
Кратчайший путь между вершинами взвешенного графа, в котором есть ребра с отрицательным весом C++
C++ Поиск ободов в графе
C++ Поиск мостов в графе

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

Или воспользуйтесь поиском по форуму:
NurlashKO
87 / 87 / 14
Регистрация: 07.10.2012
Сообщений: 145
28.08.2013, 19:51     Поиск циклов в графе. Поиск центра взвешенного графа #23
Да, я ошибся. Я предполагал что граф не ориентирован (Моя ошибка что я это не уточнил).
Yandex
Объявления
28.08.2013, 19:51     Поиск циклов в графе. Поиск центра взвешенного графа
Ответ Создать тему
Опции темы

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