深度优先遍历，广度优先遍历，寻求最短路径
本例使用邻接矩阵
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