《Java数据结构和算法》第二版 Robert lafore 编程作业 第十四章

《Java数据结构和算法》第二版 Robert lafore 编程作业 第十四章

/*14.1 修改path.java(清单14.2)，打印一张任意两点间最小耗费的表。这个 练习需要修改原来假设源点总是A的例程。 */package chap14.pp1;// path.java// demonstrates shortest path with weighted, directed graphs// to run this program: C>java PathApp////////////////////////////////////////////////////////////////class DistPar             // distance and parent{                      // items stored in sPath arraypublic int distance;   // distance from start to this vertexpublic int parentVert; // current parent of this vertex// -------------------------public DistPar(int pv, int d)  // constructor{distance = d;parentVert = pv;}// -------------------------}  // end class DistPar// /////////////////////////////////////////////////////////////class Vertex {public char label;        // label (e.g. 'A')public boolean isInTree;// -------------------------public Vertex(char lab)   // constructor{label = lab;isInTree = false;}// -------------------------}  // end class Vertex// //////////////////////////////////////////////////////////////class Graph {private final int MAX_VERTS = 20;private final int INFINITY = 1000000;private Vertex vertexList[]; // list of verticesprivate int adjMat[][];      // adjacency matrixprivate int nVerts;          // current number of verticesprivate int nTree;           // number of verts in treeprivate DistPar sPath[];     // array for shortest-path dataprivate int currentVert;     // current vertexprivate int startToCurrent;  // distance to currentVert// -------------------------public Graph()               // constructor{vertexList = new Vertex[MAX_VERTS];// adjacency matrixadjMat = new int[MAX_VERTS][MAX_VERTS];nVerts = 0;nTree = 0;for (int j = 0; j < MAX_VERTS; j++)// set adjacencyfor (int k = 0; k < MAX_VERTS; k++)// matrixadjMat[j][k] = INFINITY;     // to infinitysPath = new DistPar[MAX_VERTS];    // shortest paths}  // end constructor// -------------------------public void addVertex(char lab) {vertexList[nVerts++] = new Vertex(lab);}// -------------------------public void addEdge(int start, int end, int weight) {adjMat[start][end] = weight;  // (directed)}// -------------------------public void path()                // find all shortest paths{// ==============================================// 编程作业 14.1// 外层加了个for循环for (int i = 0; i < nVerts; i++) {int startTree = i;             // start at vertex 0vertexList[startTree].isInTree = true;nTree = 1;                     // put it in tree// transfer row of distances from adjMat to sPathfor (int j = 0; j < nVerts; j++) {int tempDist = adjMat[startTree][j];sPath[j] = new DistPar(startTree, tempDist);}// until all vertices are in the treewhile (nTree < nVerts) {int indexMin = getMin();    // get minimum from sPathint minDist = sPath[indexMin].distance;if (minDist == INFINITY)     // if all infinite{                        // or in tree,System.out.println("There are unreachable vertices");break;                   // sPath is complete} else {                        // reset currentVertcurrentVert = indexMin;  // to closest vertstartToCurrent = sPath[indexMin].distance;// minimum distance from startTree is// to currentVert, and is startToCurrent}// put current vertex in treevertexList[currentVert].isInTree = true;nTree++;adjust_sPath();             // update sPath[] array}  // end while(nTree<nVerts)if (nTree == nVerts) {System.out.println("There are all reachable vertices");}displayPaths();                // display sPath[] contentsnTree = 0;                     // clear treefor (int j = 0; j < nVerts; j++)vertexList[j].isInTree = false;// ==============================================}}  // end path()// -------------------------public int getMin()               // get entry from sPath{                              // with minimum distanceint minDist = INFINITY;        // assume minimumint indexMin = 0;for (int j = 1; j < nVerts; j++)    // for each vertex,{                           // if it's in tree andif (!vertexList[j].isInTree &&  // smaller than old onesPath[j].distance < minDist) {minDist = sPath[j].distance;indexMin = j;            // update minimum}}  // end forreturn indexMin;               // return index of minimum}  // end getMin()// -------------------------public void adjust_sPath() {// adjust values in shortest-path array sPathint column = 1;                // skip starting vertexwhile (column < nVerts)         // go across columns{// if this column's vertex already in tree, skip itif (vertexList[column].isInTree) {column++;continue;}// calculate distance for one sPath entry// get edge from currentVert to columnint currentToFringe = adjMat[currentVert][column];// add distance from startint startToFringe = startToCurrent + currentToFringe;// get distance of current sPath entryint sPathDist = sPath[column].distance;// compare distance from start with sPath entryif (startToFringe < sPathDist)   // if shorter,{                            // update sPathsPath[column].parentVert = currentVert;sPath[column].distance = startToFringe;}column++;}  // end while(column < nVerts)}  // end adjust_sPath()// -------------------------public void displayPaths() {for (int j = 0; j < nVerts; j++) // display contents of sPath[]{System.out.print(vertexList[j].label + "="); // B=if (sPath[j].distance == INFINITY)System.out.print("inf");                  // infelseSystem.out.print(sPath[j].distance);      // 50char parent = vertexList[sPath[j].parentVert].label;System.out.print("(" + parent + ") ");       // (A)}System.out.println("");}// -------------------------}  // end class Graph// //////////////////////////////////////////////////////////////public class PathApp {public static void main(String[] args) {Graph theGraph = new Graph();theGraph.addVertex('A');     // 0 (start)theGraph.addVertex('B');     // 1theGraph.addVertex('C');     // 2theGraph.addVertex('D');     // 3theGraph.addVertex('E');     // 4theGraph.addEdge(0, 1, 50);  // AB 50theGraph.addEdge(0, 3, 80);  // AD 80theGraph.addEdge(1, 2, 60);  // BC 60theGraph.addEdge(1, 3, 90);  // BD 90theGraph.addEdge(2, 4, 40);  // CE 40theGraph.addEdge(3, 2, 20);  // DC 20theGraph.addEdge(3, 4, 70);  // DE 70theGraph.addEdge(4, 1, 50);  // EB 50System.out.println("Shortest paths");theGraph.path();             // shortest pathsSystem.out.println();}  // end main()}  // end class PathApp// //////////////////////////////////////////////////////////////

