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

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

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

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

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

В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать статью/пособие, где было бы подробно об этом написано?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.08.2013, 23:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск циклов в графе. Поиск центра взвешенного графа (C++):

Поиск Ф-циклов в графе - C++
Нужно вывести на печать все фундаментальные циклы графа. Мой код выводит правильно(судя по данному примеру),но помоему он не разделяет сами...

Поиск циклов в графе - C++
Как узнать что граф имеет цикл?

Поиск отрицательых циклов в графе - C++
подскажите пожалуйста, как определить, есть ли в графе отрицательные циклы....граф задаётся матрицей смежности P.S очень срочно...

Поиск отрицательных циклов в графе - C++
Добрый день. Имеется код производящий обход графа. Мне надо "Определить, имеются ли //у него циклы отрицательного веса. . Я...

Поиск циклов в ориентированном графе - C++
Доброго времени суток. Может кому-нибудь из вас не составит особого труда, или возможно кто-то писал похожую программу. В общем, я написал...

Поиск всех циклов в неориентированном графе. - C++
На входе программа принимает номера вершин и вес ребра между ними. Например: 2 3 1 - между вершинами 2 и 3 есть ребро весом 1. Нужно...

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

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

Не по теме:

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

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

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

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

Не по теме:


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

Не по теме:

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

0
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;
        }
    }
    
}
0
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
28.08.2013, 19:44 #22
NurlashKO, у меня вопрос по программе 2): судя по 17 строке, работа будет идти с орграфом. в 34 строке ищется максимальное значение в i-ой строке, т.е. эксцентриситет вы ищите как:
максимальное расстояние из всех минимальных расстояний от данной вершины до других вершин.
в той статье из вики, что я приводил ранее, говорится про экцентриситет так:
максимальное расстояние из всех минимальных расстояний от других вершин до данной вершины.
так собственно вопрос: википедия обманывает или я чего-то непонял? просветите
0
NurlashKO
87 / 87 / 14
Регистрация: 07.10.2012
Сообщений: 145
28.08.2013, 19:51 #23
Да, я ошибся. Я предполагал что граф не ориентирован (Моя ошибка что я это не уточнил).
0
28.08.2013, 19:51
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.08.2013, 19:51
Привет! Вот еще темы с ответами:

поиск центра графа - C++
Здраствуйте. нужен универсальный код поиска центра графа(вершины или двух). рисовать или вставлять граф не нужно.

Реализация матрицы смежности и инцидентности, поиск циклов в графе - C++
Здравствуйте. Есть программа, выводящая матрицу смежности и инцидентности. Прошу помощи в реализации добавления и удаления вершин и рёбер...

Поиск на графе - C++
Доброго времени суток. Мне не совсем понятна реализация в коде поиска на графе в высоту и ширину. Т.к. в книге они описаны не совсем...

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


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

Или воспользуйтесь поиском по форуму:
23
Ответ Создать тему
Опции темы

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