大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
java中怎么计算图两点之间的所有路径?针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。
兴安网站制作公司哪家好,找创新互联!从网页设计、网站建设、微信开发、APP开发、响应式网站开发等网站项目制作,到程序开发,运营维护。创新互联成立于2013年到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选创新互联。
1.给定图如下:
2.求0到3之间可达的所有路径
这里问题就是关于搜索遍历的问题,但其中需要注意到不能产生回路或环.
算法描述如下:
top_node:当前栈顶元素
adjvex_node;当前top_node已经访问的邻接点
next_node:即将访问的元素(top_node的第adjvex_node个邻接点所对应的元素)
找出所有路径采用的是遍历的方法,以“深度优先”算法为基础。从源点出发,先到源点的第一个邻接点N00,再到N00的第一个邻接点N10,再到N10的第一个邻接点N20...当遍历到目标点时表明找到一条路径。
上述代码的核心数据结构为一个栈,主要步骤:
①源点先入栈,并进行标记
②获取栈顶元素top_node,如果栈顶为终点时,即找到一条路径,栈顶元素top_node出栈,此时adjvex_node=top_node,新的栈顶元素为top_node,否则执行③
③从top_node的所有邻接点中,从adjvex_node为起点,选取下一个邻接点next_node;如果该元素非空,则入栈,使得adjvex_node=-1,(adjvex_node=-1代表top_node的邻接点一个还没有访问)做入栈标记。否则代表没有后续节点了,此时必须出栈栈顶元素,并置adjvex_node为该栈顶元素,并做出栈标记。
④为避免回路,已入栈元素要记录,选取新入栈顶点时应跳过已入栈的顶点,当栈为空时,遍历完成
3.java代码实现
1)图结构
点表
public class Vertex { //存放点信息 public int data; //与该点邻接的第一个边节点 public Edge firstEdge; }
边表(代表与点相连的点的集合)
//边节点 public class Edge { //对应的点下表 public int vertexId; //边的权重 public int weight; //下一个边节点 public Edge next; //getter and setter自行补充 }
2).算法实现
import java.util.HashMap; import java.util.Map; import java.util.Stack; public class graph { public Vertex[] vertexList; //存放点的集合 public graph(int vertexNum){ this.vertexNum=vertexNum; vertexList=new Vertex[vertexNum]; } //点个数 public int vertexNum; //边个数 public int edgeLength; public void initVertext(int datas[]){ for(int i=0;istates=new HashMap(); //存放放入stack中的节点 public Stack stack=new Stack(); //输出2个节点之间的输出路径 public void visit(int x,int y){ //初始化所有节点在stack中的情况 for(int i=0;i "); } sb.delete(sb.length()-2,sb.length()); System.out.println(sb.toString()); } public static void main(String[]args){ graph g=new graph(5); g.initVertext(new int[]{1,2,3,4,4}); //System.out.println(g.vertexList[0]); g.addEdge(0,1,1); g.addEdge(0,2,3); g.addEdge(0,3,4); g.addEdge(1,2,1); g.addEdge(2,0,1); g.addEdge(2,3,1); g.addEdge(1,3,2); g.visit(0,3); } }
执行结果如下:
0->3
0->2->3
0->1->2->3
关于java中怎么计算图两点之间的所有路径问题的解答就分享到这里了,希望以上内容可以对大家有一定的帮助,如果你还有很多疑惑没有解开,可以关注创新互联行业资讯频道了解更多相关知识。