import java.util.LinkedList; import java.util.Queue; public class Graph { /** * @PLA 图的遍历 */ private int num = 9;// 结点数 private boolean[] flag;// 存储结点是否遍历过 private String[] vertexs = { "A", "B", "C", "D", "E", "F", "G", "H", "I" };// 结点 private int[][] edges = { // 邻接矩阵存储边 { 0, 1, 0, 0, 0, 1, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0, 1, 0, 1 }, { 0, 1, 0, 1, 0, 0, 0, 0, 1 }, { 0, 0, 1, 0, 1, 0, 1, 1, 1 }, { 0, 0, 0, 1, 0, 1, 0, 1, 0 }, { 1, 0, 0, 0, 1, 0, 1, 0, 0 }, { 0, 1, 0, 1, 0, 1, 0, 1, 0 }, { 0, 0, 0, 1, 1, 0, 1, 0, 0 }, { 0, 1, 1, 1, 0, 0, 0, 0, 0 } }; // 深度优先遍历,默认选取A为开始遍历结点 void DFSTraverse() { flag = new boolean[num]; for (int i = 0; i < num; i++) { if (flag[i] == false) { DFST(i); } } } private void DFST(int i) { // TODO Auto-generated method stub System.out.println(vertexs[i] + " "); flag[i] = true; for (int j = i; j < num; j++) { if (flag[j] == false && edges[i][j] == 1) { DFST(j); } } } // 广度优先遍历 void BFSTraverse() { flag = new boolean[num]; Queue<Integer> queue = new LinkedList<Integer>(); for (int i = 0; i < num; i++) { if (flag[i] == false) { System.out.println(vertexs[i] + " "); flag[i] = true; queue.add(i); } while (!queue.isEmpty()) { int j = queue.poll(); for (int k = 0; k < num; k++) { if (edges[j][k] == 1 && flag[k] == false) { System.out.println(vertexs[k] + " "); flag[k] = true; queue.add(k); } } } } } public static void main(String[] args) { // TODO Auto-generated method stub Graph graph = new Graph(); System.out.println("图的深度优先遍历:"); graph.DFSTraverse(); System.out.println("图的广度优先遍历"); graph.BFSTraverse(); } }
【上篇】用天平(只能比较,不能称重)从一堆小球中找出其中唯一一个较轻的,使用x 次天平, 最多可以从y 个小球中找出较轻的那个,求y 与x 的关系式。
【下篇】n 支队伍比赛,分别编号为0,1,2……n-1,已知它们之间的实力对比关系,存储在一个二维数组w[n][n]中。。。
【下篇】n 支队伍比赛,分别编号为0,1,2……n-1,已知它们之间的实力对比关系,存储在一个二维数组w[n][n]中。。。