Предложения, необходимые для улучшения алгоритма эйлерова пути для проблемы доставки почты CSES

Question

У меня превышен лимит времени для моего решения по доставке почты CSES для некоторых тестовых случаев.

Ваша задача – доставить почту жителям города. По этой причине вам нужно найти маршрут, начальной и конечной точкой которого является почтовое отделение, и который проходит через каждую улицу ровно один раз.

По сути, проблема требует поиска эйлерова пути. Для алгоритма я сослался на следующее описание алгоритма Хирхольцера: ссылка

Ниже приведены некоторые фрагменты кода моего решения:

              LinkedList<Integer> adj[] = new LinkedList[n];

        ArrayDeque<Integer> s = new ArrayDeque<>();
        s.push(0);
        int curr_v = 0;
        int g[][] = new int[n][n];
        boolean flag = false;
        while (!s.isEmpty()) {

            flag = false;
            while(adj[curr_v].size() > 0) {
                //System.out.println(curr_v);
                int next_v = adj[curr_v].remove();
                if(g[curr_v][next_v] == 1){
                    continue;
                }
                flag = true;
                s.push(curr_v);
                g[curr_v][next_v] = 1;
                g[next_v][curr_v] = 1;
                curr_v = next_v;
            }
            if(!flag){
                circuit.add(curr_v + 1);
                curr_v = s.pop();
            }
        }

Полный код можно найти по ссылке «Моя отправка».

Может кто-нибудь подсказать мне, как я могу улучшить приведенный выше код, чтобы пройти все тесты?

Answer 1

Самая первая теорема теории графов была сформулирована в 1735 году Леонардом Эйлером .

Проблема была известна как «Семь мостов Кенигсберга ». [80] Город Кенигсберг в Пруссии был расположен на реке Прегель и включал в себя два больших острова, которые были соединены друг с другом и материком семью мостами. Задача состоит в том, чтобы решить, можно ли следовать по пути, который пересекает каждый мост ровно один раз и возвращается в исходную точку. Это невозможно: эйлеровой схемы не существует .

В терминах современной теории графов задача состоит в том, чтобы определить, имеет ли каждый узел одинаковую входную степень с исходящей степенью. Если они равны, то каждый раз, когда путь достигает узла, должно оставаться неиспользованное ребро, позволяющее покинуть его.

Проницательность Эйлера позволяет разработать алгоритм для поиска схемы Эйлера, если она существует, что почти тривиально.

Алгоритм:

      ASSERT graph directed
ASSERT in-degree == out-degree for all vertices
SET vertex to first
WHILE true
    ADD vertex to circuit  
    FIND next vertex along unused edge
    MARK edge used
    IF no unused edge
        STOP

Сигнатура метода C++

          /// @brief  Find euler path through graph
    /// @param g graph
    /// @return vector of vertex indices on path
    /// If no euler path, exception thrown
    
    std::vector<int> euler( const cGraph& g);

Модульный тест:

      TEST(Euler2)
{
    raven::graph::cGraph g;
    g.directed();
    g.findorAdd("0","1");
    g.findorAdd("0","6");
    g.findorAdd("1","2");
    g.findorAdd("2","0");
    g.findorAdd("2","3");
    g.findorAdd("3","4");
    g.findorAdd("4","2");
    g.findorAdd("4","5");
    g.findorAdd("5","0");
    g.findorAdd("6","4");

    auto act = euler(g);

    CHECK_EQUAL(8, act.size());

    std::vector<std::string> exp1 { "0", "1", "2", "0", "6", "4", "2", "3", "4", "5", "0" };

    auto sact = g.userName( act );

    CHECK(std::equal(
            exp1.begin(),
            exp1.end(),
            sact.begin()));
}

Реализация С++:

         std::vector<int> euler(const cGraph &g)
        {
            // firewall
            if (!g.isDirected())
                throw std::runtime_error(
                    "euler:  needs directed graph ( 2nd input line must be 'g')");
            for (int vi = 0; vi < g.vertexCount(); vi++)
                if (g.adjacentIn(vi).size() != g.adjacentOut(vi).size())
                    throw std::runtime_error(
                        "euler: every vertex in-degree must equal out-degree");

            // working copy of graph
            cGraph work = g;

            // list to store circuit
            std::vector<int> circuit;

            // start at first vertex
            int curr_v = 0;

            while (1)
            {
                // add vertex to circuit
                 circuit.push_back(curr_v);

                // find next vertex along unused edge
                auto vadj = work.adjacentOut(curr_v);
                if (!vadj.size())
                    break;
                int next_v = vadj[0];

                // remove used edge
                work.remove(work.find(curr_v, next_v));

                // continue from new vertex
                curr_v = next_v;
            }

            return circuit;
        }

Полный код приложения:

https://github.com/JamesBremner/PathFinder

Код для генерации случайных графов Эйлера с указанным количеством узлов:

      void genEuler(const std::vector<std::string> &q)
{
    int vmax = atoi(q[1].c_str());
    theGraph.clear();
    theGraph.directed();
    for (int k = 0; k < vmax; k++)
    {
        theGraph.add("V" + std::to_string(k));
    }    
    int v1 = 0;
    for( int k = 0; k < vmax; k++ )
    {
        int v2 = v1;
        while( v2 == v1)
            v2 = rand() % vmax;
        theGraph.addEdge(v1,v2);
        v1 = v2;
    }
    theGraph.addEdge(v1,0);
}

Результаты производительности: