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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.65
_Колючий_
3 / 3 / 2
Регистрация: 05.08.2012
Сообщений: 88
26.08.2013, 23:31     Поиск циклов в графе. Поиск центра взвешенного графа #1
В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать статью/пособие, где было бы подробно об этом написано?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.08.2013, 23:31     Поиск циклов в графе. Поиск центра взвешенного графа
Посмотрите здесь:

C++ поиск циклов в графе
C++ поиск центра графа
Поиск на графе C++
Поиск всех циклов в неориентированном графе. C++
Поиск Ф-циклов в графе C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
luciys
5 / 5 / 1
Регистрация: 27.11.2012
Сообщений: 160
27.08.2013, 01:52     Поиск циклов в графе. Поиск центра взвешенного графа #2
что значит поиск циклов? найти их количество? найти 1/все маршрут/ы? просто ответить: есть ли цикл в графе?
_Колючий_
3 / 3 / 2
Регистрация: 05.08.2012
Сообщений: 88
27.08.2013, 10:03  [ТС]     Поиск циклов в графе. Поиск центра взвешенного графа #3
Цитата Сообщение от luciys Посмотреть сообщение
что значит поиск циклов? найти их количество? найти 1/все маршрут/ы? просто ответить: есть ли цикл в графе?
У меня вопрос такой экзаменационный. "Поиск циклов в графе".

Учитывая, что за первый курс - да. Скорее всего просто есть/нету.
luciys
5 / 5 / 1
Регистрация: 27.11.2012
Сообщений: 160
27.08.2013, 10:16     Поиск циклов в графе. Поиск центра взвешенного графа #4
Цитата Сообщение от _Колючий_ Посмотреть сообщение
У меня вопрос такой экзаменационный. "Поиск циклов в графе".

Учитывая, что за первый курс - да. Скорее всего просто есть/нету.
ну не знаю, я бы пошёл в лоб, взял бы пустил бы волновой метод, граф представил бы матрицей смежности, конечно пускать нужно от каждой вершины, ну т.е. организовал бы очередь
или поиск в глубину

и если доходишь до вершины с которой начал, то true

Добавлено через 8 минут
так стоп, вопрос экзаменационный, а конспекты какие-нибудь? методы? должен же быть какой-то источник теории
_Колючий_
3 / 3 / 2
Регистрация: 05.08.2012
Сообщений: 88
27.08.2013, 10:22  [ТС]     Поиск циклов в графе. Поиск центра взвешенного графа #5
Честно говоря, смутно себе представляю, как именно это сделать. Что из себя представляет этот волновой метод?

Теории никакой нет. Т.к. я недавно перевелся. Дали билеты в зубы - сказали что бы за лето выучил. Как-то так.
luciys
5 / 5 / 1
Регистрация: 27.11.2012
Сообщений: 160
27.08.2013, 10:49     Поиск циклов в графе. Поиск центра взвешенного графа #6
ну так тут сложновато на форуме объяснить, да и объяснять я толком не умею =D
вот, блин, нашёл свои графы, здесь отвечает есть-ли путь из 1-ой вершины в 2-ую, правда что-то по виду она чуть не доработана и она на паскале...)
Pascal
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
53
54
55
56
57
58
var f1,f2:text;
    a:array [-1..100,-1..100] of integer;
    fl,p,way,n_u:array [-1..100] of integer;
    p1,p2,i,k,v,v1,v2,n,ksv:integer;
begin
 assign(f1,'f1.txt');reset(f1);
 assign(f2,'f2.txt');rewrite(f2);
 writeln('Vvedite koli4estvo verwin:');
 readln(f1,n);
 writeln('Vvedite koli4estvo par sv9zannblh verwin:');
 readln(f1,ksv);
 writeln('Vvedite sv9zannble verwinbl:');
 for i:=1 to ksv do
        begin
                readln(f1,v1,v2);
                a[v1,v2]:=1;
                a[v2,v1]:=1;
        end;
 writeln('Vvedite na4alnuu verwin:');
 readln(f1,v);
 writeln('Vvedite punkt nazna4eni9:');
 readln(f1,v1);
 
        for i:=0 to n do
                begin
                        fl[i]:=0;
                        p[i]:=0;
                end;
        p1:=1;
        p2:=1;
        p[1]:=v;
        fl[v]:=1;
        n_u[1]:=1;
        while (p1<=p2) do
                begin
                        for i:=1 to n do
                                if (a[v,i]=1) and (fl[i]=0) then
                                        begin
                                                fl[i]:=1;
                                                inc(p2);
                                                p[p2]:=i;
                                                n_u[p2]:=n_u[p1]+1;
 
                                        end;
                        inc(p1);
                        v:=p[p1];
                end;
{ if fl[v1]=0 then
                writeln(f2,'false')
             else    }
             begin
                     writeln(f2,'true');
                     for i:=1 to p2 do
                      writeln(f2,p[i]:2,n_u[i]:2);
              end;
close(f1);
close(f2);
end.
_Колючий_
3 / 3 / 2
Регистрация: 05.08.2012
Сообщений: 88
27.08.2013, 10:58  [ТС]     Поиск циклов в графе. Поиск центра взвешенного графа #7
Паскаль я знаю. Ладно, разберусь, если 100% рабочее.
luciys
5 / 5 / 1
Регистрация: 27.11.2012
Сообщений: 160
27.08.2013, 11:00     Поиск циклов в графе. Поиск центра взвешенного графа #8
можно ещё вот как сделать, кстати, ты даже не сказал ор граф или неор?, можно брать отсеивать "висячие ветки", т.е. те, которые имеют только 1 "соседа", так бегаешь по графу пока они есть, т.е. пробежал по графу, встретил такую ветку выбросил её, пошёл дальше, прошёл все вершины, снова пошёл, так проходишь пока не уйдут все вершины или не останется висячих, и если осталось больше 2 вершин, то циклу есть место, но я точно не уверен, это стоило бы тщательно на листке расписать, на каких-нибудь сложных графах и частных случаях
_Колючий_
3 / 3 / 2
Регистрация: 05.08.2012
Сообщений: 88
27.08.2013, 11:05  [ТС]     Поиск циклов в графе. Поиск центра взвешенного графа #9
Орграф. В неориентированном проще все гораздо. Это понятно. Можно просто запустить поиск в ширину + сделать список, куда бы заносились уже пройденные вершины. Если при рассмотрении очередной вершины натыкаемся на пройденную - цикл.
luciys
5 / 5 / 1
Регистрация: 27.11.2012
Сообщений: 160
27.08.2013, 11:23     Поиск циклов в графе. Поиск центра взвешенного графа #10
закончились деньги на интернете, а я там матрицы начал писать...
ну да, только не спмсок, а индексный массив, или как там его, в общем, посетил 4 вершину ставишь в этом массиве 1 в 4 ячейку и тд
iRomul
 Аватар для iRomul
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 474
Завершенные тесты: 1
27.08.2013, 12:32     Поиск циклов в графе. Поиск центра взвешенного графа #11
Если я правильно понял по циклам, то цикл эйлера подойдет:
http://ru.wikipedia.org/wiki/Эйлеров_цикл

Там и алгоритм есть
_Колючий_
3 / 3 / 2
Регистрация: 05.08.2012
Сообщений: 88
27.08.2013, 16:29  [ТС]     Поиск циклов в графе. Поиск центра взвешенного графа #12
Цитата Сообщение от iRomul Посмотреть сообщение
Если я правильно понял по циклам, то цикл эйлера подойдет:
http://ru.wikipedia.org/wiki/Эйлеров_цикл

Там и алгоритм есть
Как я понимаю, Эйлеров цикл - это частный случай. Когда он проходит через ВСЕ ребра. А если нет. В алгоритме сказано

procedure find_all_cycles (v)
var массив cycles
1. пока есть цикл, проходящий через v, находим его... (Как?)
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
27.08.2013, 16:52     Поиск циклов в графе. Поиск центра взвешенного графа #13
Цитата Сообщение от _Колючий_ Посмотреть сообщение
Можно просто запустить поиск в ширину
точнее в глубину

вот так провряется наличие циклов в орграфе:
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <vector>
using namespace std;
 
int N; // кол-во вершин в орграфе
std::vector< std::vector< bool > > g; // представление графа в виде матрицы смежности
std::vector< bool > pre; // здесь будем помечать пройденные вершины на прямом ходу
std::vector< bool > post; // здесь будем помечать пройденные вершины на обратном ходу, пометка вершин на обратном ходу нужна чтобы определять тип ребра в остовном дереве
 
void init_digraph() // инициализация мартицы смежности
{
    g.resize( N, std::vector< bool >( N, false ) );
}
 
void read_digraph() // считываем ребра орграфа: вводим пары чисел, обозначающих исходную и конечную вершины
{
    for ( int p, q; std::cin >> p >> q; ) // ctrl+Z для выхода
        if ( p >= 0 && p < N && q >= 0 && q < N && p != q )
            g[ p ][ q ] = true;
}
 
void show_digraph() // самая бестолковая функция
{
    for ( int i = 0; i < N; ++i )
    {
        for ( int j = 0; j < N; ++j )
            std::cout << g[ i ][ j ] << ' ';
        std::cout << std::endl;
    }
}
 
bool dfs( int i ) // самая важная функция: обход орграфа и поиск цикла
{
    pre[ i ] = true; // первый раз натыкаемся на вершину и сразу помечаем ее (прямой обход), дальше будем обходить ее потомков
    for ( int j = 0; j < N; ++j ) // побежали обходить потомков вершины i
    {
        if ( !g[ i ][ j ] ) continue; // нет ребра i->j
        if ( !pre[ j ] ) // в вершине j мы еще ни разу не были
        {
            if ( !dfs( j ) ) // обходим вершину j (и всех ее потомков)
                return false; // где-то в процессе обхода потомков вершины j нашли цикл (слышен крик из глубины) (как нашли смотри на пару строк ниже)
            post[ j ] = true; // еще раз помечаем вершину, но теперь все ее потомки обойдены и здесь нам делать нечего (обратный обход)
        }
        // слеующая строка самая главная, ради нее всё и затевалось, ради нее делались все пометки в векторах pre и post
        else if ( !post[ j ] ) // в вершине j мы уже были (т.к. pre[ j ] == true), но обошли не всех ее потомков - это и есть условие цикла (это сложно понять, но это так)
            return false; // кричим из глубины рекурсии, что цикл найден
    }
    return true; // крика не было, всё тихо, т.е. true
}
 
bool isDAG() // функция проверки на то, является ли орграф DAG-графом, т.е. орграфом, не содержащим циклов
{
    pre.resize( N, false ); // сбрасываем пометки
    post.resize( N, false ); // еще раз сбрасываем пометки 
    for ( int i = 0; i < N; ++i ) // этот for и следующий за ним if нужны для несвязных графов; если граф связный то можно обойтись только вызовом dfs( 0 )
        if ( !pre[ i ] ) // описал выше
            if ( !dfs( i ) ) // запуск проверки орграфа на циклы
                return false; // был найден цикл
    return true; // как мы не мучили орграф, но так и не смогли найти цикл
}
 
int main()
{
    std::cin >> N; // вводим кол-во вершин в орграфе
    init_digraph();
    read_digraph();
    show_digraph();
    if ( isDAG() )  // нет циклов
        std::cout << "DAG" << std::endl;
    else // есть циклы
        std::cout << "!DAG" << std::endl;
 
    return 0;
}
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
27.08.2013, 16:56     Поиск циклов в графе. Поиск центра взвешенного графа #14
поищите в интернете. Все есть.
iRomul
 Аватар для iRomul
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 474
Завершенные тесты: 1
27.08.2013, 17:22     Поиск циклов в графе. Поиск центра взвешенного графа #15
_Колючий_, есть цикл гамильтона - проход по всем узлам. Но для него нет алгоритма - только перебор.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
27.08.2013, 17:51     Поиск циклов в графе. Поиск центра взвешенного графа #16
насчет центра взвешенного графа. вот здесь: http://ru.wikipedia.org/wiki/Глоссарий_теории_графов всё описано просто и понятно. как я понял надо найти кратчайшие пути между всеми парами вершин, т.е. составить матрицу кратчайших путей. затем посчитать максимальное значение в каждой строке матрицы (!!в орграфе не в строках а в столбцах, т.к. в статье сказано кратчайший путь В каждую вершину, а алгоритмы обычно ищут кратчайшие пути ИЗ каждой вершины). и затем найти минимальное из этих максимальных значений. та вершина, которая имеет это минимальное значение и есть центр графа.
могу ошибаться, но я так это понял.

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

Не по теме:

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

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

Рекомендую книгу Кормена по алгоритмам - там всё просто и понятно, с псевдокодами и иллюстрациями.
ya_noob
_
200 / 144 / 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
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
27.08.2013, 18:24     Поиск циклов в графе. Поиск центра взвешенного графа #19
iRomul, есть. Нейронные сети, муравьиные алгоритмы, метод ветвей и границ и другие.
Первые два - дают приближенные результаты, третий - точные.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.08.2013, 00:01     Поиск циклов в графе. Поиск центра взвешенного графа
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
_Колючий_
3 / 3 / 2
Регистрация: 05.08.2012
Сообщений: 88
28.08.2013, 00:01  [ТС]     Поиск циклов в графе. Поиск центра взвешенного графа #20
Цитата Сообщение от ya_noob Посмотреть сообщение
зачем? и простых будет достаточно, даже больше скажу: достаточно и необходимо
А это, так понимаю, как раз приведенный выше код?

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

Не по теме:


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

Не по теме:

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

Yandex
Объявления
28.08.2013, 00:01     Поиск циклов в графе. Поиск центра взвешенного графа
Ответ Создать тему
Опции темы

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