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

@Serg046 · Регистрация: 07.01.2010

Студворк — интернет-сервис помощи студентам

Нужно найти все контуры.
Контур - путь, у которого начало и конец совпадают. Т.е. например (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 минуту
Решил пока список замутить, его вроде немного попроще заполнить, чем так...

@Serg046 · 04.06.2012, 18:17 **[ТС]**

Вот так пытаюсь дерево забить, но не верно что-то

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

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .