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

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

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

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

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

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

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

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

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

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

Там и алгоритм есть
_Колючий_
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, находим его... (Как?)
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;
}
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
27.08.2013, 16:56     Поиск циклов в графе. Поиск центра взвешенного графа #14
поищите в интернете. Все есть.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.08.2013, 17:22     Поиск циклов в графе. Поиск центра взвешенного графа
Еще ссылки по теме:
Реализация матрицы смежности и инцидентности, поиск циклов в графе C++
Поиск на графе C++
Кратчайший путь между вершинами взвешенного графа, в котором есть ребра с отрицательным весом C++
C++ Поиск ободов в графе
C++ Поиск мостов в графе

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

Или воспользуйтесь поиском по форуму:
iRomul
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 480
Завершенные тесты: 1
27.08.2013, 17:22     Поиск циклов в графе. Поиск центра взвешенного графа #15
_Колючий_, есть цикл гамильтона - проход по всем узлам. Но для него нет алгоритма - только перебор.
Yandex
Объявления
27.08.2013, 17:22     Поиск циклов в графе. Поиск центра взвешенного графа
Ответ Создать тему
Опции темы

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