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);} }

總結

以上是生活随笔為你收集整理的《漫画算法2》源码整理-2 图算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。