WeightedGraph クラス

WeightedGraph クラスは AbstractGraph を拡張します。
前の章では、グラフをモデリングするための Graph インターフェイス、AbstractGraph クラス、および UnweightedGraph クラスを設計しました。このパターンに従い、下の図に示すように、WeightedGraph を AbstractGraph のサブクラスとして設計します。

WeightedGraph は、具体的な WeightedGraph インスタンスを作成するための 5 つのコンストラクターを使用して AbstractGraph を拡張するだけです。 WeightedGraph は、AbstractGraph からすべてのメソッドを継承し、clear メソッドと addVertex メソッドをオーバーライドし、新しい addEdge メソッドを実装します。重み付きエッジを追加し、最小スパニング ツリーを取得し、単一ソースの最短パスをすべて見つけるための新しい方法も導入します。最小スパニング ツリーと最短パスは、それぞれ「最小スパニング ツリーと最短パス」セクションで紹介されます。

以下のコードは WeightedGraph を実装します。エッジ隣接リスト (行 38 ～ 63) は、頂点の隣接エッジを格納するために内部的に使用されます。 WeightedGraph が構築されると、そのエッジ隣接リストが作成されます (47 行目と 57 行目)。メソッド getMinimumSpanningTree() (行 99 ～ 138) および getShortestPath() (行 156 ～ 197) は、今後のセクションで紹介されます。

package demo;
import java.util.*;

public class WeightedGraph<V> extends AbstractGraph<V> {
    /** Construct an empty */
    public WeightedGraph() {}

    /** Construct a WeightedGraph from vertices and edged in arrays */
    public WeightedGraph(V[] vertices, int[][] edges) {
        createWeightedGraph(java.util.Arrays.asList(vertices), edges);
    }

     /** Construct a WeightedGraph from vertices and edges in list */
    public WeightedGraph(int[][] edges, int numberOfVertices) {
        List<V> vertices = new ArrayList<>();
        for (int i = 0; i < numberOfVertices; i++)
            vertices.add((V)(new Integer(i)));

        createWeightedGraph(vertices, edges);
    }

    /** Construct a WeightedGraph for vertices 0, 1, 2 and edge list */
    public WeightedGraph(List<V> vertices, List<WeightedEdge> edges) {
        createWeightedGraph(vertices, edges);
    }

    /** Construct a WeightedGraph from vertices 0, 1, and edge array */
    public WeightedGraph(List<WeightedEdge> edges, int numberOfVertices) {
        List<V> vertices = new ArrayList<>();
        for (int i = 0; i < numberOfVertices; i++)
            vertices.add((V)(new Integer(i)));

        createWeightedGraph(vertices, edges);
    }

    /** Create adjacency lists from edge arrays */
    private void createWeightedGraph(List<V> vertices, int[][] edges) {
        this.vertices = vertices;

        for (int i = 0; i < vertices.size(); i++) {
            neighbors.add(new ArrayList<Edge>()); // Create a list for vertices
        }

        for (int i = 0; i < edges.length; i++) {
            neighbors.get(edges[i][0]).add(new WeightedEdge(edges[i][0], edges[i][1], edges[i][2]));
        }
    }

    /** Create adjacency lists from edge lists */
    private void createWeightedGraph(List<V> vertices, List<WeightedEdge> edges) {
        this.vertices = vertices;

        for (int i = 0; i < vertices.size(); i++) {
            neighbors.add(new ArrayList<Edge>()); // Create a list for vertices
        }

        for (WeightedEdge edge: edges) {
            neighbors.get(edge.u).add(edge); // Add an edge into the list
        }
    }

    /** Return the weight on the edge (u, v) */
    public double getWeight(int u, int v) throws Exception {
        for (Edge edge : neighbors.get(u)) {
            if (edge.v == v) {
                return ((WeightedEdge)edge).weight;
            }
        }

        throw new Exception("Edge does not exit");
    }

    /** Display edges with weights */
    public void printWeightedEdges() {
        for (int i = 0; i < getSize(); i++) {
            System.out.print(getVertex(i) + " (" + i + "): ");
            for (Edge edge : neighbors.get(i)) {
                System.out.print("(" + edge.u + ", " + edge.v + ", " + ((WeightedEdge)edge).weight + ") ");
            }

            System.out.println();
        }
    }

    /** Add edges to the weighted graph */
    public boolean addEdge(int u, int v, double weight) {
        return addEdge(new WeightedEdge(u, v, weight));
    }

    /** Get a minimum spanning tree rooted at vertex 0 */
    public MST getMinimumSpanningTree() {
        return getMinimumSpanningTree(0);
    }

