广度优先深度优先寻求最短路径

深度优先遍历，广度优先遍历，寻求最短路径
本例使用邻接矩阵

public class GraphTest {

  // 节点
  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 {
    // 存节点数据
    private Vertex[] vertices;
    // 矩阵
    private int[][] matrix;
    // 队列，用于 BFS
    private Queue<Integer> queue = new LinkedList<>();
    // 栈，用于 DFS
    private Stack<Integer> stack = new Stack<>();

    private Map<Integer, Integer> dependencyMap = new HashMap<>();

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

    // 找到未访问过的邻接点
    public List<Integer> getUnvisitedVertex(int i) {List<Integer> unvisitedVertices = new ArrayList<>();
      for (int j = 0; j < matrix.length; j++) {if (matrix[i][j] > 0 && !vertices[j].isVisited) {unvisitedVertices.add(j);
        }
      }
      return unvisitedVertices;
    }

    // 广度优先
    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<Integer> unvisitedVertices = getUnvisitedVertex(v);
          unvisitedVertices.forEach(uv -> {queue.offer(uv);
            dependencyMap.putIfAbsent(uv, v);
          });
        }
      }
    }

    // 深度优先
    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<Integer> unvisitedVertices = getUnvisitedVertex(v);
          unvisitedVertices.forEach(uv -> stack.push(uv));
        }
      }
    }

    // 深度优先递归实现
    public void dfsRecursion(int vertex) {if (!vertices[vertex].isVisited) {vertices[vertex].displayName();
        vertices[vertex].isVisited = true;

        List<Integer> 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("广度优先搜索：");
    graph.bfs(0);
    graph.clear();

    System.out.println("深度优先搜索：");

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

    System.out.println("递归深度优先搜索：");

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

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

    graph.printShortestPath(0, 4);
  }
}

打印结果
广度优先搜索：
name:v0
name:v2
name:v3
name:v1
name:v4
深度优先搜索：
name:v0
name:v3
name:v4
name:v2
name:v1
递归深度优先搜索：
name:v0
name:v2
name:v1
name:v4
name:v3
打印最短路径：
name:v0
name:v2
name:v3
name:v1
name:v4
v4–>v2–>v0