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

时间:2022-11-28 11:37:12

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

图类:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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");
 }
 }

算法:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
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);
       }
     }
   }
 }
 
 
}

测试类:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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