Алгоритм эйлеровой цепи


Этот метод рисует Эйлеровой цепи из направленного графа. На графике представлена массивом двусторонней очередью, представляющих исходящих из нее ребер. Это не обязательно должна быть двусторонней очередью, если есть более эффективный тип данных; насколько я могу сказать Дека является наиболее эффективной реализации стека, но я могу ошибаться.

Я пробовал заменять ArrayDequeс LinkedListно это не делает никакой разницы.

Я пытался держать массив edgeCount вместо того, чтобы проверить количество узлов с использованием edges[currentVertexNumber].size() > 0. Но это делает его медленнее.

import java.util.*;



class PrintCircuit{
    /**
     *
     * @param edges list of adjacent vertices for current edges
     * @return circuit in deque list
     */
    Deque<Integer> makeEulerianCircuit(Deque<Integer>[] edges, int numberOfNodes)
    {

        // return empty list for empty graph
        if (edges.length==0)
            return new LinkedList<>(); //empty graph

        // Stack for the path in the current iteration
        Deque<Integer> currentPath = new ArrayDeque<>();

        // queue for the final circuit
        Deque<Integer> circuit = new ArrayDeque<>();

        // start from any vertex
        currentPath.push(0);
        int currentVertexNumber = 0; // Current vertex

        while (!currentPath.isEmpty())
        {
            //if there are outgoing edges
            if (edges[currentVertexNumber].size() > 0)
            {
                currentPath.push(currentVertexNumber);
                int nextVertexNumber = edges[currentVertexNumber].pop();
                currentVertexNumber = nextVertexNumber;
            }

            // otherwise step back
            else
            {
                circuit.add(currentVertexNumber);
                currentVertexNumber = currentPath.pop();
            }
        }

        return circuit;

    }


    public static void main(String[] args)
    {

        PrintCircuit pc = new PrintCircuit();
        pc.inputAndPrintCircuit();

    }


    /**
     * Get the input, check to make sure the graph is even and run the printCircuit function
     */
    private void inputAndPrintCircuit(){
        Scanner scanner = new Scanner(System.in);
        int[] in = new int[2];
        in[0] = scanner.nextInt();
        in[1] = scanner.nextInt();
        Deque<Integer>[] edges = new Deque[in[0]];
        for(int i=0;i<in[0];i++)
        {
            edges[i] = new ArrayDeque<>();
        }

        // evenChecker is a Nx2 array where [0] = incoming edges and [1] = outgoing edges
        //should be equal or graph isn't Eulerian
        int[][] evenChecker = new int[in[0]][2];
        for (int i = 0; i < in[1]; i++) {
            int from = scanner.nextInt()-1;
            int to = scanner.nextInt()-1;
            evenChecker[from][0]++;
            evenChecker[to][1]++;
            edges[from].push(to);

        }
        if(!isGraphEven(evenChecker)){
            System.out.println("0");
            System.exit(0);
        } else {
            System.out.println("1");
        }
        Deque<Integer> circuit = makeEulerianCircuit(edges, in[0]);
        while(circuit.size()>1){
            int nextNode = circuit.pollLast()+1;
            System.out.print(nextNode + " ");
        }
        System.out.println();
    }

    /**
     * checks to make sure that incoming edges = outgoing edges
     * @param evenChecker a Nx2 array where [0] = incoming edges and [1] = outgoing edges
     * @return true if incoming eges = outgoing edges, false otherwise
     */
    private boolean isGraphEven(int[][] evenChecker){
        for(int[] evenCheck:evenChecker){
            if(evenCheck[0]!=evenCheck[1]){
                return false;
            }
        }
        return true;
    }



}

Есть все, что может сделать это быстрее? Лучше структуры данных? Более эффективный алгоритм? Сейчас это не проходит задание, которое я писал, и я не могу думать ни о чем, чтобы сделать его работать более эффективно.

Обновление: Здесь представлены технические задания:

Задач. Дан ориентированный граф, найти Эйлерова цикла в графе, или сообщить, что его не существует.

Формат Ввода. Первая строка содержит целые числа n и M — количество вершин и количество ребер, соответственно. Каждая из следующих M строк определяет ребро в формате “у вьюна”. (Как обычно, мы предполагаем, что вершины графа {1, 2, . . . , п}.) График может содержать петель (то есть, края форме (в, V)) и параллельными краями (то есть несколько копий одного и того же края). Гарантируется, что граф сильно связный.

