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

@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

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод Сайт называется reddit: The Thinkpad X220 Tablet is the best budget school laptop period. Это. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .