求（有向）图中任意两点间所有路径 1建图： 图类中包括如下信息：顶点集合，邻接矩阵。 节点类中包括如下信息：是否被访问过，节点的名称，从这个节点访问到下一个节点的集合 图1 图2 2 算法思路 A 将始点设置为已访问，将其入栈 B 查看栈顶节点V在图中，有没有可以到达、且没有入栈、且没有从这个节点V出发访问过的节点 C 如果有，则将找到的这个节点入栈 D 如果没有，则将节点V访问到下一个节点的集合中每个元素赋值为零，V出栈 E 当栈顶元素为终点时，设置终点没有被访问过，打印栈中元素，弹出栈顶节点 F 重复执行B – E,直到栈中元素为空 Java代码 1. package util; 2. 3. public class Graph { 4. 5. private Vertex vertexList[]; // list of vertices 6. private int adjMat[][]; // adjacency matrix 7. 8. private int nVerts; 9. private static int MAX_VERTS = 7; // n个点 10. 11.int i = 0; 12.int j = 0; 13. 14.public Vertex[] getVertexList() { 15.return vertexList; 16.} 17. 18.public int[][] getAdjMat() { 19.return adjMat; 20.} 21. 22.public int getN() { 23.return MAX_VERTS; 24.} 25. 26.public Graph(int index) { 27.adjMat = new int[MAX_VERTS][MAX_VERTS]; // 邻接矩阵 28.vertexList = new Vertex[MAX_VERTS]; // 顶点数组 29.nVerts = 0; 30. 31.for (i = 0; i < MAX_VERTS; i++) { 32.for (j = 0; j < MAX_VERTS; j++) { 33.adjMat[i][j] = 0; 34.} 35.} 36. 37.addVertex('A'); 38.addVertex('B'); 39.addVertex('C'); 40.addVertex('D'); 41.addVertex('E'); 42.addVertex('F'); 43.addVertex('G'); 44. 45.addEdge(0, 1); 46.addEdge(0, 2); 47.addEdge(1, 4); 48.addEdge(2, 0); 49.addEdge(2, 5); 50.addEdge(3, 0); 51.addEdge(3, 2); 52.addEdge(3, 3); 53.addEdge(4, 1); 54.addEdge(4, 2); 55.addEdge(5, 6); 56.addEdge(6, 3); 57. 58.switch (index) { 59.case 0: 60.break; 61.case 1: 62.delEdge(4, 2); 63.break; 64.default: 65.break; 66.} 67.} 68. 69.private void delEdge(int start, int end) { 70.adjMat[start][end] = 0; 71.} 72....
VIP
