网站建设资讯

NEWS

网站建设资讯

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

小编给大家分享一下java如何查找图中两点之间所有路径,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

创新互联基于分布式IDC数据中心构建的平台为众多户提供成都服务器托管 四川大带宽租用 成都机柜租用 成都服务器租用。

图类:

package graph2;
 
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

算法:

package graph2;
 
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
 
import javax.swing.plaf.synth.SynthStyle;
 
import graph2.Graph.EdgeNode;
 
public class FindALlPath {
 
 
 //代表某节点是否在stack中,避免产生回路 
 public Map states=new HashMap(); 
  
 //存放放入stack中的节点 
 public Stack 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

测试类:

package graph2;
 
import java.util.Iterator;
 
import graph2.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如何查找图中两点之间所有路径”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!


网站名称:java如何查找图中两点之间所有路径
URL分享:http://njwzjz.com/article/ijsihg.html