GraphUtil
import java.util.LinkedList; public class GraphUtil { //深度优先遍历 public static void dfs(Graph graph, int start, boolean[] visited) { System.out.println(graph.vertexes[start].data); visited[start] = true; for (int index : graph.adj[start]) { if (!visited[index]) { dfs(graph, index, visited); } } } //广度优先遍历 public static void bfs(Graph graph, int start, boolean[] visited, LinkedList<Integer> queue) { queue.offer(start); while (!queue.isEmpty()) { int front = queue.poll(); if (visited[front]) { continue; } System.out.println(graph.vertexes[front].data); visited[front] = true; for (int index : graph.adj[front]) { queue.offer(index);; } } } //图的顶点 private static class Vertex { int data; Vertex(int data) { this.data = data; } } //图(邻接表形式) private static class Graph { private int size; private Vertex[] vertexes; private LinkedList<Integer>[] adj; Graph(int size) { this.size = size; //初始化顶点和邻接矩阵 vertexes = new Vertex[size]; adj = new LinkedList[size]; for (int i = 0; i < size; i++) { vertexes[i] = new Vertex(i); adj[i] = new LinkedList(); } } } public static void main(String[] args) { Graph graph = new Graph(6); graph.adj[0].add(1); graph.adj[0].add(2); graph.adj[0].add(3); graph.adj[1].add(0); graph.adj[1].add(3); graph.adj[1].add(4); graph.adj[2].add(0); graph.adj[3].add(0); graph.adj[3].add(1); graph.adj[3].add(4); graph.adj[3].add(5); graph.adj[4].add(1); graph.adj[4].add(3); graph.adj[4].add(5); graph.adj[5].add(3); graph.adj[5].add(4); System.out.println("图的深度优先遍历:"); dfs(graph, 0, new boolean[graph.size]); System.out.println("图的广度优先遍历:"); bfs(graph, 0, new boolean[graph.size], new LinkedList<Integer>()); } }
单源最短路径算法 Dijkstra 算法
import java.util.*; public class Dijkstra { // Dijkstra最短路径算法 public static int[] dijkstra(Graph graph, int startIndex) { //图的顶点数量 int size = graph.vertexes.length; //创建距离表,存储从起点到每一个顶点的临时距离 int[] distances = new int[size]; //记录顶点遍历状态 boolean[] access = new boolean[size]; //初始化最短路径表,到达每个顶点的路径代价默认为无穷大 for (int i = 1; i < size; i++) { distances[i] = Integer.MAX_VALUE; } //遍历起点,刷新距离表 access[0] = true; List<Edge> edgesFromStart = graph.adj[startIndex]; for (Edge edge : edgesFromStart) { distances[edge.index] = edge.weight; } //主循环,重复遍历最短距离顶点和刷新距离表的操作 for (int i = 1; i < size; i++) { //寻找最短距离顶点 int minDistanceFromStart = Integer.MAX_VALUE; int minDistanceIndex = -1; for (int j = 1; j < size; j++) { if (!access[j] && (distances[j] < minDistanceFromStart)) { minDistanceFromStart = distances[j]; minDistanceIndex = j; } } if (minDistanceIndex == -1) { break; } //遍历顶点,刷新距离表 access[minDistanceIndex] = true; for (Edge edge : graph.adj[minDistanceIndex]) { if (access[edge.index]) { continue; } int weight = edge.weight; int preDistance = distances[edge.index]; if ((weight != Integer.MAX_VALUE) && ((minDistanceFromStart + weight) < preDistance)) { distances[edge.index] = minDistanceFromStart + weight; } } } return distances; } // Dijkstra最短路径算法(返回完整路径) public static int[] dijkstraV2(Graph graph, int startIndex) { //图的顶点数量 int size = graph.vertexes.length; //创建距离表,存储从起点到每一个顶点的临时距离 int[] distances = new int[size]; //创建前置定点表,存储从起点到每一个顶点的已知最短路径的前置节点 int[] prevs = new int[size]; //记录顶点遍历状态 boolean[] access = new boolean[size]; //初始化最短路径表,到达每个顶点的路径代价默认为无穷大 for (int i = 0; i < size; i++) { distances[i] = Integer.MAX_VALUE; } //遍历起点,刷新距离表 access[0] = true; List<Edge> edgesFromStart = graph.adj[startIndex]; for (Edge edge : edgesFromStart) { distances[edge.index] = edge.weight; prevs[edge.index] = 0; } //主循环,重复 遍历最短距离顶点和刷新距离表 的操作 for (int i = 1; i < size; i++) { //寻找最短距离顶点 int minDistanceFromStart = Integer.MAX_VALUE; int minDistanceIndex = -1; for (int j = 1; j < size; j++) { if (!access[j] && (distances[j] < minDistanceFromStart)) { minDistanceFromStart = distances[j]; minDistanceIndex = j; } } if (minDistanceIndex == -1) { break; } //遍历顶点,刷新距离表 access[minDistanceIndex] = true; for (Edge edge : graph.adj[minDistanceIndex]) { if (access[edge.index]) { continue; } int weight = edge.weight; int preDistance = distances[edge.index]; if ((weight != Integer.MAX_VALUE) && ((minDistanceFromStart + weight) < preDistance)) { distances[edge.index] = minDistanceFromStart + weight; prevs[edge.index] = minDistanceIndex; } } } return prevs; } private static void printPrevs(Vertex[] vertexes, int[] prev, int i) { if (i > 0) { printPrevs(vertexes, prev, prev[i]); } System.out.println(vertexes[i].data); } private static void initGraph(Graph graph) { graph.vertexes[0] = new Vertex("A"); graph.vertexes[1] = new Vertex("B"); graph.vertexes[2] = new Vertex("C"); graph.vertexes[3] = new Vertex("D"); graph.vertexes[4] = new Vertex("E"); graph.vertexes[5] = new Vertex("F"); graph.vertexes[6] = new Vertex("G"); graph.adj[0].add(new Edge(1, 5)); graph.adj[0].add(new Edge(2, 2)); graph.adj[1].add(new Edge(0, 5)); graph.adj[1].add(new Edge(3, 1)); graph.adj[1].add(new Edge(4, 6)); graph.adj[2].add(new Edge(0, 2)); graph.adj[2].add(new Edge(3, 6)); graph.adj[2].add(new Edge(5, 8)); graph.adj[3].add(new Edge(1, 1)); graph.adj[3].add(new Edge(2, 6)); graph.adj[3].add(new Edge(4, 1)); graph.adj[3].add(new Edge(5, 2)); graph.adj[4].add(new Edge(1, 6)); graph.adj[4].add(new Edge(3, 1)); graph.adj[4].add(new Edge(6, 7)); graph.adj[5].add(new Edge(2, 8)); graph.adj[5].add(new Edge(3, 2)); graph.adj[5].add(new Edge(6, 3)); graph.adj[6].add(new Edge(4, 7)); graph.adj[6].add(new Edge(5, 3)); } //图的顶点 private static class Vertex { String data; Vertex(String data) { this.data = data; } } //图的边 private static class Edge { int index; int weight; Edge(int index, int weight) { this.index = index; this.weight = weight; } } // 图 private static class Graph { private Vertex[] vertexes; private LinkedList<Edge>[] adj; Graph(int size) { //初始化顶点和邻接矩阵 vertexes = new Vertex[size]; adj = new LinkedList[size]; for (int i = 0; i < adj.length; i++) { adj[i] = new LinkedList<Edge>(); } } } public static void main(String[] args) { Graph graph = new Graph(7); initGraph(graph); int[] distances = dijkstra(graph, 0); System.out.println(distances[6]); System.out.println("输出完整路径:"); int[] prevs = dijkstraV2(graph, 0); printPrevs(graph.vertexes, prevs, graph.vertexes.length- 1); } }
多源最短路径算法 Floyd 算法
public class Floyd { final static int INF = Integer.MAX_VALUE; public static void floyd(int[][] matrix) { //循环更新矩阵的值 for (int k = 0; k < matrix.length; k++) { for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix.length; j++) { if ((matrix[i][k] == INF) || (matrix[k][j] == INF)) { continue; } matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k][j]); } } } // 打印floyd最短路径的结果 System.out.printf("最短路径矩阵: \n"); for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix.length; j++) { System.out.printf("%3d ", matrix[i][j]); } System.out.printf("\n"); } } public static void main(String[] args) { int[][] matrix = { { 0, 5, 2, INF, INF, INF, INF }, { 5, 0, INF, 1, 6, INF, INF }, { 2, INF, 0, 6, INF, 8, INF }, { INF, 1, 6, 0, 1, 2, INF }, { INF, 6, INF, 1, 0, INF, 7 }, { INF, INF, 8, 2, INF, 0, 3 }, { INF, INF, INF, INF, 7, 3, 0 } }; floyd(matrix); } }