/*14.2 迄今为止已经用邻接矩阵和邻接表实现了图。另一个方法是用Java有引用  代表边，这样Vertex对象就包含一个对其邻接点的引用列表。在有向图中，  这种方式的引用尤其直观。因为它“指明”从一个顶点到另一个顶点。写程  序实现这个表示方法。main()方法应该与path.java程序(清单)的图。然  后，它应该显示图的连通性表，以证明图被正确的构建。还要在某处存储  每条边的权值。一个方法是使用Edge类，类中存储权值和边的终点。每个  顶点拥有一个Edge对象的列表--即，从这个顶点开始的边。 */package chap14.pp2;import java.util.ArrayList;import java.util.List;// path.java// demonstrates shortest path with weighted, directed graphs// to run this program: C>java PathApp////////////////////////////////////////////////////////////////class DistPar             // distance and parent{                      // items stored in sPath arraypublic int distance;   // distance from start to this vertexpublic int parentVert; // current parent of this vertex// -------------------------public DistPar(int pv, int d)  // constructor{distance = d;parentVert = pv;}// -------------------------}  // end class DistPar// /////////////////////////////////////////////////////////////class Vertex {public char label;        // label (e.g. 'A')public boolean isInTree;public List<Edge> edges; // list of vertices// -------------------------public Vertex(char lab)   // constructor{label = lab;isInTree = false;edges = new ArrayList<Edge>();}// 添加边public void addEdge(Edge edge) {this.edges.add(edge);}// -------------------------}  // end class Vertex// //////////////////////////////////////////////////////////////class Edge {public int weight;public int end; // 边的终点public Edge(int weight, int end) {this.weight = weight;this.end = end;}}// //////////////////////////////////////////////////////////////class Graph {private final int MAX_VERTS = 20;private final int INFINITY = 1000000;private Vertex[] vertexs;private int nVerts;private int nTree;private DistPar sPath[];     // array for shortest-path dataprivate int currentVert;     // current vertexprivate int startToCurrent;  // distance to currentVertpublic Graph() {this.vertexs = new Vertex[MAX_VERTS];this.sPath = new DistPar[MAX_VERTS];    // shortest paths}public void addEdge(int start, int end, int weight) {Edge edge = new Edge(weight, end);vertexs[start].addEdge(edge);}// -------------------------public void addVertex(char lab) {vertexs[nVerts++] = new Vertex(lab);}// -------------------------public void path()                // find all shortest paths{for (int k = 0; k < nVerts; k++) {int startTree = k;             // start at vertex 0vertexs[startTree].isInTree = true;nTree = 1;                     // put it in tree// transfer row of distances from adjMat to sPathList<Edge> edgesList = vertexs[startTree].edges;for (int i = 0; i < MAX_VERTS; i++) {sPath[i] = new DistPar(startTree, INFINITY);}for (int i = 0; i < edgesList.size(); i++) {Edge tempEdge = edgesList.get(i);sPath[tempEdge.end] = new DistPar(startTree, tempEdge.weight);}// until all vertices are in the treewhile (nTree < nVerts) {int indexMin = getMin();    // get minimum from sPathint minDist = sPath[indexMin].distance;if (minDist == INFINITY)     // if all infinite{                        // or in tree,System.out.println("There are unreachable vertices");break;                   // sPath is complete} else {                        // reset currentVertcurrentVert = indexMin;  // to closest vertstartToCurrent = sPath[indexMin].distance;// minimum distance from startTree is// to currentVert, and is startToCurrent}// put current vertex in treevertexs[currentVert].isInTree = true;nTree++;adjust_sPath();             // update sPath[] array}  // end while(nTree<nVerts)if (nTree == nVerts) {System.out.println("There are all reachable vertices");}displayPaths();                // display sPath[] contentsnTree = 0;                     // clear treefor (int j = 0; j < nVerts; j++)vertexs[j].isInTree = false;}}  // end path()// -------------------------public int getMin()               // get entry from sPath{                              // with minimum distanceint minDist = INFINITY;        // assume minimumint indexMin = 0;for (int j = 1; j < nVerts; j++)    // for each vertex,{                           // if it's in tree andif (!vertexs[j].isInTree &&  // smaller than old onesPath[j].distance < minDist) {minDist = sPath[j].distance;indexMin = j;            // update minimum}}  // end forreturn indexMin;               // return index of minimum}  // end getMin()// -------------------------public void adjust_sPath() {// adjust values in shortest-path array sPathList<Edge> list = vertexs[currentVert].edges;for (int i = 0; i < list.size(); i++)         // go across columns{// if this column's vertex already in tree, skip itint v = list.get(i).end;if (vertexs[v].isInTree) {continue;}// calculate distance for one sPath entry// get edge from currentVert to fringeEdge e = list.get(i);int fringe = e.end;int currentToFringe = e.weight;// add distance from startint startToFringe = startToCurrent + currentToFringe;// get distance of current sPath entryint sPathDist = sPath[fringe].distance;// compare distance from start with sPath entryif (startToFringe < sPathDist)   // if shorter,{                            // update sPathsPath[fringe].parentVert = currentVert;sPath[fringe].distance = startToFringe;}}  // end while(column < nVerts)}  // end adjust_sPath()// -------------------------public void displayPaths() {for (int j = 0; j < nVerts; j++) // display contents of sPath[]{System.out.print(vertexs[j].label + "="); // B=if (sPath[j].distance == INFINITY)System.out.print("inf");                  // infelseSystem.out.print(sPath[j].distance);      // 50char parent = vertexs[sPath[j].parentVert].label;System.out.print("(" + parent + ") ");       // (A)}System.out.println("");}// -------------------------}  // end class Graph// //////////////////////////////////////////////////////////////public class PathApp {public static void main(String[] args) {Graph theGraph = new Graph();theGraph.addVertex('A');     // 0 (start)theGraph.addVertex('B');     // 1theGraph.addVertex('C');     // 2theGraph.addVertex('D');     // 3theGraph.addVertex('E');     // 4theGraph.addEdge(0, 1, 50);  // AB 50theGraph.addEdge(0, 3, 80);  // AD 80theGraph.addEdge(1, 2, 60);  // BC 60theGraph.addEdge(1, 3, 90);  // BD 90theGraph.addEdge(2, 4, 40);  // CE 40theGraph.addEdge(3, 2, 20);  // DC 20theGraph.addEdge(3, 4, 70);  // DE 70theGraph.addEdge(4, 1, 50);  // EB 50System.out.println("Shortest paths");theGraph.path();             // shortest pathsSystem.out.println();}  // end main()}  // end class PathApp// //////////////////////////////////////////////////////////////

