当前位置:主页 > java教程 >

java查找图中两点之间所有路径

发布:2022-10-08 14:25:17 93


为找教程的网友们整理了java相关的编程文章,网友盖成益根据主题投稿了本篇教程内容,涉及到java查找图中所有路径、java查找两点间所有路径、java查找两点之间所有路径相关内容,已被845网友关注,内容中涉及的知识点可以在下方直接下载获取。

本文实例为大家分享了java查找图中两点之间所有路径的具体代码,基于邻接表,供大家参考,具体内容如下

图类:

package graph1;
 
import java.util.LinkedList;
 
import graph.Graph.edgeNode;
 
public class Graph {
 
 class EdgeNode{
  int adjvex;
  EdgeNode nextEdge;
 }
 
 class VexNode{
 int data;
 EdgeNode firstEdge;
 boolean isVisted;
 public boolean isVisted() {
  return isVisted;
 }
 public void setVisted(boolean isVisted) {
  this.isVisted = isVisted;
 }
 
 }
 
 VexNode[] vexsarray ;
 int[] visited = new int[100];
 boolean[] isVisited = new boolean[100];
 
 public void linkLast(EdgeNode target,EdgeNode node) {
 while (target.nextEdge!=null) {
  target=target.nextEdge;
 }
 target.nextEdge=node;
 }
 
 public int getPosition(int data) {
  for(int i=0;i<vexsarray.length;i++) {
  if (data==vexsarray[i].data) {
   return i;
  }
  }
  return -1;
 }
 
 
 public void buildGraph(int[] vexs,int[][] edges ) {
 int vLen = vexs.length;
 int eLen = edges.length;
 vexsarray = new VexNode[vLen];
 
 for(int i=0;i<vLen;i++) {
  vexsarray[i] = new VexNode();
  vexsarray[i].data = vexs[i];
  vexsarray[i].firstEdge = null;
 }
 
 for(int i=0;i<eLen;i++) {
  
  int a = edges[i][0];
  int b = edges[i][1];
  
  int start = getPosition(a);
  int end = getPosition(b);
  
  EdgeNode edgeNode = new EdgeNode();
  edgeNode.adjvex = end;
  
  if (vexsarray[start].firstEdge == null) {
  vexsarray[start].firstEdge = edgeNode;
  } else {
  linkLast(vexsarray[start].firstEdge,edgeNode);
  }
 }
 }
 
 
 public void printGraph() {
 for(int i=0;i<vexsarray.length;i++) {
  System.out.printf("%d--",vexsarray[i].data);
  EdgeNode node = vexsarray[i].firstEdge;
  while (node!=null) {
  System.out.printf("%d(%d)--",node.adjvex,vexsarray[node.adjvex].data);
  node = node.nextEdge;
  }
  System.out.println("\n");
 }
 }

算法:

package graph1;
 
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
 
import javax.swing.plaf.synth.SynthStyle;
 
import graph1.Graph.EdgeNode;
 
public class FindALlPath {
 
 
 //代表某节点是否在stack中,避免产生回路 
 public Map<Integer,Boolean> states=new HashMap(); 
  
 //存放放入stack中的节点 
 public Stack<Integer> stack=new Stack(); 
 
 //打印stack中信息,即路径信息 
 public void printPath(){ 
   StringBuilder sb=new StringBuilder(); 
   for(Integer i :stack){ 
     sb.append(i+"->"); 
   } 
   sb.delete(sb.length()-2,sb.length()); 
   System.out.println(sb.toString()); 
 } 
 
 //得到x的邻接点为y的后一个邻接点位置,为-1说明没有找到 
 public int getNextNode(Graph graph,int x,int y){ 
   int next_node=-1; 
   EdgeNode edge=graph.vexsarray[x].firstEdge; 
   if(null!=edge&&y==-1){ 
     int n=edge.adjvex; 
     //元素还不在stack中 
     if(!states.get(n)) 
       return n; 
     return -1; 
   } 
      
   while(null!=edge){ 
     //节点未访问 
     if(edge.adjvex==y){ 
       if(null!=edge.nextEdge){ 
       next_node=edge.nextEdge.adjvex; 
       
       if(!states.get(next_node)) 
         return next_node; 
       } 
       else 
         return -1; 
     } 
     edge=edge.nextEdge; 
   } 
   return -1; 
 }
 
 
 
 public void visit(Graph graph,int x,int y){ 
    //初始化所有节点在stack中的情况 
     for(int i=0;i<graph.vexsarray.length;i++){ 
     states.put(i,false); 
   } 
     //stack top元素 
     int top_node; 
   //存放当前top元素已经访问过的邻接点,若不存在则置-1,此时代表访问该top元素的第一个邻接点 
     int adjvex_node=-1; 
   int next_node; 
   stack.add(x); 
   states.put(x,true); 
   
   while(!stack.isEmpty()){ 
     top_node=stack.peek(); 
     //找到需要访问的节点 
        if(top_node==y){ 
       //打印该路径 
       printPath(); 
       adjvex_node=stack.pop(); 
       states.put(adjvex_node,false); 
     } 
     else{ 
       //访问top_node的第advex_node个邻接点 
             next_node=getNextNode(graph,top_node,adjvex_node); 
       if(next_node!=-1){ 
         stack.push(next_node); 
         //置当前节点访问状态为已在stack中 
                 states.put(next_node,true); 
         //临接点重置 
                 adjvex_node=-1; 
       } 
            //不存在临接点,将stack top元素退出  
             else{ 
         //当前已经访问过了top_node的第adjvex_node邻接点 
                 adjvex_node=stack.pop(); 
         //不在stack中 
         states.put(adjvex_node,false); 
       } 
     } 
   } 
 } 
 
 
}

测试类:

package graph1;
 
import java.util.Iterator;
 
import graph1.Graph.VexNode;
 
public class Tset2 {
 
 public static void main(String[] args) {
 
 int[] vexs = {0,1,2,3,4};
 int[][] edges = {
  {0,1},
  {0,3},
  {1,0},
  {1,2},
  {2,1},
  {2,3},
  {2,4},
  {3,0},
  {3,2},
  {3,4},
  {4,2},
  {4,3},
  
 };
 Graph graph = new Graph();
 graph.buildGraph(vexs, edges);
 graph.printGraph();
 
 
 FindALlPath findALlPath = new FindALlPath();
 findALlPath.visit(graph, 4, 0);
 
 }
 
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持码农之家。


相关文章

  • java实现highcharts导出图片至excel实例方法

    发布:2019-09-05

    这篇文章主要介绍了如何通过java实现highcharts导出图片至excel。文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,下面我们就来一起学习一下吧


  • Java String字符串和Unicode字符相互转换实例代码

    发布:2019-12-24

    这篇文章主要介绍了Java String字符串和Unicode字符相互转换代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习


  • Java文件和base64流相互转换功能实现方法

    发布:2019-06-07

    这篇文章主要介绍了Java实现文件和base64流的相互转换功能,涉及Java文件读取及base64 转换相关操作技巧,需要的朋友可以参考下


  • java加解密RSA使用的实例方法

    发布:2020-01-13

    这篇文章主要介绍了java加解密RSA使用方法代码示例,还是比较不错的,这里分享给大家,供需要的朋友参考。


  • Java实现随机10道10以内加减法的代码详解

    发布:2019-11-16

    这篇文章主要介绍了Java实现随机出题,10道10以内加减法计算,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习


  • 用java实现简单的学生信息管理系统方案实例

    发布:2020-02-10

    这篇文章主要介绍了java实现简单的学生信息管理系统,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧


  • java异常与处理机制分析

    发布:2019-08-11

    这篇文章主要介绍了java的异常与处理机制,结合实例形式分析了Java异常与处理机制的概念、原理、相关操作技巧与注意事项,并附带面试题分析供大家参考,需要的朋友可以参考下


  • java自定义和自然排序知识点总结

    发布:2020-01-21

    这篇文章主要介绍了简单了解java自定义和自然排序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下


  • Java selenium处理极验滑动验证码示例

    Java selenium处理极验滑动验证码示例

    发布:2022-09-07

    为网友们分享了关于selenium的教程,本篇文章主要介绍了Java selenium处理极验滑动验证码示例,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧


  • 浅谈JAVA Future类

    发布:2020-01-21

    Future是并发编程中的一种设计模式,Future它代表一个异步计算的结果,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,下面小编和大家来一起学习一下吧


网友讨论