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(); } } } 根据提供的文件信息,本文将对“欧拉回路程序java”进行详细解析,涉及的知识点主要包括:欧拉路径与欧拉回路的概念、Java程序设计基础、数据结构(如图和节点)、算法实现(欧拉回路算法)等。 ### 欧拉路径与欧拉回路 #### 定义 - **欧拉路径**:在一个无向图或有向图中,如果存在一条路径,经过每条边恰好一次,这条路径称为欧拉路径。 - **欧拉回路**:如果这条路径同时又是闭合的,即起点和终点相同,则这条路径称为欧拉回路。 #### 特征 一个无向图存在欧拉回路的条件是: - 图是连通的; - 图中的所有顶点的度数都是偶数。 ### Java程序设计基础 Java是一种广泛使用的面向对象编程语言。本例中,使用了以下Java特性和类库: - **包声明**:`package hamierton;` - **导入语句**:导入了`java.io.BufferedReader`和`java.io.InputStreamReader`用于读取控制台输入;`java.util.ArrayList`用于动态数组的处理。 - **类定义**:定义了三个类`EularCircuit`、`Node`和`SNode`以及`Graph`,分别用于主程序、节点表示、简单节点表示和图表示。 ### 数据结构与算法实现 #### `Node`类 - 表示图中的一个节点。 - 属性包括:节点名称`name`、邻接列表`adjacencyList`、是否访问过`visited`。 - 方法包括:添加、移除、查询邻接节点、判断是否所有邻接节点都被访问过等。 #### `SNode`类 - 表示节点的邻接节点。 - 属性包括:是否访问过`visited`、节点索引`index`。 - 实现了`equals`方法来比较两个邻接节点是否相等。 #### `Graph`类 - 代表一个图。 - 属性包括:节点列表`nodeList`、路径列表`path`。 - 方法包括:初始化图`ginit`、生成欧拉回路`circuit`、打印图`printg`、判断是否为欧拉图`isEularG`。 - **初始化图`ginit`**:构造了一个包含四个节点的图,并设置了节点间的连接关系。 - **生成欧拉回路`circuit`**:该方法采用了一种基于深度优先搜索的算法来查找欧拉回路。具体过程为:从第一个节点出发,沿着未被访问过的边一直前行,直到回到起始点。这个过程中不断更新路径列表`path`,直到所有的边都被访问过。 - **打印图`printg`**:遍历图中的每个节点,输出节点名及与其相邻的所有节点名。 - **判断是否为欧拉图`isEularG`**:检查图中每个节点的度数是否都为偶数,以此判断该图是否存在欧拉回路。 ### 总结 本Java程序实现了对欧拉回路的查找功能。通过定义节点类`Node`、简单节点类`SNode`和图类`Graph`,并结合算法逻辑,实现了从指定节点出发寻找图中的欧拉回路的过程。对于理解欧拉路径与欧拉回路的基本概念及其在实际问题中的应用具有重要意义。此外,程序中还展示了如何利用Java的数据结构(如`ArrayList`)和控制结构来实现算法逻辑,这对于学习Java编程也有很大帮助。
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;
剩余11页未读,继续阅读
- 粉丝: 0
- 资源: 1
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助