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

Поиск всех контуров в ориентированном графе - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.69
Serg046
21 / 21 / 2
Регистрация: 07.01.2010
Сообщений: 376
31.05.2012, 21:24     Поиск всех контуров в ориентированном графе #1
Нужно найти все контуры.
Контур - путь, у которого начало и конец совпадают. Т.е. например (1;5)(5;2)(2;4)(4;1).

Имею вектор с направленными ребрама (0;1)(2;0)(3;5)...и т.д.
Лежат здесь
C++
1
2
3
4
5
6
7
8
vector<ribItem> tRibs;
//на булы не обращайте внимания
class ribItem
{
public:
int First, Last;
bool leftRight, rightLeft;
};
Решил его отсортировать в vector< vector<ribItem> > sortRibs
так что каждый каждый элемент вектора sortRibs соответствует ribItem.First
Ну в общем так
Был вектор с ребрами tRibs (0;2)(0;3)(2;0)(5;0)(7;1)(7;2)
получил вектор
sortRibs
--0---1---2---3--4--5---6---7---
(0;2) -- (2;0) -- -- (5;0) -- (7;1)
(0;3) (7;2)
Т.е. если нету ребер из вершины 1, то sortRibs[1].size() == 0

Если тупо перебирать все сочетания из tRibs, то все норм, но если элементов в tRibs больше 8, то все происходит очень медленно.

Тогда и решил отсортировать вектор и шагать по нему.
Что-то типа
(допустим другие значения в векторах)
Взяли ребро (2;0) пошли в sortRibsх[0] взяли ребро оттуда, например там (0;3) -> sortRibsх[3] (3;2) в вершине 2 уже были возвращаемся.
Берем (3;0) ну и т.д.
Только возвращаемся по нескольким признакам. Полностью алгоритм описывать не буду, т.к. работает коряво. Думаю код кидать смысла нету, но все же

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
class verItem
{
public:
int Ver, Pos, Count;
ribItem Rib;
};
 
void addConturs (vector<resItem> &conts, int ver, vector<tRibsItem> &sortRibs)
{
vector< vector<ribItem> > ways;
vector<ribItem> temp;
vector<verItem> vers;
bool work = true;
    while(work)
    {
    bool prev = false;
        if (inPrevVers(ver, vers))
        {
        ver = vers.back().Ver;
        ways.push_back(temp);
        temp.pop_back();
        prev = true;
        }
        else if (nextVer(ver, sortRibs))
        {
        int pos = 0;
        verItem it; it.Ver = ver; it.Pos = pos; it.Count = sortRibs[ver].size();
        it.Rib = sortRibs[ver][pos];
        vers.push_back(it);
        temp.push_back(it.Rib);
        ver = it.Rib.Last;
        }
        else if (!overPos(vers.back()))
        {
        bool go = true;
            while(go)
            {
            ver = vers.back().Ver;
            ways.push_back(temp);
            temp.pop_back();
            vers.pop_back();
                if (!vers.size())
                {
                go = false;
                work = false;
                }
            }
        }
        if (prev)
        {
        bool go = true;
            while(go)
            {
                if (overPos(vers.back()))
                {
                int pos = vers.back().Pos + 1;
                vers.pop_back();
                verItem it; it.Ver = ver; it.Pos = pos; it.Count = sortRibs[ver].size();
                it.Rib = sortRibs[ver][pos];
                vers.push_back(it);
                temp.push_back(it.Rib);
                ver = it.Rib.Last;
                go = false;
                }
                else
                {
                ver = vers.back().Ver;
                ways.push_back(temp);
                temp.pop_back();
                vers.pop_back();
                    if (!vers.size())
                    {
                    go = false;
                    work = false;
                    }
                }
            }
        }
    }
AnsiString res;
for (int i = 0; i < ways.size(); i++)
    {
    AnsiString a;
    for (int j = 0; j < ways[i].size(); j++)
        a += (AnsiString)ways[i][j].First + "-" +
                (AnsiString)ways[i][j].Last;
    res += a + "\n";
    }
ShowMessage(res);
}
 
bool overPos (verItem it)
{
if (it.Pos < it.Count-1)
        return true;
return false;
}
 
bool nextVer (int ver, vector<tRibsItem> &sortRibs)
{
if (sortRibs[ver].size())
        return true;
return false;
}
 
