当前位置：首页 > article >正文

java-图算法

article 2024/11/24 0:06:59

1. 最短路径算法

迪杰斯特拉算法（Dijkstra’s Algorithm）

描述：
迪杰斯特拉算法是一种用于在加权图中找到单个源点到所有其他顶点的最短路径的算法。它适用于有向图和无向图，且边的权重必须为非负数。

Java案例：

import java.util.Arrays;

public class DijkstraAlgorithm {
    public static void dijkstra(int[][] graph, int src) {
        int V = graph.length;
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        boolean[] sptSet = new boolean[V];

        dist[src] = 0;

        for (int count = 0; count < V - 1; count++) {
            int u = minDistance(dist, sptSet, V);
            sptSet[u] = true;

            for (int v = 0; v < V; v++)
                if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
        }

        printSolution(dist);
    }

    private static int minDistance(int[] dist, boolean[] sptSet, int V) {
        int min = Integer.MAX_VALUE, minIndex = -1;

        for (int v = 0; v < V; v++)
            if (!sptSet[v] && dist[v] <= min)
                min = dist[v], minIndex = v;

        return minIndex;
    }

    private static void printSolution(int[] dist) {
        System.out.println("Vertex \t Distance from Source");
        for (int i = 0; i < dist.length; i++)
            System.out.println(i + " \t\t " + dist[i]);
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 4, 0, 0, 0, 0, 0, 8, 0},
            {4, 0, 8, 0, 0, 0, 0, 11, 0},
            {0, 8, 0, 7, 0, 4, 0, 0, 2},
            {0, 0, 7, 0, 9, 14, 0, 0, 0},
            {0, 0, 0, 9, 0, 10, 0, 0, 0},
            {0, 0, 4, 14, 10, 0, 2, 0, 0},
            {0, 0, 0, 0, 0, 2, 0, 1, 6},
            {8, 11, 0, 0, 0, 0, 1, 0, 7},
            {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };
        dijkstra(graph, 0);
    }
}

弗洛伊德算法（Floyd-Warshall Algorithm）

描述：
弗洛伊德算法用于在加权图中找到所有顶点对之间的最短路径。它可以处理正权边和负权边，但不能处理负权环。

Java案例：

public class FloydWarshallAlgorithm {
    public static void floydWarshallAlgorithm(int[][] graph) {
        int V = graph.length;
        int[][] dist = new int[V][V];
        boolean[][] isShortestPath = new boolean[V][V];

        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                dist[i][j] = graph[i][j];

        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE
                            && dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        isShortestPath[i][j] = false;
                    } else if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE
                            && dist[i][j] == dist[i][k] + dist[k][j]) {
                        isShortestPath[i][j] = true;
                    }
                }
            }
        }

        printSolution(dist);
    }

    private static void printSolution(int[][] dist) {
        System.out.println("The following matrix shows the shortest distances between every pair of vertices:");
        for (int i = 0; i < dist.length; i++) {
            for (int j = 0; j < dist[i].length; j++) {
                if (dist[i][j] == Integer.MAX_VALUE)
                    System.out.print("\u221e ");
                else
                    System.out.print(dist[i][j] + "   ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 5, 0, 0, 0, 0, 0, 8, 0},
            {5, 0, 10, 0, 0, 0, 0, 3, 0},
            {0, 10, 0, 15, 0, 0, 0, 0, 2},
            {0, 0, 15, 0, 6, 0, 0, 0, 0},
            {0, 0, 0, 6, 0, 9, 0, 0, 0},
            {0, 0, 0, 0, 9, 0, 7, 0, 0},
            {0, 0, 0, 0, 0, 7, 0, 4, 0},
            {8, 3, 0, 0, 0, 0, 4, 0, 2},
            {0, 0, 2, 0, 0, 0, 0, 2, 0}
        };
        floydWarshallAlgorithm(graph);
    }
}

2. 最小生成树算法

普里姆算法（Prim’s Algorithm）

描述：
普里姆算法是一种贪心算法，用于在加权连通图中找到最小生成树。它从一个任意顶点开始，逐渐增加树中的顶点，直到包含所有顶点。

Java案例：

import java.util.Arrays;

public class PrimsAlgorithm {
    public static void primsAlgorithm(int[][] graph) {
        int V = graph.length;
        int[] parent = new int[V];
        int[] minHeap = new int[V];
        Arrays.fill(minHeap, Integer.MAX_VALUE);
        boolean[] added = new boolean[V];

        minHeap[0] = 0;
        parent[0] = -1;

        for (int i = 0; i < V - 1; i++) {
            int u = minHeap[0];
            added[u] = true;

            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && !added[v] && graph[u][v] < minHeap[v]) {
                    minHeap[v] = graph[u][v];
                    parent[v] = u;
                }
            }

            for (int v = 0; v < V; v++) {
                if (!added[v] && minHeap[v] < minHeap[0]) {
                    minHeap[0] = minHeap[v];
                }
            }
        }

        printMST(parent);
    }

    private static void printMST(int[] parent) {
        System.out.println("Edge \t Weight");
        for (int i = 1; i < parent.length; i++)
            System.out.println(parent[i] + " - " + i + "\t" + 1);
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 2, 0, 6, 0},
            {2, 0, 3, 8, 5},
            {0, 3, 0, 0, 7},
            {6, 8, 0, 0, 9},
            {0, 5, 7, 9, 0}
        };
        primsAlgorithm(graph);
    }
}