Ограничений. 1 ≤ н ≤ 104 ; Н ≤ М ≤ 105 ; 1 ≤ U, В ≤ Н.

Выходной Формат. Если граф не имеет Эйлерова цикла, то вывести 0. В противном случае выход 1 в первой строке и последовательность В1, В2 . . . ВМ вершин во второй строке. Эта последовательность должна пройти Эйлерова цикла в графе: (В1, В2),(В2, В3), . . . ,(ВМ−1, ВМ),(ВМ, В1) все должны быть ребра и каждое ребро график должен появиться в этой последовательности ровно один раз. Как обычно, график может содержать множество Эйлера циклов (в частности, каждый Эйлерового цикла может быть пересечена, начиная с любой его вершины). Вы можете выведите любую из них.

Вот некоторые примеры ввода: Вход:

3 4

2 3

2 2

1 2

3 1

Выход:

1

1 2 2 3

Я также обновил выше, чтобы включать всю программу.



357
0
задан 3 марта 2018 в 05:03 Источник Поделиться
Комментарии
2 ответа

Это будет производительность ценой читабельности поста, вижу явные похвалы за комментарии, только для обычного анализа кода.
Есть всегда несколько "microefficiencies" можно переживать и не стоит, по крайней мере, не до всех больше очков заботятся, и проблема сохраняется.
Еще, желательно, чтобы начать с упором на читабельность и улучшить алгоритм есть.
Одна вещь, которая может поймать горе-производительность кодера врасплох Ява Ио производительности - в частности, java.util.Scanner "избили". (Я не пытался делать полезные измерений, я подозреваю, что это сравнительно плохо только с больших входных файлов и никакой буферизации.) Так:

/** Parses InputStream for smallish natural numbers: <code>charС.
* Пропускает не-цифры; возвращает -1 - '0' в конец файла */
класс символов { логическое hasCurrent; Чара тока;
окончательный Ява.Ио.InputStream в;
Символы() { это(система.в); }
Чарс(Ява.Ио.InputStream в) {
это.в = В оператор instanceof в Java.Ио.BufferedInputStream
? в : новый Java.Ио.BufferedInputStream(в);
}
/** @обратного тока char. */
общественные чар тока() {
если (!hasCurrent)
бросить новый к RuntimeException("нет текущий символ");
обратного тока;
}
/** @вернуться в следующем char. */
публичных чар следующий() {
попробовать { инт с, n = 0;
хотя (!Характер.isDigit(С = в.читать()))
если (-1 == С) // ВФ
Break; // все бросить? возвращает 0?
н = с - '0';
пока (персонажа.isDigit(С = в.читать()))
Н = 10*н + с - '0';
hasCurrent = истина;
ток = (char), в Н;
} поймать (исключение IOException е) { бросить новый к RuntimeException(е); }
}
}

Другой момент-это размещение памяти на каждом уровне иерархии. В Constraints читать число не превышает 105 - short или char надо сделать штраф вместо int.
Вместо подсчета входящего и исходящего ребра отдельно, держать баланс (увеличивается на одну, уменьшается для других): график не Eularian если остаток отличен от нуля после ввода.
Как правило, создать "основу коллекции Java-классы" использование ожидаемого размера, где это возможно. Здесь нет вершин будет больше, чем г-н ребер, - но даже инстанцирования Н "массив-коллекция"с, что размер Θ(н*м). Не указание мощности приводит к Θ(mlogm) если "почти все" ребра из одной вершины.
java.util.LinkedList<E> должна быть линейной, но с высокими коэффициентами - так:

/** Graph vertex keeping a <code>List из преемников.
* (Только add() и iterator() являются полезными.) */
статический класс вершинного расширяется Java.утиль.AbstractList
реализации Java.утиль.Итератор/ / Список
{
Метка объект;
узел статического класса {
Узел;
окончательной вершины v;
публичных узел(вершина V, узел) {
это.в = в;
это.следующий = следующий;
}
@Переопределить
общественного строка toString() {
возвращение нового класса StringBuilder("П").добавление(В. метки).метод toString();
}
}
Вершины.Первый узел;
// статический класс итератор реализует Java.утиль.Итератор{
Вершины.Узел;
// общественных итератор(вершины.Узел первый) { следующий = первый; }
общественная логическое hasNext() { возвращать значение null != следующий; }
общественные вершины следующий() {
Вершина ток = далее.в;
следующий = следующая.далее;
обратного тока;
}
// }

общественные вершины(объекта) { это.метка = метка; }
статический публичный окончательной вершины[]никто = {};
@Переопределить
общественного строка toString() {
возвращение нового класса StringBuilder("V_").добавить(метка).метод toString();
}

@Переопределить
общественная логическое сложение(вершина V) {
первый = новый узел(в первую очередь);
возвратите True;
}
@Переопределить
общественные итератора итератор() {
следующий = первый;
возвращение этого;
}
@Переопределить
общественные вершины вам(индекс инт) { возвращать значение null; }
@Переопределить
размер государственной инт() { возвращать значение null == первый ? 0 : 1; }
}

(Было бы использовать массивы, только - "Фортран", не в настоящее время чувствую, что кодирование это.)
Используя выше Vertex и открыть закодированные стека:

/** @param vertices (index 0 shall not be used)
* @param totalEdges total number of edges
* @return circuit */
static Vertex[]
makeEulerianCircuit(Vertex[] vertices, int totalEdges) {
if (vertices.length == 0) // empty graph
return Vertex.NONE;
// Stack for the path in the current iteration
Vertex[] currentPath = new Vertex[totalEdges];//nVertices may be too low
int top = -1;
// final circuit
Vertex[] circuit = new Vertex[totalEdges];
int visit = circuit.length;
// start from any vertex
Vertex currentVertex = vertices[1];
while (true) {//currentVertex.iterator()
if (currentVertex.hasNext()) { // there is another outgoing edge
currentPath[++top] = currentVertex;
currentVertex = currentVertex.next();
} else { // otherwise step back
circuit[--visit] = currentVertex;
currentVertex = currentPath[top--];
if (top < 0)
return circuit;
}
}
}

1
ответ дан 6 марта 2018 в 01:03 Источник Поделиться

(Обычно, Эйлеровой цепи является для ООН, направленных конечных графах.)
Вопрос с тегами то время как синтаксис кода показали, выглядит типа, переменной обработки выглядит Фортран.
makeEulerianCircuit() и (inputAndPrintCircuit) являются экземпляре членами - напрасно. Хотя это может быть полезно иметь абстракция ввод и печать, имея его распечатать результат нетривиальный алгоритм выглядит странно. Определить и внедрить input() способ (и обработки ввода с использованием попробовать с ресурсами).
inputAndPrintCircuit() смены вершинных чисел отличается от постановки задачи - нет.
Почему есть массив in[] провести входные значения, которые имеют разный смысл? Просто использовать nVertices и nEdges. Аналогичным образом, рассмотрите возможность использования nOutgoing[] и nIncoming[] вместо двумерного массива. (С учетом постоянной времени size() для коллекции исходящих ребер, можно обойтись без nOutgoing[].)
Насколько мне нравится код прокомментировал: // empty graph избыточна (я бы бросить комментарий перед условный оператор и пусть // empty graph комментарий состояние (слегка преувеличиваешь проблему - связный граф без ребер может содержать одну вершину; ввод спецификаций: nVertices ≤ nEdges).)
Вам не нужно int nextVertexNumber - назначить edges[currentVertexNumber].pop() для currentVertexNumber напрямую.
Я думаю makeEulerianCircuit() зависит от edges[] указания (сильно) связный граф: его комментарий документа должны отражать это.

Альтернативный дизайн будет ввести class Vertexкаждый экземпляр держит ассортимент других вершин, которые могут быть достигнуты от этого.

До сих пор, я и не пытался убедить себя makeEulerianCircuit() действительно, собрать Эйлеровой цепи для каждого подключенного "даже" график - частично из-за отсутствия тест на эшафот на вопрос.

Is there anything that can make this faster? Better data structures? A more efficient algorithm?
Я думаю, что это реализует Хиргольцер алгоритм за O(m) (С немного силы-баловались с добавлением до М - Н ребер к ArrayDeque принимая Θ(mlogm) время - с константами "никогда", позволяющий LinkedList чтобы быть быстрее). (Если бы это было правдой, там не должно быть проблемы с производительностью - я должна действительно создать тест.)

0
ответ дан 4 марта 2018 в 04:03 Источник Поделиться