可以证明,当算法停止时所得的简单回路Wm=v0e1v1e2….emvm(vm=v0)为G中的一条欧拉回路，复杂度为O(e*e)……
2021-06-23 11:00:11
90KB
1
这是一款基于QT实现的一笔画软件，该项目的背景起源于中国邮递员问题，本程序用来模拟邮递员选择最短路径送完所有快递再回到出发点。具体来说，用户可以通过的工具栏在画板区域进行画点并连线，最后形成的图如果能够一笔画完，本程序将以动画的形式在画板上描绘出一笔画的路径，此即邮递员派送快递的最短路径。
2019-12-21 21:27:22
20KB
1
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;
2019-12-21 19:48:49
7KB
1