/*14.3 实现Floyd算法。可以从path.java程序（清单14.2）开始，适当地修改它。 例如，可以删除所有的最短路径代码。保留对不可到达顶点为无穷大的表示 法。这样作，当比较新得到的耗费和已存在的耗费时，就不再需要检查0。 所有可能到达的路线的耗费都比无穷大小。可以在main()方法中构建任意 复杂的图。 */package chap14.pp3;// path.java// demonstrates shortest path with weighted, directed graphs// to run this program: C>java PathApp// /////////////////////////////////////////////////////////////class Vertex {public char label;        // label (e.g. 'A')public boolean isInTree;// -------------------------public Vertex(char lab)   // constructor{label = lab;isInTree = false;}public String toString() {return String.valueOf(label);}// -------------------------}  // end class Vertex// //////////////////////////////////////////////////////////////class Graph {private final int MAX_VERTS = 20;private final int INFINITY = 1000000;private Vertex vertexList[]; // list of verticesprivate int adjMat[][];      // adjacency matrixprivate int nVerts;          // current number of vertices// -------------------------public Graph()               // constructor{vertexList = new Vertex[MAX_VERTS];// adjacency matrixadjMat = new int[MAX_VERTS][MAX_VERTS];nVerts = 0;for (int j = 0; j < MAX_VERTS; j++)// set adjacencyfor (int k = 0; k < MAX_VERTS; k++)// matrixadjMat[j][k] = INFINITY;     // to infinity}  // end constructor// -------------------------public void addVertex(char lab) {vertexList[nVerts++] = new Vertex(lab);}// -------------------------public void addEdge(int start, int end, int weight) {adjMat[start][end] = weight;  // (directed)}// -------------------------// ==========================================================public void floyd() {for (int i = 0; i < nVerts; i++) {for (int j = 0; j < nVerts; j++) {if (adjMat[i][j] < INFINITY) {for (int k = 0; k < nVerts; k++) {if (adjMat[k][i] < INFINITY) {int temp = adjMat[k][i] + adjMat[i][j];if (adjMat[k][j] > temp) {adjMat[k][j] = temp;}}}}}}}// ==========================================================// -------------------------public void display() {for (int i = 0; i < nVerts; i++) {System.out.print("" + vertexList[i]);}System.out.println();for (int j = 0; j < nVerts; j++) // display contents of sPath[]{System.out.print(vertexList[j]);for (int i = 0; i < nVerts; i++) {int temp = adjMat[j][i];if (temp != INFINITY)System.out.print("" + adjMat[j][i]);else {System.out.print("");}}System.out.println();}System.out.println();}// -------------------------}  // end class Graph// //////////////////////////////////////////////////////////////public class PathApp {public static void main(String[] args) {Graph theGraph = new Graph();theGraph.addVertex('A');     // 0 (start)theGraph.addVertex('B');     // 1theGraph.addVertex('C');     // 2theGraph.addVertex('D');     // 3theGraph.addVertex('E');     // 4theGraph.addEdge(0, 1, 50);  // AB 50theGraph.addEdge(0, 3, 80);  // AD 80theGraph.addEdge(1, 2, 60);  // BC 60theGraph.addEdge(1, 3, 90);  // BD 90theGraph.addEdge(2, 4, 40);  // CE 40theGraph.addEdge(3, 2, 20);  // DC 20theGraph.addEdge(3, 4, 70);  // DE 70theGraph.addEdge(4, 1, 50);  // EB 50System.out.println("before floyd!");theGraph.display();theGraph.floyd();System.out.println("after floyd!");theGraph.display();             // shortest paths}  // end main()}  // end class PathApp// //////////////////////////////////////////////////////////////

