假设图中有四个顶点，分别为A,B,C,D。图中的路径有一下几条：
A->B, A->C, C->B, C->D, D->B
我们采用邻接矩阵方式存储路径信息。如下所示
图的邻接矩阵
假设我们要找从A到B的所有路径，采用DFS算法：
import java.util.ArrayList;
import java.util.List;
public class AllRoads {
// 定义一个图
static int[][] Graph = {
{0,1,1,0},
{0,0,0,0},
{0,1,0,1},
{0,1,0,0}
};
// 顶点个数
static int G_length = 4;
// visit数组，用于在dfs中记录访问过的顶点信息。
static int[] visit = new int[G_length];
//存储每条可能的路径
static ArrayList<Character> path = new ArrayList<>();
// 用于存储所有路径的集合
static ArrayList<String> ans = new ArrayList<>();
//起点和终点
static int start;
static int end;
static void dfs(int u){
visit[u] = 1;
path.add((char)((int)'A'+u));
if(u == end){
ans.add(path.toString());
}else{
for (int i = 0; i < G_length; i++) {
if(visit[i]==0&&i!=u&&Graph[u][i]==1){
dfs(i);
}
}
}
path.remove(path.size()-1);
visit[u] = 0;
}
public static void main(String[] args) {
start = 0;
end = 1;
dfs(start);
System.out.println(ans);
}
}
输出结果为：
image.png
