【程序背景】最近在做子图匹配的实验，对查询图需要进行预处理，得到最小生成树，然后进行后续的子图匹配工作，由于匹配过程是按照顺序依次遍历匹配的，当时程序就卡在寻找一条顺序相连的最小生成树问题上了，查了很多关于欧拉路径的解决方案，觉得过于复杂，干脆最后自己写了一个小程序，“解决”了。
【重要说明】程序还是有bug的，查询图不大的时候发现不了，但是当规模一扩大，问题就暴露了，原来最小生成树并不一定存在欧拉路径，没办法完成一笔画问题！
不过这个程序完成一些小规模的实验还是可以，就此保留吧。
【问题说明】输入list：（2,6）（1,3）（1,2）（4,5）（1,4）
得到newlist：（4,5）（1,4）（1,3）（1,2）（2,6）
【实验环境】eclipse+Java
【算法思路】list是最小生成树，newlist是需要得到顺序相连的欧拉路径，注意最小生成树一定是连通图，即一定存在欧拉路径
* 第一步--->取list中的第一条边，遍历剩余边，寻找与该边相连接的所有边，add到newList中 * 第二步--->取list中的剩余边edge，与newList中的边进行比较 * 1-->如果edge与newlist的第一条边相连，直接newList.add(0,edge)，在头插入，然后删除list中的edge * 2-->如果edge与newlist的最后一条边相连，直接newList.add(edge)，在尾插入，然后删除list中的edge * 3-->如果edge与newlist中间的一条边相连，先把newlist中的那条边移动到尾部，再进行插入删除操作 * 4-->如果都不相连，去list的下一条边进行上述操作，直至最后list集合为空为止。
【代码说明】代码中有一个Edge类--->Edge（CITING，CITED），表示一条边，专利的引用关系。
public class Edge { private String CITING; private String CITED; public Edge(String CITING,String CITED){ this.CITING = CITING; this.CITED = CITED; } public String getCITING() { return CITING; } public void setCITING(String cITING) { CITING = cITING; } public String getCITED() { return CITED; } public void setCITED(String cITED) { CITED = cITED; } public boolean equals(Edge obj) { // TODO Auto-generated method stub String citing = obj.getCITING(); String cited = obj.getCITED(); if(CITING.equals(citing)&&CITED.equals(cited)) return true; else return false; } public boolean isExistOf(String str){ if(str.equals(CITING)||str.equals(CITED)) return true; else return false; } public boolean isLinked(Edge e){ if(e.getCITING().equals(CITING)||e.getCITING().equals(CITED)|| e.getCITED().equals(CITING)||e.getCITED().equals(CITED)) return true; else return false; } public String toString(){ return CITING +" -> "+CITED; } }【实验代码】
import java.util.ArrayList; /** * @author Coraline * 算法---寻找最小生成树的欧拉路径，即一笔画问题 * 遍历所有的边仅一次，边前后相连 * 算法思路： * 第一步--->取list中的第一条边，遍历剩余边，寻找与该边相连接的所有边，add到newList中 * 第二步--->取list中的剩余边edge，与newList中的边进行比较 * 1-->如果edge与newlist的第一条边相连，直接newList.add(0,edge)，在头插入，然后删除list中的edge * 2-->如果edge与newlist的最后一条边相连，直接newList.add(edge)，在尾插入，然后删除list中的edge * 3-->如果edge与newlist中间的一条边相连，先把newlist中的那条边移动到尾部，再进行插入删除操作 * 4-->如果都不相连，去list的下一条边进行上述操作，直至最后list集合为空为止。 */ public class Main { public static void main(String[] args) throws Exception { //算法测试数据 ArrayList<Edge> list = new ArrayList<>(); list.add(new Edge("2", "6")); list.add(new Edge("1", "3")); list.add(new Edge("1", "2")); list.add(new Edge("4", "5")); list.add(new Edge("1", "4")); //用于存放重新排序之后的结果集合 ArrayList<Edge> newlist = new ArrayList<>(); Edge e1 = list.get(0); list.remove(0); newlist.add(e1); String citing = e1.getCITING(); String cited = e1.getCITED(); //第一步，选取第一条边，取得所有与该边相连的所有连边，add到newlist for(int i =0;i<list.size();i++){ if(list.get(i).isExistOf(citing)){ newlist.add(0,list.get(i)); list.remove(i); i--; } else if(list.get(i).isExistOf(cited)){ newlist.add(list.get(i)); list.remove(i); i--; } } System.out.println("newlist"); for (Edge edge : newlist) { System.out.println(edge.toString()); } System.out.println("list"); for (Edge edge : list) { System.out.println(edge.toString()); } //第二步，从剩余边中依次进行判断，有序加入到newlist中 int point = 0;//设置一个指针，指明当前进行判断的记录 while(!list.isEmpty()){ e1 = list.get(point); citing = e1.getCITING(); cited = e1.getCITED(); for(int i =0 ;i<newlist.size();i++){ //如果list(point)与newlist中的记录是相连的 if(newlist.get(i).isExistOf(citing)||newlist.get(i).isExistOf(cited)){ //相连的记录在newlist的头部，直接在头部插入 if(i == 0){ newlist.add(0,e1); list.remove(point); point=-1;//注意指针要回归到-1 break; } //相连的记录在newlist的尾部，直接在尾部插入 else if(i == newlist.size()-1){ newlist.add(e1); list.remove(point); point=-1;//注意指针要回归到-1 break; } //相连的记录不在头尾的，先调整顺序至于尾部，再插入 else{ newlist.add(newlist.get(i)); newlist.remove(i); newlist.add(e1); list.remove(point); point=-1;//注意指针要回归到-1 break; } } } point++;//指针下移，判断下一个结点 } System.out.println("newlist"); for (Edge edge : newlist) { System.out.println(edge.toString()); } System.out.println("list"); for (Edge edge : list) { System.out.println(edge.toString()); } } }