bool inPrevVers (int ver, vector<verItem> &vers)
{
for (unsigned int i = 0; i < vers.size(); i++)
        if (vers[i].Ver == ver)
            return true;
return false;
}
Вот этот код мне в ways пишет все пути графа, вернее когда пишет, а когда нет, иногда еще в вечном цикле все крутится.

Вдруг кому-то не лень мне помочь, буду очень благодарен.

Добавлено через 3 часа 1 минуту
Решил пока список замутить, его вроде немного попроще заполнить, чем так...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.05.2012, 21:24     Поиск всех контуров в ориентированном графе
Посмотрите здесь:

C++ Удаление цикла в ориентированном графе
Поиск всех циклов в неориентированном графе. C++
C++ найти количество всех путей и контуров графа длиной S
Поиск циклов в графе. Поиск центра взвешенного графа C++
Поиск всех различных путей в графе C++
C++ Ранжирование вершин на ориентированном графе без контуров по отношению к вершине
C++ Алгоритм поиска в глубину в ориентированном графе

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Serg046
21 / 21 / 2
Регистрация: 07.01.2010
Сообщений: 376
04.06.2012, 18:17  [ТС]     Поиск всех контуров в ориентированном графе #2
Вот так пытаюсь дерево забить, но не верно что-то
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
void addConturs (vector<resItem> &conts, int ver, vector<tRibsItem> &sortRibs)
{
vector<tree> Tree;
vector<int> Bottoms;
tree *p;
tree beg; beg.Ver = ver; beg.P = NULL; beg.Pos = 0;
beg.Vers.push_back(ver);
if (beg.Pos < (int)sortRibs[beg.Ver].size())
        beg.NextVer = sortRibs[beg.Ver][beg.Pos].Last;
else
        beg.NextVer = -1;
Tree.push_back(beg);
p = &Tree.back();
bool work = true;
    while (work)
    {
        if ((*p).NextVer != -1)
        {
        int tVer = (*p).NextVer;
            if (findVector(tVer, (*p).Vers) || !sortRibs[tVer].size())
            {
                (*p).Pos++;
                if ((*p).Pos < (int)sortRibs[(*p).Ver].size())
                    (*p).NextVer = sortRibs[(*p).Ver][(*p).Pos].Last;
                else
                    (*p).NextVer = -1;
            }
            else if (sortRibs[tVer].size())
            {
            tree a; a.Ver = sortRibs[tVer][0].Last; a.P = p;
            a.Pos = 0; a.Vers = (*p).Vers;
            a.Vers.push_back(a.Ver);
                if (a.Pos < (int)sortRibs[a.Ver].size())
                    a.NextVer = sortRibs[a.Ver][a.Pos].Last;
                else
                    a.NextVer = -1;
            Tree.push_back(a);
            p = &Tree.back();
            }
            else
                ShowMessage("Непредвиденная ошибка");
        }
        else
        {
            if ((*p).P == NULL)
                work = false;
            else
                p = (*p).P;
        }
    }
}
Добавлено через 1 минуту
Нужно найти все контуры некого ориентированного графа. Сейчас я сделал таким образом. На вход кол-во вершин графа и матрица смежности (как у неориентированного графа (1,0) ). Далее строю неориентированный граф и рандомно выбираю ребра (направления). Далее получил вектор со всеми ребрами (например [1,0][2,3][6,1] и т.д.). Но не могу перебрать правильно.
Может кто подскажет как все проще реализовать?

Добавлено через 1 час 29 минут
Понял что дурак и что для этого существуют рекурсивные функции (а я сам while'ами пытался).
Нашел статью http://e-maxx.ru/algo/dfs
Вот код
C++
1
2
3
4
5
class ribItem
{
public:
int First, Last;
};
C++
1
2
3
4
5
6
7
void dfs(int v, vector<bool> &used, vector< vector<ribItem> > &sortRibs)
{
used[v] = true;
for (unsigned int i = 0; i < sortRibs[v].size(); i++)
    if (!used[sortRibs[v][i].Last])
        dfs(used[sortRibs[v][i].Last], used, sortRibs);
}
Что с ним не так? Он вечно крутиться

Добавлено через 13 минут
хотя иногда норм xD
Yandex
Объявления
04.06.2012, 18:17     Поиск всех контуров в ориентированном графе
Ответ Создать тему
Опции темы

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