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

本文实例为大家分享了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);

}

}

来源：https://blog.csdn.net/Coder_py/article/details/72542898