    /** Get a minimum spanning tree rooted at a specified vertex */
    public MST getMinimumSpanningTree(int startingVertex) {
        // cost[v] stores the cost by adding v to the tree
        double[] cost = new double[getSize()];
        for (int i = 0; i < cost.length; i++) {
            cost[i] = Double.POSITIVE_INFINITY; // Initial cost
        }
        cost[startingVertex] = 0; // Cost of source is 0

        int[] parent = new int[getSize()]; // Parent of a vertex
        parent[startingVertex] = -1; // startingVertex is the root
        double totalWeight = 0; // Total weight of the tree thus far

        List<Integer> T = new ArrayList<>();

        // Expand T
        while (T.size() < getSize()) {
            // Find smallest cost v in V - T
            int u = -1; // Vertex to be determined
            double currentMinCost = Double.POSITIVE_INFINITY;
            for (int i = 0; i < getSize(); i++) {
                if (!T.contains(i) && cost[i] < currentMinCost) {
                    currentMinCost = cost[i];
                    u = i;
                }
            }

            T.add(u); // Add a new vertex to T
            totalWeight += cost[u]; // Add cost[u] to the tree

            // Adjust cost[v] for v that is adjacent to u and v in V - T
            for (Edge e : neighbors.get(u)) {
                if (!T.contains(e.v) && cost[e.v] > ((WeightedEdge)e).weight) {
                    cost[e.v] = ((WeightedEdge)e).weight;
                    parent[e.v] = u;
                }
            }
        } // End of while

        return new MST(startingVertex, parent, T, totalWeight);
    }

    /** MST is an inner class in WeightedGraph */
    public class MST extends Tree {
        private double totalWeight; // Total weight of all edges in the tree

        public MST(int root, int[] parent, List<Integer> searchOrder, double totalWeight) {
            super(root, parent, searchOrder);
            this.totalWeight = totalWeight;
        }

        public double getTotalWeight() {
            return totalWeight;
        }
    }

    /** Find single source shortest paths */
    public ShortestPathTree getShortestPath(int sourceVertex) {
        // cost[v] stores the cost of the path from v to the source
        double[] cost = new double[getSize()];
        for (int i = 0; i < cost.length; i++) {
            cost[i] = Double.POSITIVE_INFINITY; // Initial cost set to infinity
        }
        cost[sourceVertex] = 0; // Cost of source is 0

        // parent[v] stores the previous vertex of v in the path
        int[] parent = new int[getSize()];
        parent[sourceVertex] = -1; // The parent of source is set to -1

        // T stores the vertices whose path found so far
        List<Integer> T = new ArrayList<>();

        // Expand T
        while (T.size() < getSize()) {
            // Find smallest cost v in V - T
            int u = -1; // Vertex to be determined
            double currentMinCost = Double.POSITIVE_INFINITY;
            for (int i = 0; i < getSize(); i++) {
                if (!T.contains(i) && cost[i] < currentMinCost) {
                    currentMinCost = cost[i];
                    u = i;
                }
            }

            T.add(u); // Add a new vertex to T

            // Adjust cost[v] for v that is adjacent to u and v in V - T
            for (Edge e : neighbors.get(u)) {
                if (!T.contains(e.v) && cost[e.v] > cost[u] + ((WeightedEdge)e).weight) {
                    cost[e.v] = cost[u] + ((WeightedEdge)e).weight;
                    parent[e.v] = u;
                }
            }
        } // End of while

        // Create a ShortestPathTree
        return new ShortestPathTree(sourceVertex, parent, T, cost);
    }

    /** ShortestPathTree is an inner class in WeightedGraph */
    public class ShortestPathTree extends Tree {
        private double[] cost; // cost[v] is the cost from v to source

        /** Construct a path */
        public ShortestPathTree(int source, int[] parent, List<Integer> searchOrder, double[] cost) {
            super(source, parent, searchOrder);
            this.cost = cost;
        }

        /** Return the cost for a path from the root to vertex v */
        public double getCost(int v) {
            return cost[v];
        }

        /** Print paths from all vertices to the source */
        public void printAllPaths() {
            System.out.println("All shortest paths from " + vertices.get(getRoot()) + " are:");
            for (int i = 0; i < cost.length; i++) {
                printPath(i); // Print a path from i to the source
                System.out.println("(cost: " + cost[i] + ")"); // Path cost
            }
        }
    }
}

WeightedGraph クラスは、AbstractGraph クラスを拡張します (3 行目)。 AbstractGraph のプロパティ vertices と neighbors は、リストである WeightedGraph.neighbors に継承されます。各要素はリストであり、エッジを含む別のリストです。重み付けされていないグラフの場合、各エッジは AbstractGraph.Edge のインスタンスです。重み付きグラフの場合、各エッジは WeightedEdge のインスタンスです。 WeightedEdge は Edge のサブタイプです。したがって、重み付きグラフの重み付きエッジを neighbors.get(i) に追加できます (行 47)。

以下のコードは、下図のグラフと下図 a のグラフを作成するテスト プログラムを提供します。

package demo;

