java搜索无向图中两点之间所有路径的算法
程序员文章站
2024-02-23 12:33:16
参考 ,对代码进行了部分修改,并编写了测试用例。
算法要求:
1. 在一个无向连通图中求出两个给定点之间的所有路径;
2. 在所得路径上不能含有环路或重复的...
参考 ,对代码进行了部分修改,并编写了测试用例。
算法要求:
1. 在一个无向连通图中求出两个给定点之间的所有路径;
2. 在所得路径上不能含有环路或重复的点;
算法思想描述:
1. 整理节点间的关系,为每个节点建立一个集合,该集合中保存所有与该节点直接相连的节点(不包括该节点自身);
2. 定义两点一个为起始节点,另一个为终点,求解两者之间的所有路径的问题可以被分解为如下所述的子问题:对每一 个与起始节点直接相连的节点,求解它到终点的所有路径(路径上不包括起始节点)得到一个路径集合,将这些路径集合相加就可以得到起始节点到终点的所有路径;依次类推就可以应用递归的思想,层层递归直到终点,若发现希望得到的一条路径,则转储并打印输出;若发现环路,或发现死路,则停止寻路并返回;
3. 用栈保存当前已经寻到的路径(不是完整路径)上的节点,在每一次寻到完整路径时弹出栈顶节点;而在遇到从栈顶节点无法继续向下寻路时也弹出该栈顶节点,从而实现回溯。
实现代码
1.node.java
import java.util.arraylist; /* 表示一个节点以及和这个节点相连的所有节点 */ public class node { public string name = null; public arraylist<node> relationnodes = new arraylist<node>(); public string getname() { return name; } public void setname(string name) { this.name = name; } public arraylist<node> getrelationnodes() { return relationnodes; } public void setrelationnodes(arraylist<node> relationnodes) { this.relationnodes = relationnodes; } }
2.test.java
import java.util.arraylist; import java.util.iterator; import java.util.stack; public class test { /* 临时保存路径节点的栈 */ public static stack<node> stack = new stack<node>(); /* 存储路径的集合 */ public static arraylist<object[]> sers = new arraylist<object[]>(); /* 判断节点是否在栈中 */ public static boolean isnodeinstack(node node) { iterator<node> it = stack.iterator(); while (it.hasnext()) { node node1 = (node) it.next(); if (node == node1) return true; } return false; } /* 此时栈中的节点组成一条所求路径,转储并打印输出 */ public static void showandsavepath() { object[] o = stack.toarray(); for (int i = 0; i < o.length; i++) { node nnode = (node) o[i]; if(i < (o.length - 1)) system.out.print(nnode.getname() + "->"); else system.out.print(nnode.getname()); } sers.add(o); /* 转储 */ system.out.println("\n"); } /* * 寻找路径的方法 * cnode: 当前的起始节点currentnode * pnode: 当前起始节点的上一节点previousnode * snode: 最初的起始节点startnode * enode: 终点endnode */ public static boolean getpaths(node cnode, node pnode, node snode, node enode) { node nnode = null; /* 如果符合条件判断说明出现环路,不能再顺着该路径继续寻路,返回false */ if (cnode != null && pnode != null && cnode == pnode) return false; if (cnode != null) { int i = 0; /* 起始节点入栈 */ stack.push(cnode); /* 如果该起始节点就是终点,说明找到一条路径 */ if (cnode == enode) { /* 转储并打印输出该路径,返回true */ showandsavepath(); return true; } /* 如果不是,继续寻路 */ else { /* * 从与当前起始节点cnode有连接关系的节点集中按顺序遍历得到一个节点 * 作为下一次递归寻路时的起始节点 */ nnode = cnode.getrelationnodes().get(i); while (nnode != null) { /* * 如果nnode是最初的起始节点或者nnode就是cnode的上一节点或者nnode已经在栈中 , * 说明产生环路 ,应重新在与当前起始节点有连接关系的节点集中寻找nnode */ if (pnode != null && (nnode == snode || nnode == pnode || isnodeinstack(nnode))) { i++; if (i >= cnode.getrelationnodes().size()) nnode = null; else nnode = cnode.getrelationnodes().get(i); continue; } /* 以nnode为新的起始节点,当前起始节点cnode为上一节点,递归调用寻路方法 */ if (getpaths(nnode, cnode, snode, enode))/* 递归调用 */ { /* 如果找到一条路径,则弹出栈顶节点 */ stack.pop(); } /* 继续在与cnode有连接关系的节点集中测试nnode */ i++; if (i >= cnode.getrelationnodes().size()) nnode = null; else nnode = cnode.getrelationnodes().get(i); } /* * 当遍历完所有与cnode有连接关系的节点后, * 说明在以cnode为起始节点到终点的路径已经全部找到 */ stack.pop(); return false; } } else return false; } public static void main(string[] args) { /* 定义节点关系 */ int noderalation[][] = { {1}, //0 {0,5,2,3},//1 {1,4}, //2 {1,4}, //3 {2,3,5}, //4 {1,4} //5 }; /* 定义节点数组 */ node[] node = new node[noderalation.length]; for(int i=0;i<noderalation.length;i++) { node[i] = new node(); node[i].setname("node" + i); } /* 定义与节点相关联的节点集合 */ for(int i=0;i<noderalation.length;i++) { arraylist<node> list = new arraylist<node>(); for(int j=0;j<noderalation[i].length;j++) { list.add(node[noderalation[i][j]]); } node[i].setrelationnodes(list); list = null; //释放内存 } /* 开始搜索所有路径 */ getpaths(node[0], null, node[0], node[4]); } }
输出:
node0->node1->node5->node4
node0->node1->node2->node4
node0->node1->node3->node4
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。