/*14.4 实现本单“难题”中描述的旅行商问题。不考虑它的难度，当N较小时，比   如10或更小，这个问题很好解决。在无向图上尝试一下。使用穷举法测   试每种可能的城市序列。序列改变的方式，参考第6章“递归”中的   anagram.java程序(清单6.2)。用无穷大表示不存在的边。这样做，当   从一个城市到下一个城市的边不存在的情况发生时，不需要中止对序列的   计算；任何无穷大的权值总和都是不可能的路线。而且，不必考虑消除对   称路线的情况，例如ABCDEA和AEDCBA都要显示 */package chap14.pp4;import java.util.ArrayList;import java.util.List;// path.java// demonstrates shortest path with weighted, directed graphs// to run this program: C>java PathApp// /////////////////////////////////////////////////////////////class Vertex {public char label;        // label (e.g. 'A')public boolean isInTree;// -------------------------public Vertex(char lab)   // constructor{label = lab;isInTree = false;}// -------------------------}  // end class Vertex// //////////////////////////////////////////////////////////////class Graph {private final int MAX_VERTS = 20;private final int INFINITY = 1000000;private Vertex vertexList[]; // list of verticesprivate int adjMat[][];      // adjacency matrixprivate int nVerts;          // current number of verticesprivate int vertexs[];// array for index of vertex in vertexListprivate List<int[]> list;// save the possible vertexs[] ;// -------------------------public Graph()               // constructor{vertexList = new Vertex[MAX_VERTS];// adjacency matrixadjMat = new int[MAX_VERTS][MAX_VERTS];nVerts = 0;for (int j = 0; j < MAX_VERTS; j++)// set adjacencyfor (int k = 0; k < MAX_VERTS; k++)// matrixadjMat[j][k] = INFINITY;     // to infinity}  // end constructor// -------------------------public void addVertex(char lab) {vertexList[nVerts++] = new Vertex(lab);}// -------------------------public void addEdge(int start, int end, int weight) {adjMat[start][end] = weight;  // (directed)}// -------------------------// ===========================================================public void displayWord() {int minIndex = 0;int minWeight = INFINITY;for (int i = 0; i < list.size(); i++) {int weight = 0;int[] temp = list.get(i);for (int j = 0; j < temp.length - 1; j++) {weight += adjMat[temp[j]][temp[j + 1]];}weight += adjMat[temp[temp.length - 1]][temp[0]];if (weight < minWeight) {minWeight = weight;minIndex = i;}}int[] min = list.get(minIndex);for (int j = 0; j < nVerts; j++) {System.out.print(" " + vertexList[min[j]].label);}System.out.print(" " + vertexList[min[0]].label);System.out.println("(" + minWeight + ")");}// ===========================================================// 编程作业 14.4public void travelingSalesman() {vertexs = new int[nVerts];list = new ArrayList();for (int i = 0; i < nVerts; i++) {vertexs[i] = i;}doAnagram(vertexs.length);}// ===========================================================public void doAnagram(int newSize) {if (newSize == 1) {                    // if too small,for (int i = 0; i < nVerts - 1; i++) {if (adjMat[vertexs[i]][vertexs[i + 1]] == INFINITY) {return;}}if (adjMat[vertexs[nVerts - 1]][vertexs[0]] != INFINITY) {// 最后一个顶点到起始点int[] temp = new int[nVerts];System.arraycopy(vertexs, 0, temp, 0, nVerts);list.add(temp);}return;}                          // go no furtherfor (int j = 0; j < newSize; j++)         // for each position,{doAnagram(newSize - 1);             // anagram remainingrotate(newSize);}}// ===========================================================public void rotate(int newSize)// rotate left all chars from position to end{int j;int position = nVerts - newSize;int temp = vertexs[position];       // save first letterfor (j = position + 1; j < nVerts; j++)// shift others leftvertexs[j - 1] = vertexs[j];vertexs[j - 1] = temp;                 // put first on right}// ===========================================================}  // end class Graph// //////////////////////////////////////////////////////////////public class PathApp {public static void main(String[] args) {Graph theGraph = new Graph();theGraph.addVertex('A'); // 0 (start)theGraph.addVertex('B'); // 1theGraph.addVertex('C'); // 2theGraph.addVertex('D'); // 3theGraph.addVertex('E'); // 4theGraph.addEdge(0, 1, 50); // AB 50theGraph.addEdge(0, 2, 50); // AC 50theGraph.addEdge(1, 0, 50); // BA 50theGraph.addEdge(3, 0, 80); // DA 80theGraph.addEdge(1, 2, 60); // BC 60theGraph.addEdge(1, 3, 90); // BD 90theGraph.addEdge(2, 3, 40); // CD 40theGraph.addEdge(3, 4, 20); // DE 20theGraph.addEdge(4, 0, 70); // EA 70theGraph.addEdge(4, 1, 50); // EB 50theGraph.travelingSalesman();theGraph.displayWord();System.out.println("over!");}  // end main()}  // end class PathApp// //////////////////////////////////////////////////////////////

