深度優(yōu)先：是否存在通路，尋找所有解。

廣度優(yōu)先遍歷：尋求最優(yōu)解，尋求最短路徑

鄰接矩陣可以使用一個(gè)二維數(shù)組來(lái)表示

public class GraphTest {

  // 節(jié)點(diǎn)
  public static class Vertex {
    public String name;
    private boolean isVisited;

    public Vertex(String name) {
      this.name = name;
      this.isVisited = false;
    }

    public void displayName() {
      System.out.println("name:" + name);
    }
  }

  // 圖
  public static class Graph {
    // 存節(jié)點(diǎn)數(shù)據(jù)
    private Vertex[] vertices;
    // 矩陣
    private int[][] matrix;
    // 隊(duì)列，用于BFS
    private Queue queue = new LinkedList<>();
    // 棧，用于DFS
    private Stack stack = new Stack<>();

    private Map dependencyMap = new HashMap<>();

    public Graph(Vertex[] vertices, int[][] matrix) {
      this.vertices = vertices;
      this.matrix = matrix;
    }

    // 找到未訪問(wèn)過(guò)的鄰接點(diǎn)
    public List getUnvisitedVertex(int i) {
      List unvisitedVertices = new ArrayList<>();
      for (int j = 0; j < matrix.length; j++) {
        if (matrix[i][j] > 0 && !vertices[j].isVisited) {
          unvisitedVertices.add(j);
        }
      }
      return unvisitedVertices;
    }

    // 廣度優(yōu)先
    public void bfs(int vertex) {
      queue.offer(vertex);

      while (!queue.isEmpty()) {
        int v = queue.poll();
        if (!vertices[v].isVisited) {
          vertices[v].displayName();
          vertices[v].isVisited = true;

          List unvisitedVertices = getUnvisitedVertex(v);
          unvisitedVertices.forEach(uv -> {
            queue.offer(uv);
            dependencyMap.putIfAbsent(uv, v);
          });
        }
      }
    }

    // 深度優(yōu)先
    public void dfs(int vertex) {
      stack.push(vertex);

      while (!stack.isEmpty()) {
        int v = stack.pop();
        if (!vertices[v].isVisited) {
          vertices[v].displayName();
          vertices[v].isVisited = true;

          List unvisitedVertices = getUnvisitedVertex(v);
          unvisitedVertices.forEach(uv -> stack.push(uv));
        }
      }
    }

    // 深度優(yōu)先遞歸實(shí)現(xiàn)
    public void dfsRecursion(int vertex) {
      if (!vertices[vertex].isVisited) {
        vertices[vertex].displayName();
        vertices[vertex].isVisited = true;

        List unvisitedVertices = getUnvisitedVertex(vertex);
        unvisitedVertices.forEach(this::dfsRecursion);
      }
    }

    public void printShortestPath(int start, int end) {
      bfs(start);

      String symbol = "-->";
      StringBuilder sb = new StringBuilder();
      sb.append(vertices[end].name);
      sb.append(symbol);
      while (dependencyMap.get(end) != null) {
        sb.append(vertices[dependencyMap.get(end)].name);
        sb.append(symbol);
        end = dependencyMap.get(end);
      }
      String path = sb.substring(0, sb.lastIndexOf(symbol));
      System.out.println(path);
    }

    public void clear() {
      stack.clear();
      queue.clear();
      dependencyMap.clear();
      for (int i = 0; i < vertices.length; i++) {
        vertices[i].isVisited = false;
      }
    }

  }

  public static void main(String[] args) {
    Vertex[] vertices = {
            new Vertex("v0"),
            new Vertex("v1"),
            new Vertex("v2"),
            new Vertex("v3"),
            new Vertex("v4")
    };

    int[][] matrix = new int[][]{
            {0, 0, 1, 1, 0},
            {0, 0, 1, 0, 1},
            {1, 1, 0, 0, 1},
            {1, 0, 0, 0, 1},
            {0, 1, 1, 1, 0}
    };

    Graph graph = new Graph(vertices, matrix);

    System.out.println("廣度優(yōu)先搜索：");
    graph.bfs(0);
    graph.clear();

    System.out.println("深度優(yōu)先搜索：");

    graph.dfs(0);
    graph.clear();

    System.out.println("遞歸深度優(yōu)先搜索：");

    graph.dfsRecursion(0);
    graph.clear();

    System.out.println("打印最短路徑：");

    graph.printShortestPath(0, 4);
  }
}

打印結(jié)果
廣度優(yōu)先搜索：
name:v0
name:v2
name:v3
name:v1
name:v4
深度優(yōu)先搜索：
name:v0
name:v3
name:v4
name:v2
name:v1
遞歸深度優(yōu)先搜索：
name:v0
name:v2
name:v1
name:v4
name:v3
打印最短路徑：
name:v0
name:v2
name:v3
name:v1
name:v4
v4-->v2-->v0

鄰接表可以使用數(shù)組+鏈表，鏈表+鏈表，哈希表等等數(shù)據(jù)結(jié)構(gòu)來(lái)表示。在java中，map結(jié)構(gòu)非常適合表示鄰接表

public class GraphTest {
  public static void main(String[] args){
    //初始化先建立起各個(gè)節(jié)點(diǎn)信息，以及對(duì)應(yīng)的直接子節(jié)點(diǎn)列表
    HashMap map = new HashMap<>();
    map.put("V0", new String[] {"V2","V3"});
    map.put("V1", new String[] {"V2","V4"});
    map.put("V2", new String[] {"V0","V1","V4"});
    map.put("V3", new String[] {"V0","V4"});
    map.put("V4", new String[] {"V1","V2","V3"});
    //獲取從A到H的最短路徑節(jié)點(diǎn)鏈表
    Node target = findTarget("V0","V4",map);
    //打印出最短路徑的各個(gè)節(jié)點(diǎn)信息
    printSearPath(target);

  }

  /**
   * 打印出到達(dá)節(jié)點(diǎn)target所經(jīng)過(guò)的各個(gè)節(jié)點(diǎn)信息
   * @param target
   */
  static void printSearPath(Node target) {
    if (target != null) {
      System.out.print("找到了目標(biāo)節(jié)點(diǎn):" + target.id + "
");

      List searchPath = new ArrayList();
      searchPath.add(target);
      Node node = target.parent;
      while(node!=null) {
        searchPath.add(node);
        node = node.parent;
      }
      String path = "";
      for(int i=searchPath.size()-1;i>=0;i--) {
        path += searchPath.get(i).id;
        if(i!=0) {
          path += "-->";
        }
      }
      System.out.print("步數(shù)最短："+path);
    } else {
      System.out.print("未找到了目標(biāo)節(jié)點(diǎn)");
    }
  }

  /**
   * 從指定的開(kāi)始節(jié)點(diǎn) startId ，查詢到目標(biāo)節(jié)點(diǎn)targetId 的最短路徑
   * @param startId
   * @param targetId
   * @param map
   * @return
   */
  static Node findTarget(String startId,String targetId,HashMap map) {
    List hasSearchList = new ArrayList();
    LinkedList queue = new LinkedList();
    queue.offer(new Node(startId,null));
    while(!queue.isEmpty()) {
      Node node = queue.poll();

      if(hasSearchList.contains(node.id)) {
        //跳過(guò)已經(jīng)搜索過(guò)的，避免重復(fù)或者死循環(huán)
        continue;
      }
      System.out.print("判斷節(jié)點(diǎn):" + node.id +"
");
      if (targetId.equals(node.id)) {
        return node;
      }
      hasSearchList.add(node.id);
      if (map.get(node.id) != null && map.get(node.id).length > 0) {
        for (String childId : map.get(node.id)) {
          queue.offer(new Node(childId,node));
        }
      }
    }

    return null;
  }

  /**
   * 節(jié)點(diǎn)對(duì)象
   * @author Administrator
   *
   */
  static class Node{
    //節(jié)點(diǎn)唯一id
    public String id;
    //該節(jié)點(diǎn)的直接父節(jié)點(diǎn)
    public Node parent;
    //該節(jié)點(diǎn)的直接子節(jié)點(diǎn)
    public List childs = new ArrayList();
    public Node(String id,Node parent) {
      this.id = id;
      this.parent = parent;
    }
  }
}

打?。?br>判斷節(jié)點(diǎn):V0
判斷節(jié)點(diǎn):V2
判斷節(jié)點(diǎn):V3
判斷節(jié)點(diǎn):V1
判斷節(jié)點(diǎn):V4
找到了目標(biāo)節(jié)點(diǎn):V4
步數(shù)最短：V0-->V2-->V4