Java语言程序设计与数据结构（基础篇）第15章课后习题代码chapter15.rar

import java.util.*; public class Exercise29_18 { 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<>(edges, vertices); WeightedGraph<String>.ShortestPathTree tree1 = graph1 .getShortestPath(graph1.getIndex("Chicago")); tree1.printAllPaths(); // Display shortest paths from Houston to Chicago System.out.print("Shortest path from Houston to Chicago: "); java.util.List<String> path = tree1.getPath(graph1.getIndex("Houston")); for (String s : path) { System.out.print(s + " "); } 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<Integer>(edges, 5); WeightedGraph<Integer>.ShortestPathTree tree2 = graph2.getShortestPath(3); System.out.println("\n"); tree2.printAllPaths(); } public static interface Graph<V> { /** Return the number of vertices in the graph */ public int getSize(); /** Return the vertices in the graph */ public java.util.List<V> getVertices(); /** Return the object for the specified vertex index */ public V getVertex(int index); /** Return the index for the specified vertex object */ public int getIndex(V v); /** Return the neighbors of vertex with the specified index */ public java.util.List<Integer> getNeighbors(int index); /** Return the degree for a specified vertex */ public int getDegree(int v); /** Print the edges */ public void printEdges(); /** Clear graph */ public void clear(); /** Add a vertex to the graph */ public boolean addVertex(V vertex); /** Add an edge to the graph */ public boolean addEdge(int u, int v); /** Obtain a depth-first search tree */ public AbstractGraph<V>.Tree dfs(int v); /** Obtain a breadth-first search tree */ public AbstractGraph<V>.Tree bfs(int v); } public static abstract class AbstractGraph<V> implements Graph<V> { protected List<V> vertices = new ArrayList<V>(); // Store vertices protected List<List<Integer>> neighbors = new ArrayList<List<Integer>>(); // Adjacency lists /** Construct an empty graph */ protected AbstractGraph() { } /** Construct a graph from edges and vertices stored in arrays */ protected AbstractGraph(int[][] edges, V[] vertices) { for (int i = 0; i < vertices.length; i++) addVertex(vertices[i]); createAdjacencyLists(edges, vertices.length); } /** Construct a graph from edges and vertices stored in List */ protected AbstractGraph(List<Edge> edges, List<V> vertices) { for (int i = 0; i < vertices.size(); i++) addVertex(vertices.get(i)); createAdjacencyLists(edges, vertices.size()); } /** Construct a graph for integer vertices 0, 1, 2 and edge list */ protected AbstractGraph(List<Edge> edges, int numberOfVertices) { for (int i = 0; i < numberOfVertices; i++) addVertex((V)(new Integer(i))); // vertices is {0, 1, ...} createAdjacencyLists(edges, numberOfVertices); } /** Construct a graph from integer vertices 0, 1, and edge array */ protected AbstractGraph(int[][] edges, int numberOfVertices) { for (int i = 0; i < numberOfVertices; i++) addVertex((V)(new Integer(i))); // vertices is {0, 1, ...} createAdjacencyLists(edges, numberOfVertices); } /** Create adjacency lists for each vertex */ private void createAdjacencyLists( int[][] edges, int numberOfVertices) { for (int i = 0; i < edges.length; i++) { int u = edges[i][0]; int v = edges[i][1]; addEdge(u, v); } } /** Create adjacency lists for each vertex */ private void createAdjacencyLists( List<Edge> edges, int numberOfVertices) { for (Edge edge: edges) { addEdge(edge.u, edge.v); } } @Override /** Return the number of vertices in the graph */ public int getSize() { return vertices.size(); } @Override /** Return the vertices in the graph */ public List<V> getVertices() { return vertices; } @Override /** Return the object for the specified vertex */ public V getVertex(int index) { return vertices.get(index); } @Override /** Return the index for the specified vertex object */ public int getIndex(V v) { return vertices.indexOf(v); } @Override /** Return the neighbors of the specified vertex */ public List<Integer> getNeighbors(int index) { return neighbors.get(index); } @Override /** Return the degree for a specified vertex */ public int getDegree(int v) { return neighbors.get(v).size(); } @Override /** Print the edges */ public void printEdges() { for (int u = 0; u < neighbors.size(); u++) { System.out.print(getVertex(u) + " (" + u + "): "); for (int j = 0; j < neighbors.get(u).size(); j++) { System.out.print("(" + u + ", " + neighbors.get(u).get(j) + ") "); } System.out.println(); } } @Override /** Clear graph */ public void clear() { vertices.clear(); neighbors.clear(); } @Override /** Add a vertex to the graph */ public boolean addVertex(V vertex) { if (!vertices.contains(vertex)) { vertices.add(vertex); neighbors.add(new ArrayList<Integer>()); return true; } else { return false; } } @Override /** Add an edge to the graph */ public boolean addEdge(int u, int v) { if (u < 0 || u > getSize() - 1) throw new IllegalArgumentException("No such index: " + u); if (v < 0 || v > getSize() - 1) throw new IllegalArgumentException("No such index: " + v); if (!neighbors.get(u).contains(v)) { neighbors.get(u).add(v); return true; } else { return false; } } /** Edge inner class inside the AbstractGraph class */ public static class Edge { public int u; // Starting vertex of the edge public int v; // Ending vertex of the edge /** Construct an edge for (u, v) */ public Edge(int u, int v) { this.u = u; this.v = v; } } @Override /** Obtain a DFS tree starting from vertex v */ /** To be discussed in Section 30.6 */ public Tree dfs(int v) { List<Integer> searchOrder = new ArrayList<Integer>(); int[] parent = new int[vertices