java版无向图的深度优先搜索和连通图的计算
这是本人学习相关算法后,自制的。欢迎大家前来指导学习,代码+详细注释奉上:
package ctong; import java.util.Arrays; import java.util.Random; public class Graph_DFS { /** * Ctong * @param args */ //建立一个标识数组,0表示未被发现的节点,1表示已被发现的节点,2表示邻接表检索完后的节点 private static int[] color; //记录连通图的个数 private static int count = 0; //遍历方法 public void DFS_visit(int[][] array,int n){ //节点n已查找 color[n]=1; System.out.println(Arrays.toString(color)); //从n出发查找与n相连的节点 for(int i = n;i<array.length;i++){ for(int j = 0;j<array.length;j++){ if(array[n][j]==1){ if(color[j]==0){ DFS_visit(array,j); } } } } color[n]=2; System.out.println(Arrays.toString(color)); //以上两次打印color数组是为了显示遍历过程,当某一次打印的数组只有2或0时,表示这里有一个已经查找完毕的连通图 } public Graph_DFS(int[][] graph){ //初始化color数组,表示该无向图的所有节点都没有查找过 for(int i = 0;i<graph.length;i++){ color[i]=0; } //图的遍历 for(int j = 0;j<graph.length;j++){ if(color[j]==0){ //每次执行以下2行代码,表示多出一个连通图 count++; DFS_visit(graph,j); } } } /** * 主函数 */ public static void main(String[] args) { //创建一个1,2,3和4,5,6的环 int[][] map1 = new int[][]{ {0,1,0}, {1,0,0}, {0,0,0}, }; int[][] map = new int[][]{ {0,1,0,0,0,0}, {1,0,0,0,0,0}, {0,0,0,1,0,0}, {0,0,1,0,0,0}, {0,0,0,0,0,1}, {0,0,0,0,1,0}}; //创建随机数组 int[][] map2 = createRandomBArray(); //打印 print(map2); System.out.println("随机创建的2维数组中,行号和列号表示2个节点,它们对应的数据表示它们的连接情况,0表示这两个节点未连通,1表示这两个节点连通"); //0表示未被发现的节点,1表示已被发现的节点,2表示邻接表检索完后的节点 color = new int[map2.length]; System.out.println("无向图的深度优先搜索:"); new Graph_DFS(map2); System.out.println("连通图个数为:"+count); } //创建一个随机的2维数组 private static int[][] createRandomBArray() { Random ra= new Random(); int n = ra.nextInt(5)+4; int[][] Barray= new int[n][n]; for(int k = 0;k<n;k++){ Barray[k][k]=0; } for(int i = 0 ;i<n;i++){ for(int j = 0 ;j<n;j++){ if(i!=j){ if(j>i){ if(Math.random()<0.5) Barray[i][j]= 1; else Barray[i][j]= 0; }else Barray[i][j]=Barray[j][i]; } } } return Barray; } //打印二维数组 public static void print(int[][] c){ for(int i=0;i<c.length;i++ ){ for(int j=0;j<c.length;j++ ){ if(c[i][j]==0) System.out.print(c[i][j]+"\t"); else System.out.print(c[i][j]+"\t"); } System.out.println(); } } }
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1675685
数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历.rar
图数据结构和算法未加权、无向图(隐式边) 深度优先搜索计算从源 s 到目标 t 的可达性。 计算图的连通性(连接的组件)。 图遍历/探索也可用于查找 2 个节点之间的最短路径。 对于真正的大图(如兴趣)不利,因为它...
1)实现图的邻接矩阵和邻接表存储结构; 2)完成基于邻接矩阵的深度优先搜索遍历及广度优先搜索遍历; 3)实现从键盘输入任意一对顶点,求出顶点间的最短路径。
10.6 深度优先搜索 304 10.7 广度优先搜索 313 10.8 添加启发信息 316 10.8.1 爬山搜索 317 10.8.2 爬山搜索的分析 322 10.8.3 最小代价搜索 323 10.8.4 最小代价搜索的分析 324 10.9 查找多个解 324 10.9.1 路径...
2)BFS:该程序包对无向图和无权图具有广度优先搜索算法的实现。 广度优先搜索(BFS)是一种用于遍历或搜索树或图数据结构的算法。 它从树的根(或图的某个任意节点,有时称为“搜索关键字” [1])开始,并探索当前...
图论算法9.1 若干定义9.2 拓扑排序9.3 最短路径算法9.3.1 无权最短路径...深度优先搜索的应用9.6.1 无向图9.6.2 双连通性9.6.3 欧拉回路9.6.4 有向图9.6.5 查找强分支9.7 NP完全性介绍9.7.1 难与易9.7.2 NP类9.7.3 ...
图论算法9.1 若干定义9.2 拓扑排序9.3 最短路径算法9.3.1 无权最短路径...深度优先搜索的应用9.6.1 无向图9.6.2 双连通性9.6.3 欧拉回路9.6.4 有向图9.6.5 查找强分支9.7 NP完全性介绍9.7.1 难与易9.7.2 NP类9.7.3 ...
深度优先搜索和广度优先搜索 参与者: 主持人: 第23章名人问题和无向图表示 参与者: , 主持人: 22 有向图表示 参与者: , , 主持人: 21 AVL 二叉搜索树 参与者: , , 主持人: 20 旋转数组和 3 总和 参与者: , ...
4.1.3 深度优先搜索 338 4.1.4 寻找路径 342 4.1.5 广度优先搜索 344 4.1.6 连通分量 349 4.1.7 符号图 352 4.1.8 总结 358 4.2 有向图 364 4.2.1 术语 364 4.2.2 有向图的数据类型 365 ...
图论算法9.1 若干定义9.2 拓扑排序9.3 最短路径算法9.3.1 无权最短路径...深度优先搜索的应用9.6.1 无向图9.6.2 双连通性9.6.3 欧拉回路9.6.4 有向图9.6.5 查找强分支9.7 NP完全性介绍9.7.1 难与易9.7.2 NP类9.7.3 ...
4.1.3 深度优先搜索 338 4.1.4 寻找路径 342 4.1.5 广度优先搜索 344 4.1.6 连通分量 349 4.1.7 符号图 352 4.1.8 总结 358 4.2 有向图 364 4.2.1 术语 364 4.2.2 有向图的数据类型 365 4.2.3 有向图中的...
4.1.3 深度优先搜索 338 4.1.4 寻找路径 342 4.1.5 广度优先搜索 344 4.1.6 连通分量 349 4.1.7 符号图 352 4.1.8 总结 358 4.2 有向图 364 4.2.1 术语 364 4.2.2 有向图的数据类型 365 4.2.3 有...
9.6 深度优先搜索的应用 9.6.1 无向图 9.6.2 双连通性 9.6.3 欧拉回路 9.6.4 有向图 9.6.5 查找强分支 9.7 NP完全性介绍 9.7.1 难与易 9.7.2 NP类 9.7.3 NP完全问题 小结 练习 参考文献 第10章 算法设计技巧 ...
4.1.3 深度优先搜索 4.1.4 寻找路径 4.1.5 广度优先搜索 4.1.6 连通分量 4.1.7 符号图 4.1.8 总结 4.2 有向图 4.2.1 术语 4.2.2 有向图的数据类型 4.2.3 有向图中的可达性 4.2.4 环和有向无环图 4.2.5 ...
10.6 深度优先搜索 304 10.7 广度优先搜索 313 10.8 添加启发信息 316 10.8.1 爬山搜索 317 10.8.2 爬山搜索的分析 322 10.8.3 最小代价搜索 323 10.8.4 最小代价搜索的分析 324 10.9 查找多个解 324 10.9.1...
9.3.4 无圈图 9.3.5 所有点对最短路径 9.3.6 最短路径的例子 9.4 网络流问题 9.5 最小生成树 9.5.1 prim算法 9.5.2 kruskal算法 9.6 深度优先搜索的应用 9.6.1 无向图 9.6.2 双连通性 9.6.3 ...
9.3.4 无圈图 9.3.5 所有点对最短路径 9.3.6 最短路径的例子 9.4 网络流问题 9.5 最小生成树 9.5.1 prim算法 9.5.2 kruskal算法 9.6 深度优先搜索的应用 9.6.1 无向图 9.6.2 双连通性 9.6.3 ...
无向图、有向图、带权图 选型 帮助文档: 算法 冒泡排序、插入排序、选择排序 归并排序、快速排序 桶排序、计数排序、基数排序 递归 二分查找 广度、深度优先搜索 哈希算法 BF、RK 算法 BM 算法 KMP 算法 Trie 树 AC...