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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вставить функцию в программу! http://www.cyberforum.ru/cpp-beginners/thread392986.html
Помогите пжлст вставить функцию в программу #include <stdio.h> #include <locale.h> float func (float x, float eps) { return (x + eps); } void tabul (float a, float b, int n, float eps) {...
C++ Сортировка подсчётом Нужно написать функцию для сортировки одномерного массива подсчётом(простой алгоритм). http://www.cyberforum.ru/cpp-beginners/thread392967.html
Зеркально отразить ее элементы относительно побочной диагонали. C++
Дана квадратная матрица A порядка M. Зеркально отразить ее элементы относительно побочной диагонали. (при этом элементы побочной диагонали останутся на прежнем месте, элемент A1,1 поменяется местами...
C++ Непонятные знаки
Обьясните пожалуйста, что значит *char (char - любая переменная). Очень часто вижу в разных кодах.
C++ С++ и метод исключения Гаусса http://www.cyberforum.ru/cpp-beginners/thread392949.html
Помогите плиз написать программу для РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ МЕТОДОМ ИСКЛЮЧЕНИЯ ГАУССА.пожалуйста!!!!!!!!!!!! Есть доп.инфо. которая думаю поможет ст.290 ...
C++ Найти минимальный элемент для каждой ее диагонали Дана квадратная матрица A порядка M. Найти минимальный элемент для каждой ее диагонали, параллельной главной (начиная с одноэлементной диагонали A1,M). подробнее

Показать сообщение отдельно
e.b0sh
0 / 0 / 0
Регистрация: 27.11.2011
Сообщений: 5

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

28.11.2011, 22:08. Просмотров 2652. Ответов 0
Метки (Все метки)

Задача такая:
Дан ориентированный граф без циклов. Требуется проверить, существует ли в нем путь, прохо-
дящий по всем вершинам.
Первая строка входного файла содержит два целых числа n и m — количество вершин и дуг
графа соответственно. Следующие m строк содержат описания дуг по одной на строке. Ребро но-
мер i описывается двумя натуральными числами bi и ei — началом и концом дуги соответственно

Эту задачу нужно сдать в автоматическую систему проверки. Эта система прогоняет задачу по нескольким тестам и сверяет ответы. Если на каком-то тесте ответ неверный, то задача не принимается. Также там стоит ограничение по времени, т.е. если программа выполняется слишком долго, то задача не принимается.

Я решил эту задачу почти полным перебором, т.е. от каждой вершины графа запустил функцию, похожую на обход в глубину, но это оказалось слишком медленно. Затем я немного оптимизировал программу, запускал обход в глубину только от тех вершин, в которые нельзя попасть из других вершин (такая оптимизация работает, так как в графе нет циклов), но это всё равно оказалось слишком медленно Как можно еще оптимизировать алгоритм? Или, может, нужно использовать совершенно другой подход?

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
#include <iostream>
#include <fstream>
#include <vector>
 
using namespace std;
 
const int N = 100001;
 
int n, m;
int count = 0;
vector<int> graph1[N]; // graph1[i] - список вершин, в которые можно попасть через вершину i
vector<int> graph2[N]; // graph2[i] - список вершин, из которых можно попасть в вершину i
 
bool dfs(int v)
{
    ++count;
    for (int i = 1; i < graph1[v].size(); ++i)
        dfs(graph1[v][i]);
    if (count == n)
        return true;
    else
    {
        --count;
        return false;
    }
}
 
bool hamiltonian()
{
    for (int i = 1; i <= n; ++i)
        if (graph2[i].size() == 1) // Если в вершину i нельзя попасть из любой другой вершины
            if (dfs(i))
                return true;
    return false;
}
 
int main()
{
    ifstream in("hamiltonian.in.txt");
    ofstream out("hamiltonian.out.txt");
 
    int i, u, v;
    in >> n >> m;
    for (i = 0; i <= n; ++i)
        graph1[i].push_back(i);
    for (i = 0; i < m; ++i)
    {
        in >> u >> v;
        graph1[u].push_back(v);
    }
 
    for (i = 0; i <= n; ++i)
        graph2[i].push_back(i);
    for (i = 0; i < m; ++i)
    {
        in >> u >> v;
        graph2[v].push_back(u);
    }
 
    if (hamiltonian())
        out << "YES";
    else
        out << "NO";
 
    in.close();
    out.close();
    return 0;
}
Добавлено через 5 часов 18 минут
Неужели никто не знает? Или я разделом ошибся? :\

Добавлено через 23 часа 4 минуты
upupup

Добавлено через 2 часа 36 минут
Моё улучшение было неверно реализовано и даже если его реализовать правильно, то всё равно слишком медленно...
Вопрос по-прежнему остается тем же: как улучшить мой код?
Упрощенный код по-сравнению с предыдущим:
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
#include <iostream>
#include <fstream>
#include <vector>
 
using namespace std;
 
const int N = 100001;
enum COLOR {WHITE, BLACK};
 
int n, m;
int count = 0;
vector<int> graph[N]; // graph1[i] - список вершин, в которые можно попасть через вершину i
 
bool dfs(int v)
{
    ++count;
    for (unsigned i = 1; i < graph[v].size(); ++i)
        dfs(graph[v][i]);
    if (count == n)
        return true;
    else
    {
        --count;
        return false;
    }
}
 
bool hamiltonian()
{
    for (int i = 1; i <= n; ++i)
        if (dfs(i))
            return true;
    return false;
}
 
int main()
{
    ifstream in("hamiltonian.in.txt");
    ofstream out("hamiltonian.out.txt");
    int i, u, v;
    in >> n >> m;
    for (i = 0; i <= n; ++i)
        graph[i].push_back(i);
    for (i = 0; i < m; ++i)
    {
        in >> u >> v;
        graph[u].push_back(v);
    }
    if (hamiltonian())
        out << "YES";
    else
        out << "NO";
    in.close();
    out.close();
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru