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

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

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

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

26.08.2013, 23:31. Просмотров 3108. Ответов 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. Нужно...

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

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

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

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

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

Теории никакой нет. Т.к. я недавно перевелся. Дали билеты в зубы - сказали что бы за лето выучил. Как-то так.
0
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.
1
_Колючий_
4 / 4 / 2
Регистрация: 05.08.2012
Сообщений: 109
27.08.2013, 10:58  [ТС] #7
Паскаль я знаю. Ладно, разберусь, если 100% рабочее.
0
luciys
5 / 5 / 1
Регистрация: 27.11.2012
Сообщений: 160
27.08.2013, 11:00 #8
можно ещё вот как сделать, кстати, ты даже не сказал ор граф или неор?, можно брать отсеивать "висячие ветки", т.е. те, которые имеют только 1 "соседа", так бегаешь по графу пока они есть, т.е. пробежал по графу, встретил такую ветку выбросил её, пошёл дальше, прошёл все вершины, снова пошёл, так проходишь пока не уйдут все вершины или не останется висячих, и если осталось больше 2 вершин, то циклу есть место, но я точно не уверен, это стоило бы тщательно на листке расписать, на каких-нибудь сложных графах и частных случаях
0
_Колючий_
4 / 4 / 2
Регистрация: 05.08.2012
Сообщений: 109
27.08.2013, 11:05  [ТС] #9
Орграф. В неориентированном проще все гораздо. Это понятно. Можно просто запустить поиск в ширину + сделать список, куда бы заносились уже пройденные вершины. Если при рассмотрении очередной вершины натыкаемся на пройденную - цикл.
0
luciys
5 / 5 / 1
Регистрация: 27.11.2012
Сообщений: 160
27.08.2013, 11:23 #10
закончились деньги на интернете, а я там матрицы начал писать...
ну да, только не спмсок, а индексный массив, или как там его, в общем, посетил 4 вершину ставишь в этом массиве 1 в 4 ячейку и тд
0
iRomul
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 480
Завершенные тесты: 1
27.08.2013, 12:32 #11
Если я правильно понял по циклам, то цикл эйлера подойдет:
http://ru.wikipedia.org/wiki/Эйлеров_цикл

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

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

procedure find_all_cycles (v)
var массив cycles
1. пока есть цикл, проходящий через v, находим его... (Как?)
0
ya_noob
_
201 / 145 / 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;
}
1
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 728
27.08.2013, 16:56 #14
поищите в интернете. Все есть.
0
iRomul
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 480
Завершенные тесты: 1
27.08.2013, 17:22 #15
_Колючий_, есть цикл гамильтона - проход по всем узлам. Но для него нет алгоритма - только перебор.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.08.2013, 17:22
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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