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

Не рекурсивный обход графа в глубину - C++

Войти
Регистрация
Восстановить пароль
 
onlwork
1 / 1 / 0
Регистрация: 10.11.2013
Сообщений: 53
26.03.2014, 18:47     Не рекурсивный обход графа в глубину #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
void OrGraph::dfs(int v){
    int n = GetCount(); // получаем количество вершин
    int *a = new int[n];
    for (int i = 0; i < n; i++){
        *(a + i) = 1;
    }
    int k = numberTop(v);// кладем в к номер вершины v
    int u = 0 ,b = 0,it;
    Stack s;
    *(a + k) = 0;
    s.Push(v); //в стек записываем произвольную вершину
    while(!s.Emty()){//проверяем, пока не пуст стек
        b = 1;
        it = s.Pop();//просматриваем вершину из стека
        for (Org *current = first; current && b && u<n;){
        if((HasArc(it,recoverTopForTop(u)) && (*(a + u)))) b = 0; //HasArc - существует ли дуга из А в В
//recoverTopForTop - берем вершину с номером u
        else{
            u++;
            current = current -> next;
        }
        if(!b){
            s.Push(recoverTopForTop(u));
            std::cout<<recoverTopForTop(u)<<" ";
            *(a + u) = 0;
        }
        else
            s.Pop();
        }
        
    }
 
}
Граф представлен вот так

C++
1
2
3
4
5
6
7
8
9
10
struct Org {
        int begin, end;
        Org *next;
        Org(char b, char e, Org *n = NULL){
            begin = b; end = e;
            next = n;
        }
    };
 
    Org *first, *last;
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2014, 18:47     Не рекурсивный обход графа в глубину
Посмотрите здесь:

Рекурсивный обход каталога C++
C++ Рекурсивный обход директорий
Обход графа в глубину C++
C++ Хитрый обход дерева в глубину
C++ Организовать обход в глубину
C++ Обход вершин графа в глубину стеком
Обход неориентированного графа в глубину C++
Обход графа в глубину C++
C++ Рекурсивный обход небинарного дерева
C++ Рекурсивный поиск в глубину
C++ Рекурсивный и нерекурсивный поиск в глубину
C++ Обход графа в глубину

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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