Java算法之图的遍历(邻接矩阵)
发布时间:2020-12-14 23:50:42 所属栏目:Java 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 import java.util.LinkedList;import java.util.Queue;// 图的遍历public class Graph { // 邻接矩阵存储图 // --A B C D E F G H I // A 0 1 0 0 0 1
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考 import java.util.LinkedList; import java.util.Queue; // 图的遍历 public class Graph { // 邻接矩阵存储图 // --A B C D E F G H I // A 0 1 0 0 0 1 1 0 0 // B 1 0 1 0 0 0 1 0 1 // C 0 1 0 1 0 0 0 0 1 // D 0 0 1 0 1 0 1 1 1 // E 0 0 0 1 0 1 0 1 0 // F 1 0 0 0 1 0 1 0 0 // G 0 1 0 1 0 1 0 1 0 // H 0 0 0 1 1 0 1 0 0 // I 0 1 1 1 0 0 0 0 0 // 顶点数 private int number = 9; // 记录顶点是否被访问 private boolean[] flag; // 顶点 private String[] vertexs = { "A","B","C","D","E","F","G","H","I" }; // 边 private int[][] edges = { { 0,1,0 },{ 1,1 },{ 0,0 } }; // 图的深度遍历操作(递归) void DFSTraverse() { flag = new boolean[number]; for (int i = 0; i < number; i++) { if (flag[i] == false) {// 当前顶点没有被访问 DFS(i); } } } // 图的深度优先递归算法 void DFS(int i) { flag[i] = true;// 第i个顶点被访问 System.out.print(vertexs[i] + " "); for (int j = 0; j < number; j++) { if (flag[j] == false && edges[i][j] == 1) { DFS(j); } } } // 图的广度遍历操作 void BFSTraverse() { flag = new boolean[number]; Queue<Integer> queue = new LinkedList<Integer>(); for (int i = 0; i < number; i++) { if (flag[i] == false) { flag[i] = true; System.out.print(vertexs[i] + " "); queue.add(i); while (!queue.isEmpty()) { int j = queue.poll(); for (int k = 0; k < number; k++) { if (edges[j][k] == 1 && flag[k] == false) { flag[k] = true; System.out.print(vertexs[k] + " "); queue.add(k); } } } } } } // 测试 public static void main(String[] args) { Graph graph = new Graph(); System.out.println("图的深度遍历操作(递归):"); graph.DFSTraverse(); System.out.println("n-------------"); System.out.println("图的广度遍历操作:"); graph.BFSTraverse(); } } 图的深度遍历操作(递归): A B C D E F G H I ------------- 图的广度遍历操作: A B F G C I E D H 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |