本文实例为大家分享了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);
}
}
|
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持快网idc。
原文链接：https://blog.csdn.net/Coder_py/article/details/72542898
相关文章
猜你喜欢
- 个人服务器网站搭建：如何选择合适的服务器提供商？ 2025-06-10
- ASP.NET自助建站系统中如何实现多语言支持？ 2025-06-10
- 64M VPS建站：如何选择最适合的网站建设平台？ 2025-06-10
- ASP.NET本地开发时常见的配置错误及解决方法？ 2025-06-10
- ASP.NET自助建站系统的数据库备份与恢复操作指南 2025-06-10
