假設(shè)圖中有四個頂點，分別為A,B,C,D。圖中的路徑有一下幾條：

A->B, A->C, C->B, C->D, D->B

我們采用鄰接矩陣方式存儲路徑信息。如下所示

image

假設(shè)我們要找從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}
    };
    // 頂點個數(shù)
    static int G_length = 4;
    // visit數(shù)組，用于在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);
    }
}

輸出結(jié)果為：

image