欧拉电路算法

Question

这种方法从有向图中画出欧拉电路。该图形由表示传出边的Deques数组表示。如果有更有效的数据类型，就不必是Deques；据我所知，Deque是堆栈最有效的实现，但我可能错了。

我试过用ArrayDeques代替LinkedLists，但没什么区别。

我尝试保留一个数组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 makeEulerianCircuit(Deque[] 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 currentPath = new ArrayDeque<>();

        // queue for the final circuit
        Deque 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[] edges = new Deque[in[0]];
        for(int i=0;i();
        }

        // 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 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行中的每一行都指定了格式为“u”的边。(和往常一样，我们假设图的顶点是{1，2，。。。，(N)图可以包含自循环(即形式(v，v)的边)和平行边(即同一边的几个副本)。保证了图是强连通的。制约因素。1≤n≤104；n≤m≤105；1≤u，v≤n.输出格式。如果图没有欧拉循环，输出0。否则，第一行输出1和序列v1，v2，。。。，第二行中顶点的vm。此序列应遍历图中的欧拉循环：(v1，v2)，(v2，v3)，。。。，(vm−1，vm)，(vm，−)都应该是图的边，图的每条边都应该在这个序列中出现一次。与往常一样，图可能包含许多欧拉圈(特别是，每个欧拉圈可能从其任意一个顶点开始遍历)。你可以输出其中的任何一个。

下面是一些示例输入:输入：

3 4 2 3 2 2 1 2 3

输出：

1 1 2 2 3

我还更新了上面的内容，包括了整个程序。

Answer 1

(通常考虑un_directed有限图的欧拉回路。)问题是标记为java --虽然所显示的代码的_syntax看起来是类型，但是变量处理看起来是Fortran。makeEulerianCircuit()和(inputAndPrintCircuit)是实例成员--不必要。虽然有一个抽象输入& print可能很有用，但是让它打印一个非平凡算法的结果看起来很奇怪。指定并实现一个input()方法(并使用尝试使用资源处理输入)。inputAndPrintCircuit()将顶点数与问题语句不同--不要。为什么要有一个数组in[]来保存具有不同意义的输入值？只需使用nVertices和nEdges。同样，考虑使用nOutgoing[]和nIncoming[]而不是二维数组。(给定输出边集合的恒定时间size()，您可以不使用nOutgoing[]。)正如我喜欢的代码注释一样：// empty graph是多余的(我会在条件语句之前删除注释，让// empty graph注释条件(稍微夸大问题--没有边的连通图仍然可能包含一个顶点；输入规范: nVertices≤nEdges))。您不需要int nextVertexNumber --直接将edges[currentVertexNumber].pop()分配给currentVertexNumber。我认为makeEulerianCircuit()依赖于指定一个(强)连通图的edges[]：它的doc注释应该反映这一点。

另一种设计将引入一个class Vertex，每个实例都包含可以从这个实例到达的各种其他顶点。

到目前为止，我还没有试图说服自己，makeEulerianCircuit()确实为每个连通的“偶数”图组装了一个欧拉电路--部分原因是问题中缺少测试支架。

Is there anything that can make this faster? Better data structures? A more efficient algorithm? --我认为这实现了O中的Hierholzer算法 (m)(在D24中稍微挥动一下手，就可以将m边加到ArrayDeque中，占用Θ(mlogm)时间--常量“永不”，从而使LinkedList变得更快)。(如果这是真的，就不应该有性能问题--我真的应该设置一个测试。)