public class TestWeightedGraph {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1, 807}, {0, 3, 1331}, {0, 5, 2097},
                {1, 0, 807}, {1, 2, 381}, {1, 3, 1267},
                {2, 1, 381}, {2, 3, 1015}, {2, 4, 1663}, {2, 10, 1435},
                {3, 0, 1331}, {3, 1, 1267}, {3, 2, 1015}, {3, 4, 599}, {3, 5, 1003},
                {4, 2, 1663}, {4, 3, 599}, {4, 5, 533}, {4, 7, 1260}, {4, 8, 864}, {4, 10, 496},
                {5, 0, 2097}, {5, 3, 1003}, {5, 4, 533}, {5, 6, 983}, {5, 7, 787},
                {6, 5, 983}, {6, 7, 214},
                {7, 4, 1260}, {7, 5, 787}, {7, 6, 214}, {7, 8, 888},
                {8, 4, 864}, {8, 7, 888}, {8, 9, 661}, {8, 10, 781}, {8, 11, 810},
                {9, 8, 661}, {9, 11, 1187},
                {10, 2, 1435}, {10, 4, 496}, {10, 8, 781}, {10, 11, 239},
                {11, 8, 810}, {11, 9, 1187}, {11, 10, 239}
        };

        WeightedGraph<String> graph1 = new WeightedGraph<>(vertices, edges);
        System.out.println("The number of vertices in graph1: " + graph1.getSize());
        System.out.println("The vertex with index 1 is " + graph1.getVertex(1));
        System.out.println("The index for Miami is " + graph1.getIndex("Miami"));
        System.out.println("The edges for graph1:");
        graph1.printWeightedEdges();

        edges = new int[][] {
            {0, 1, 2}, {0, 3, 8},
            {1, 0, 2}, {1, 2, 7}, {1, 3, 3},
            {2, 1, 7}, {2, 3, 4}, {2, 4, 5},
            {3, 0, 8}, {3, 1, 3}, {3, 2, 4}, {3, 4, 6},
            {4, 2, 5}, {4, 3, 6}
        };
        WeightedGraph<Integer> graph2 = new WeightedGraph<>(edges, 5);
        System.out.println("\nThe edges for graph2:");
        graph2.printWeightedEdges();
    }
}

グラフ1の頂点の数: 12
インデックス 1 の頂点はサンフランシスコです
マイアミの指数は 9
グラフ 1 のエッジ:
頂点 0: (0, 1, 807) (0, 3, 1331) (0, 5, 2097)
頂点 1: (1, 2, 381) (1, 0, 807) (1, 3, 1267)
頂点 2: (2, 1, 381) (2, 3, 1015) (2, 4, 1663) (2, 10, 1435)
頂点 3: (3, 4, 599) (3, 5, 1003) (3, 1, 1267)
(3, 0, 1331) (3, 2, 1015)
頂点 4: (4, 10, 496) (4, 8, 864) (4, 5, 533) (4, 2, 1663)
(4, 7, 1260) (4, 3, 599)
頂点 5: (5, 4, 533) (5, 7, 787) (5, 3, 1003)
(5, 0, 2097) (5, 6, 983)
頂点 6: (6, 7, 214) (6, 5, 983)
頂点 7: (7, 6, 214) (7, 8, 888) (7, 5, 787) (7, 4, 1260)
頂点 8: (8, 9, 661) (8, 10, 781) (8, 4, 864)
(8, 7, 888) (8, 11, 810)
頂点 9: (9, 8, 661) (9, 11, 1187)
頂点 10: (10, 11, 239) (10, 4, 496) (10, 8, 781) (10, 2, 1435)
頂点 11: (11, 10, 239) (11, 9, 1187) (11, 8, 810)

グラフ 2 のエッジ:
頂点 0: (0, 1, 2) (0, 3, 8)
頂点 1: (1, 0, 2) (1, 2, 7) (1, 3, 3)
頂点 2: (2, 3, 4) (2, 1, 7) (2, 4, 5)
頂点 3: (3, 1, 3) (3, 4, 6) (3, 2, 4) (3, 0, 8)
頂点 4: (4, 2, 5) (4, 3, 6)

Atur cara mencipta graf1 untuk graf dalam Rajah di atas dalam baris 3–27. Bucu untuk graf1 ditakrifkan dalam baris 3–5. Tepi untuk graf1 ditakrifkan dalam baris 7–24. Tepi diwakili menggunakan tatasusunan dua dimensi. Untuk setiap baris i dalam tatasusunan, tepi[i][0] dan tepi[i][1] menunjukkan bahawa terdapat tepi dari bucu tepi[i] [0] ke bucu tepi[i][1] dan berat untuk tepi ialah tepi[i][2]. Contohnya, {0, 1, 807} (baris 8) mewakili tepi dari bucu 0 (tepi[ 0][0]) ke bucu 1 (tepi[0][1]) dengan berat 807 (tepi[0] [2]). {0, 5, 2097} (baris 8) mewakili tepi daripada bucu 0 (tepi[2][][2][ 0]) ke bucu 5 (tepi[2][1]) dengan berat 2097 (tepi[2][2] ). Baris 35 menggunakan kaedah printWeightedEdges() pada graf1 untuk memaparkan semua tepi dalam graf1.

Atur cara mencipta tepi untuk graf2 untuk graf dalam Rajah di atas a dalam baris 37–44. Baris 46 menggunakan kaedah printWeightedEdges() pada graf2 untuk memaparkan semua tepi dalam graf2.

以上がWeightedGraph クラスの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。