/* 14.5 编写程序找到并显示带权无向图的所有汉密尔顿回路。 */package chap14.pp5;// path.java// demonstrates shortest path with weighted, directed graphs// to run this program: C>java PathApp////////////////////////////////////////////////////////////////class DistPar             // distance and parent{                      // items stored in sPath arraypublic int distance;   // distance from start to this vertexpublic int parentVert; // current parent of this vertex// -------------------------public DistPar(int pv, int d)  // constructor{distance = d;parentVert = pv;}// -------------------------}  // end class DistPar// /////////////////////////////////////////////////////////////class Vertex {public char label;        // label (e.g. 'A')public boolean isInTree;// -------------------------public Vertex(char lab)   // constructor{label = lab;isInTree = false;}// -------------------------}  // end class Vertex// //////////////////////////////////////////////////////////////class Graph {private final int MAX_VERTS = 20;private final int INFINITY = 1000000;private Vertex vertexList[]; // list of verticesprivate int adjMat[][];      // adjacency matrixprivate int nVerts;          // current number of verticesprivate int vertexs[];// array for index of vertex in vertexList// -------------------------public Graph()               // constructor{vertexList = new Vertex[MAX_VERTS];// adjacency matrixadjMat = new int[MAX_VERTS][MAX_VERTS];nVerts = 0;for (int j = 0; j < MAX_VERTS; j++)// set adjacencyfor (int k = 0; k < MAX_VERTS; k++)// matrixadjMat[j][k] = INFINITY;     // to infinity}  // end constructor// -------------------------public void addVertex(char lab) {vertexList[nVerts++] = new Vertex(lab);}// -------------------------public void addEdge(int start, int end, int weight) {adjMat[start][end] = weight;  // (directed)adjMat[end][start] = weight;  // (directed)}// -------------------------// ===========================================================public void displayWord() {for (int j = 0; j < nVerts; j++) {System.out.print(" " + vertexList[vertexs[j]].label);}System.out.println(" " + vertexList[vertexs[0]].label);}// ===========================================================// 编程作业 14.5public void travelingSalesman() {vertexs = new int[nVerts];for (int i = 0; i < nVerts; i++) {vertexs[i] = i;}doAnagram(vertexs.length);}// ===========================================================public void doAnagram(int newSize) {if (newSize == 1) {                    // if too small,for (int i = 0; i < nVerts - 1; i++) {if (adjMat[vertexs[i]][vertexs[i + 1]] == INFINITY) {return;}}if (adjMat[vertexs[nVerts - 1]][vertexs[0]] != INFINITY) {// 最后一个顶点到起始点displayWord();}return;}                          // go no furtherfor (int j = 0; j < newSize; j++)         // for each position,{doAnagram(newSize - 1);             // anagram remainingrotate(newSize);}}// ===========================================================public void rotate(int newSize)// rotate left all chars from position to end{int j;int position = nVerts - newSize;int temp = vertexs[position];       // save first letterfor (j = position + 1; j < nVerts; j++)// shift others leftvertexs[j - 1] = vertexs[j];vertexs[j - 1] = temp;                 // put first on right}// ===========================================================}  // end class Graph// //////////////////////////////////////////////////////////////public class PathApp {public static void main(String[] args) {Graph theGraph = new Graph();theGraph.addVertex('A'); // 0 (start)theGraph.addVertex('B'); // 1theGraph.addVertex('C'); // 2theGraph.addVertex('D'); // 3theGraph.addVertex('E'); // 4theGraph.addEdge(0, 1, 50); // AB 50theGraph.addEdge(0, 2, 50); // AC 50theGraph.addEdge(1, 3, 90); // BD 90theGraph.addEdge(2, 3, 40); // CD 40theGraph.addEdge(3, 4, 20); // DE 20theGraph.addEdge(4, 0, 70); // EA 70theGraph.addEdge(4, 1, 50); // EB 50theGraph.travelingSalesman();theGraph.displayWord();System.out.println("over!");}  // end main()}  // end class PathApp// //////////////////////////////////////////////////////////////