• 数据结构(11)图的遍历,DFS、BFS的JAVA实现


     

    目录

     

    11.1.图的遍历

    11.2.DFS

    11.3.BFS


    11.1.图的遍历

    图的遍历,即将图内所有顶点都访问一遍。

    有两种遍历方式:

    • BFS
    • DFS

    以下图的遍历为例:

    11.2.DFS

    DFS(depth first search),深度优先搜索,先跑到叶节点,沿着原路返回,沿途遍历其他节点。

    代码示例:

    1. public class DFS {
    2. //图
    3. static int[][] graph=new int[7][7];
    4. //访问记录
    5. static boolean[] isVisited=new boolean[7];
    6. static {
    7. graph[0][1]=1;graph[0][2]=1;graph[0][3]=1;
    8. graph[1][0]=1;graph[1][2]=1;
    9. graph[2][0]=1;graph[2][1]=1;graph[2][3]=1;graph[2][4]=1;graph[2][5]=1;
    10. graph[3][0]=1;graph[3][2]=1;graph[3][4]=1;
    11. graph[4][2]=1;graph[4][3]=1;
    12. graph[5][2]=1;
    13. graph[5][6]=1;
    14. graph[6][5]=1;
    15. }
    16. public static void DFS(int i){
    17. System.out.println(i);
    18. isVisited[i]=true;
    19. for(int j=0;j
    20. if(graph[i][j]==1&&isVisited[j]==false){
    21. DFS(j);
    22. }
    23. }
    24. }
    25. public static void main(String[] args) {
    26. DFS(0);
    27. }
    28. }

    11.3.BFS

    BFS(Breadth first search),广度优先搜索,先遍历一度关系(直接相连),再遍历二度关系(直接相连的直接相连),再遍历三度关系(直接相连的直接相连的直接相连)……直到遍历完整个图。过程类似于树的层序遍历。

    1. public class BFS {
    2. //图
    3. static int[][] graph=new int[7][7];
    4. //访问记录
    5. static boolean[] isVisited=new boolean[7];
    6. //队列
    7. static LinkedList queue=new LinkedList();
    8. static {
    9. graph[0][1]=1;graph[0][2]=1;graph[0][3]=1;
    10. graph[1][0]=1;graph[1][2]=1;
    11. graph[2][0]=1;graph[2][1]=1;graph[2][3]=1;graph[2][4]=1;graph[2][5]=1;
    12. graph[3][0]=1;graph[3][2]=1;graph[3][4]=1;
    13. graph[4][2]=1;graph[4][3]=1;
    14. graph[5][2]=1;
    15. graph[5][6]=1;
    16. graph[6][5]=1;
    17. }
    18. public static void BFS(){
    19. while(!queue.isEmpty()){
    20. int i=queue.poll();
    21. System.out.println("出队:"+i);
    22. isVisited[i]=true;
    23. for(int j=0;j
    24. if(graph[i][j]==1&&isVisited[j]==false) {
    25. System.out.println("入队:"+j);
    26. isVisited[j]=true;
    27. queue.offer(j);
    28. }
    29. }
    30. }
    31. }
    32. public static void main(String[] args) {
    33. queue.offer(0);
    34. BFS();
    35. }
    36. }

  • 相关阅读:
    element-ui 切换分页条数,触发两次请求-bug记录, 分页组件封装
    分布式搜索引擎01
    第73步 时间序列建模实战:多步滚动预测 vol-1(以决策树回归为例)
    proto转java类时相关option配置
    设计模式-创建型模式-工厂方法模式
    Java高级学习篇之网络编程
    mac安装python虚拟环境
    SQL Server端口配置指南
    2023扬州大学计算机考研信息汇总
    DockerFile的使用
  • 原文地址:https://blog.csdn.net/Joker_ZJN/article/details/128176476