欧拉回路程序java

package hamierton; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Random; public class EularCircuit { public EularCircuit() { } public static void main(String[] args) { // System.out.println("please input n:"); // BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = 4; try { // n = Integer.parseInt(br.readLine()); } catch (Exception ex) { return; } try { Graph g = new Graph(n); g.printg(); g.circuit(); } catch (Exception e) { System.out.println(e.toString()); e.printStackTrace(); return; } } } class Node { private static int count = 0; private String name; private ArrayList adjacencyList; private boolean visited =false; public Node() { name = "node " + count; adjacencyList = new ArrayList(); } public Node(String name) { this.name = name; adjacencyList = new ArrayList(); } public boolean isAllVisited() { for (int i = 0; i < adjacencyList.size(); i++) { SNode sn = (SNode) adjacencyList.get(i); if (sn.visited == false) { return false; } } return true; } public boolean isvisited(){ return visited; } public void setvisited(){ visited = true; } public int getAdjacencyCount() { return adjacencyList.size(); } public boolean contains(int i) { return this.adjacencyList.contains(new SNode(i)); } public void removeAdjacencyNode(int i) { this.adjacencyList.remove(new SNode(i)); } public void addAdjacencyNode(int i) { this.adjacencyList.add(new SNode(i)); } public SNode getAdjacencyNode(int i) { return (SNode) this.adjacencyList.get(i); } public SNode getAdjacencyNodeEX(int i_ref) { for (int i = 0; i < this.getAdjacencyCount(); i++) { if (getAdjacencyNode(i).index == i_ref) { return getAdjacencyNode(i); } } return null; } public String toString() { return this.name; } } class SNode { public boolean visited = false; public int index = 0; public SNode(int index) { this.index = index; } public boolean equals(Object o) { if (((SNode) o).index == this.index) { return true; } return false; } public String toString() { return "adjacency " + index; } } class Graph { private ArrayList nodeList; private ArrayList path; private int count; public Graph(int n) throws Exception { this.count = n; nodeList = new ArrayList(count); ginit(); } public void circuit() { path = new ArrayList(); int top = 0; int k = 0; path.add(new Integer(0)); while (true) { int i, j; i = top; ArrayList path1 = new ArrayList(); path1.add(new Integer(top)); while (true) { Node node = (Node) nodeList.get(i); for (j = 0; j < this.count; j++) { if (node.contains(j) && node.getAdjacencyNodeEX(j).visited == false) { path1.add(new Integer(j)); node.getAdjacencyNodeEX(j).visited = true; // ((Node) nodeList.get(j)).getAdjacencyNodeEX(i).visited = true; i = j; break; } } if (i == top) { break; } } path.remove(k); path.addAll(k, path1); k++; if (k >= path.size()) { break; } top = ((Integer) path.get(k)).intValue(); } for (int z = 0; z < path.size(); z++) { System.out.print(path.get(z).toString() + " "); } } private void ginit() { int i; for (i = 0; i < 4; i++) { nodeList.add(new Node("node" + i)); } ((Node)nodeList.get(0)).addAdjacencyNode(3); ((Node)nodeList.get(1)).addAdjacencyNode(0); ((Node)nodeList.get(2)).addAdjacencyNode(1); ((Node)nodeList.get(3)).addAdjacencyNode(2); // ((Node)nodeList.get(0)).addAdjacencyNode(3); // ((Node)nodeList.get(1)).addAdjacencyNode(0); // ((Node)nodeList.get(2)).addAdjacencyNode(1); // ((Node)nodeList.get(3)).addAdjacencyNode(2); // for (i = 0; i < n; i++) { // nodeList.add(new Node("node" + i)); // } // ArrayList linked = new ArrayList(); // linked.add(new Integer(0)); // Random rand = new Random(); // // for (i = 1; i < n; i++) { // int size = linked.size(); // // int top = ((Integer) (linked.get(size - 1))).intValue(); // Node node = (Node) (nodeList.get(top)); // // while (true) { // int randint = rand.nextInt(n); // if (randint == top) { // continue; // } // if (node.contains(randint)) { // continue; // } else { // if (!linked.contains(new Integer(randint))) { // linked.add(new Integer(randint)); // } else if (node.getAdjacencyCount() >= (linked.size() - 1 > 6 ? 6 // : linked.size() - 1)) { // continue; // } else { // i--; // } // node.addAdjacencyNode(randint); // Node randnode = (Node) nodeList.get(randint); // randnode.addAdjacencyNode(top); // break; // } // } // } // // for (i = 0; i < this.count - 1; i++) { // Node node = (Node) nodeList.get(i); // if (node.getAdjacencyCount() % 2 != 0) { // int j = 0; // for (j = i + 1; j < this.count; j++) { // Node nn = (Node) nodeList.get(j); // if (nn.getAdjacencyCount() % 2 != 0) { // if (node.contains(j)) { // // if (nn.getAdjacencyCount() != 1 // && node.getAdjacencyCount() != 1) { // node.removeAdjacencyNode(j); // nn.removeAdjacencyNode(i); // break; // } else { // continue; // } // } else { // // node.addAdjacencyNode(j); // nn.addAdjacencyNode(i); // break; // } // } // } // // if (j == this.count) { // int k; // Node nk = null; // for (k = i + 1; k < this.count; k++) { // // nk = (Node) nodeList.get(k); // if (nk.getAdjacencyCount() % 2 != 0) { // break; // } // } // int kk = k; // for (k = 0; k < i; k++) { // Node n1 = (Node) nodeList.get(k); // if (!n1.contains(kk) && !n1.contains(i)) { // n1.addAdjacencyNode(kk); // nk.addAdjacencyNode(k); // n1.addAdjacencyNode(i); // node.addAdjacencyNode(k); // break; // } // } // boolean retry = false; // // if (k == i) { // int vv; // for (vv = 0; vv < this.count; vv++) { // Node vn = (Node) nodeList.get(vv); // if (!vn.contains(i) && i != vv) { // vn.addAdjacencyNode(i); // node.addAdjacencyNode(vv); // retry = true; // break; // } // } // if (vv == count) { // for (vv = 0; vv < count; vv++) { // Node vnn = (Node) nodeList.get(vv); // if (vnn.getAdjacencyCount() > 1) { // vnn.removeAdjacencyNode(i); // node.removeAdjacencyNode(vv); // retry = true; // break; // } // } // } // } // if (retry) { // i = -1; // } // } // } // // } // return this.isEularG(); } public boolean isEularG() { boolean isEular = true; for (int i = 0; i < this.count; i++) { Node n = (Node) nodeList.get(i); if (n.getAdjacencyCount() % 2 != 0) { isEular = false; break; } } return isEular; } public void printg() { for (int i = 0; i < this.count; i++) { Node n = (Node) nodeList.get(i); System.out.print(n.toString() + " "); for (int j = 0; j < n.getAdjacencyCount(); j++) { System.out.print(n.getAdjacencyNode(j).toString() + " "); } System.out.println(); } } }