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

Поиск всех различных путей в графе - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Создание класса для обработки информациии о товарах http://www.cyberforum.ru/cpp-beginners/thread1206101.html
- Создать класс для обработки информации о товарах. - Для каждого товара указывается наименование, объём партии, цена единицы товара. - Создать массив объектов класса, содержащий сведения о нескольких товарах. - Найти товар с самым наименьшим/наибольшим объёмом партии и вывести на экран его суммарную стоимость и цену единицы товара. -------------------------------------------------------...
C++ Namespace, содержимое переменной Уважаемые, подскажите как посмотреть содержимое переменной, т.е. допустим есть такой код: namespace data { int data; void initData() { data = 100; } http://www.cyberforum.ru/cpp-beginners/thread1206084.html
C++ Syntax error : missing ')' before ';'
пишу программу подсчета значения функции, вроде уже везде где надо поставила скобочки, ковычки и завершающие ; пишет ошибку syntax error : missing ')' before ';' #include <stdio.h> #include <math.h> int main(void) { int x = 3, q = 2;
C++ Классы: передача объекта в функцию
class Distance // длина в английской системе { private: int feet; float inches; public: // конструктор без аргументов void showdist()const // вывод длины { cout << feet << "\'-" << inches <<'\"'; } Distance add_dist(const Distance&) const; // сложение };
C++ буду благоларен http://www.cyberforum.ru/cpp-beginners/thread1206038.html
Даны натуральное число п, действительные чи¬сла x1, ..., x3n. Последовательность чисел х1, ..., x3n. определяет на плоскости п квадратов со сторонами, па¬раллельными координатным осям: так, x1, х2—координаты центра первого квадрата, x3—длина его стороны; анало¬гично, числа x4, х5, x6 определяют второй квадрат, x7, x8,x9—третий и т. д. Имеются ли точки, принадлежащие всем квадратам? Если да, то...
C++ Как объявить безразмерную матрицу Здравствуйте, мне надо написать функцию которая работает с массивом вида char txt, как обьявить эту переменную в функции. Я не знаю размеров массива, а например void set(char txt) пишет - "массив не может содержать элементы этого типа". подробнее

Показать сообщение отдельно
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
14.06.2014, 23:00     Поиск всех различных путей в графе
Ваша идея верна, решение "в лоб" рекурсивным спуском достаточно простое. Не самое оптимальное по памяти и сложности, но компактное по коду и объяснению.
Отобразим граф в память списками смежности. То есть для каждой ноды будем хранить список "дочерних" нод. Это удобно делать с помощью стандартного контейнера vector. С другой стороны каждой ноде соответсвует свой список смежности, то есть можно говорить о парах ключ-значение, где ключ - имя ноды, а значение - vector "дочерних" нод. Для такой структуры данных существует контейнер map, и полностью граф представляется так: CPP]std::map<int,std::vector<int>> graph;[/CPP]
Задача решается в два действия: нужно поднять данные из фаила в память:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//fname - абсолютный или относительный путь к фаилу
void init_graph(std::string fname, std::map<int,std::vector<int>> &g)
{
    std::ifstream in(fname,std::ifstream::in);
    int init , fin;
    in >> init >>fin; // тут просто выкидываем строки с количеством ребер и узлов -- нам не нужны. 
    while( in.good() )
    {
        in>>init>>fin;
        g[init].push_back(fin);//добавляем fin в список смежности узла init
        g[fin]; //конец дуги тоже узел. (появится, если не было, ничего не случится, если был.)
    }
    in.close();
}
рекурсивня функция поиска имеет вид:
C++
1
void foo(int init_node, int fin_node, std::map<int,std::vector<int>> &graph, std::string path)
init_node - имя ноды для которой вызывается поиск, fin_node - имя ноды пути к которой нужно найти, std::map<int,std::vector<int>> &graph - ссылка на граф смежности, std::string path - путь который прошли рекурсивные вызовы (не очень хорошо передавать его строкой, зато очень просто).
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void foo(int init_node, int fin_node, std::map<int,std::vector<int>> &graph, std::string path)
{
    path += std::to_string(init_node) + " "; // добавляем в путь текущую ноду
 
    if (init_node == fin_node)
    {
        //путь найден, печатаем и возвращаемся.        
        std::cout<<path<<std::endl;
        return;
    }
 
    if (graph[init_node].empty())
        return; // Это сток графа, путь не найден
 
    //рекурсивно продолжаем поиск для дочерних нод 
    for (auto subnode:graph[init_node])
    {
        foo(subnode,fin_node,graph,path);
    }
    return;
}
собственно, осталось только вызвать из main() с нужными параметрами, и добавить бантиков что-то вроде:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{
    std::map<int,std::vector<int>> graph;
    std::string fname = "./data.file";
 
    //читаем дуги из фаила
    init_graph(fname,graph);
 
    //спрашиваем о пути
    int start, end;
    std::cout<<"узлы начала и конца через пробел: ";
    std::cin>>start>>end;
    
    //вычисляем и отображаем пути
    std::string path = "-->: ";
    foo(start,end,graph,path);
    std::cout<<"все варианты проверены"<<std::endl;
    return 0;
}
Ожидается ожидаемое: фаил данных существует и правильно заполнен, дуги не повторяются, граф ациклический и т.п.
---
про хорошие алгоритмы на графах DAG можно почитать у Седжвика или на том же хабре, можно погуглить топологическую сортировку - взятие среза или кеш длинных путей уменьшит объем вычислений, так же любой рекурсивный алгоритм представим в итеративном виде.

бонус:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
void show(std::map<int,std::vector<int>> &graph)
{
    //вывод текущих списков смежности в читабельном виде.
    for(const auto &kvp: graph)
    {
        std::cout << kvp.first << "\t: ";
        for(auto v: kvp.second)
            std::cout << v << " ";
        std::cout<<std::endl;
    }
}
 
Текущее время: 15:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru