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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Бинарный файл http://www.cyberforum.ru/cpp-beginners/thread592664.html
#include "stdafx.h" #include <string.h> #include <conio.h> struct scan_info { char model; int price; double x_size; double y_size;
C++ Тема Функции. Переделать программы Есть задания на одномерные мессивы и двумерные. 1)Задание и код программы #include <iostream> #include <math.h> using std::cin; using std::cout; using std::endl; http://www.cyberforum.ru/cpp-beginners/thread592658.html
C++ надо переделать
#include <iostream> #include <math.h> #include <conio.h> using namespace std; class chetbIreh_ugolnik { public: chetbIreh_ugolnik(); ~chetbIreh_ugolnik(); void dl_storon(); double diagonal();
C++ Вычислить площадь правильного шестиугольника со стороной а, используя подпрограмму вычисления площади треугольника.через stdafx.h
Вычислить площадь правильного шестиугольника со стороной а, используя подпрограмму вычисления площади треугольника.через stdafx.h..очень срочно!!!!!
C++ Чтение данных из бинарного файла http://www.cyberforum.ru/cpp-beginners/thread592622.html
программа должна считывать данные из бинарного файла, записывать их в переменную абстрактного типа данных, описанного в библиотеке, и выводить на экран вот исходник программы: #include<iostream> #include<string.h> #include<conio.h> #include"logbook.h" using namespace std; int main(void)
C++ статья Рихтера http://wm-help.net/books-online/print-page/59464/59464-16.html это 22 глава книге Рихтера раздел Перехват API-вызовов с использованием раздела импорта в тексте я наткнулся вот на это PROC pfnOrig = GctProcAddress(GetModuleHandle("Kernel32"), "ExitProcess"); HMODULE hmodCaller = GetModuleHandle("DataBase.exe"); void RoplaceIATEntryInOrioMod( "Kernel32.dll", // модуль, содержащий... подробнее

Показать сообщение отдельно
Serg046
21 / 21 / 2
Регистрация: 07.01.2010
Сообщений: 376
31.05.2012, 21:24     Поиск всех контуров в ориентированном графе
Нужно найти все контуры.
Контур - путь, у которого начало и конец совпадают. Т.е. например (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 минуту
Решил пока список замутить, его вроде немного попроще заполнить, чем так...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 23:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru