[ad_1]
This method draws an Eulerian Circuit from a directed graph. The graph is represented by an array of Deques representing outgoing edges. It does not have to be Deques if there is a more efficient data type; as far as I can tell the Deque is the most efficient implementation of a stack but I could be wrong.
I've tried replacing the ArrayDeques with LinkedLists but it doesn't make any difference.
I've tried keeping an array edgeCount rather than checking the number of nodes using edges[currentVertexNumber].size() > 0. But that makes it slower.
Deque<Integer> makeEulerianCircuit(Deque<Integer>[] edges)
// 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 (edges[currentVertexNumber].size() > 0)
currentPath.push(currentVertexNumber);
Deque<Integer> currentVertex = edges[currentVertexNumber];
int nextVertexNumber = currentVertex.pop();
currentVertexNumber = nextVertexNumber;
else
circuit.add(currentVertexNumber);
currentVertexNumber = currentPath.pop();
return circuit;
Is there anything that can make this faster? Better data structures? A more efficient algorithm? Right now it's not passing the assignment I'm writing it for, and I can't think of anything to make it work more efficiently.
[ad_2]
لینک منبع
