Форум программистов, компьютерный форум 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...
C++ Вычислить площадь правильного шестиугольника со стороной а, используя подпрограмму вычисления площади треугольника.через stdafx.h
Вычислить площадь правильного шестиугольника со стороной а, используя подпрограмму вычисления площади треугольника.через stdafx.h..очень срочно!!!!!
C++ Чтение данных из бинарного файла http://www.cyberforum.ru/cpp-beginners/thread592622.html
программа должна считывать данные из бинарного файла, записывать их в переменную абстрактного типа данных, описанного в библиотеке, и выводить на экран вот исходник программы: #include<iostream>...
C++ статья Рихтера http://wm-help.net/books-online/print-page/59464/59464-16.html это 22 глава книге Рихтера раздел Перехват API-вызовов с использованием раздела импорта в тексте я наткнулся вот на это PROC pfnOrig... подробнее

Показать сообщение отдельно
Serg046
21 / 21 / 2
Регистрация: 07.01.2010
Сообщений: 376
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
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru