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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Списки:нужны или нет? http://www.cyberforum.ru/cpp-beginners/thread944104.html
Стоит ли изучать связные списки,они используются в дальнейшем? Может я туповат, но алгоритм их построения понять не могу. Уж больно все запутанно описывается в книжке. Пытался сам разбираться ,вот что вышло #include <iostream> using namespace std; class part { public: part *next; int item;
C++ Путь символа Здорова господа! Есть интересная задачка: "Проследите путь символа в вашей системе от клавиатуры до экрана на примере следующего кода:" char c; cin >>c; cout <<c<<endl; И как же его проследить???? http://www.cyberforum.ru/cpp-beginners/thread944099.html
C++ Ошибка: "case label not within a switch statement"
Здравствуйте, работая с оператором switch произошла ошибка case label '1' not within a switch statement case label '1' not within a switch statement case label '1' not within a switch statement Вот код std::cin >> pEnter;
C++ Время для функции генерирующей случайные величины
я написал функцию которая генерирует случайные величины в промежутке valarray<double> cRand::base_rnd(size_t N){ valarray<double> v; v.resize(N); int x,y; int x0 = time(0); x = fabs((a*x0 + c)%M); v = double(x)/M; for(size_t i = 1;i<N;i++){
C++ Конструктор класса http://www.cyberforum.ru/cpp-beginners/thread944077.html
class A{}; class B : public A { B(); }; B::B() : A() /// ДЛЯ ЧЕГО ТУТ :A() И ЧТО ЭТО ОЗНАЧАЕТ??? { }
C++ Конструктор класса Я не могу понять вот эту запись class A{}; class B : public A { подробнее

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

вот так провряется наличие циклов в орграфе:
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;
}
 
Текущее время: 23:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru