目录
图的遍历,即将图内所有顶点都访问一遍。
有两种遍历方式:
以下图的遍历为例:

DFS(depth first search),深度优先搜索,先跑到叶节点,沿着原路返回,沿途遍历其他节点。
代码示例:
- public class DFS {
- //图
- static int[][] graph=new int[7][7];
- //访问记录
- static boolean[] isVisited=new boolean[7];
- static {
- graph[0][1]=1;graph[0][2]=1;graph[0][3]=1;
- graph[1][0]=1;graph[1][2]=1;
- graph[2][0]=1;graph[2][1]=1;graph[2][3]=1;graph[2][4]=1;graph[2][5]=1;
- graph[3][0]=1;graph[3][2]=1;graph[3][4]=1;
- graph[4][2]=1;graph[4][3]=1;
- graph[5][2]=1;
- graph[5][6]=1;
- graph[6][5]=1;
- }
-
- public static void DFS(int i){
- System.out.println(i);
- isVisited[i]=true;
- for(int j=0;j
- if(graph[i][j]==1&&isVisited[j]==false){
- DFS(j);
- }
- }
- }
-
- public static void main(String[] args) {
- DFS(0);
- }
- }
11.3.BFS
BFS(Breadth first search),广度优先搜索,先遍历一度关系(直接相连),再遍历二度关系(直接相连的直接相连),再遍历三度关系(直接相连的直接相连的直接相连)……直到遍历完整个图。过程类似于树的层序遍历。
- public class BFS {
- //图
- static int[][] graph=new int[7][7];
- //访问记录
- static boolean[] isVisited=new boolean[7];
- //队列
- static LinkedList
queue=new LinkedList(); - static {
- graph[0][1]=1;graph[0][2]=1;graph[0][3]=1;
- graph[1][0]=1;graph[1][2]=1;
- graph[2][0]=1;graph[2][1]=1;graph[2][3]=1;graph[2][4]=1;graph[2][5]=1;
- graph[3][0]=1;graph[3][2]=1;graph[3][4]=1;
- graph[4][2]=1;graph[4][3]=1;
- graph[5][2]=1;
- graph[5][6]=1;
- graph[6][5]=1;
- }
-
- public static void BFS(){
- while(!queue.isEmpty()){
- int i=queue.poll();
- System.out.println("出队:"+i);
- isVisited[i]=true;
- for(int j=0;j
- if(graph[i][j]==1&&isVisited[j]==false) {
- System.out.println("入队:"+j);
- isVisited[j]=true;
- queue.offer(j);
- }
- }
- }
- }
-
- public static void main(String[] args) {
- queue.offer(0);
- BFS();
- }
- }
-
相关阅读:
【数字电路基础】STA(Static Timing Analysis)静态时序分析-详细版
大二数据结构实验(排序算法)
Python eval() 函数
从零开始封装 vue 组件
完美世界服务端设置小技巧
IMU预积分再理解
Python 字典类型拓展(包括 MappingProxyType 只读字典, defaultdict 缺省字典和 ChainMap)
【爬虫】第五部分 selenium库
上海计算机学会 2024年4月月赛 丙组T3 交换的次数
Linux实操篇-定时任务调度
-
原文地址:https://blog.csdn.net/Joker_ZJN/article/details/128176476