news 2026/2/10 2:22:06

java.有向图邻接表深度优先遍历手写心得

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
java.有向图邻接表深度优先遍历手写心得

基本思路就是:构造一个列表这个列表的每个元素是一个列表,

private List<List<Integer>> arrList;

然后就是为arrList添加列表,和顶点数相同,一定要注意的是不能光写一个for循环,

for (int i=1;i<=total;i++){ arrList.add(new ArrayList<>()); }

要这样写!如下图,在这个构造方法中for循环之前一定要多一步arrList.add(new ArrayList<>());

因为你循环为每个节点加列表的时候,arrList.add默认会从尾部加,也就是说我想跳过arrList[0],只加到索引1~5,是不可能的,系统会默认从索引0开始加所以,只用for循环加列表,实际上是从arrList的索引为0开始加,加到索引为4,最后一个索引5不会拥有一个列表,因此程序会报错。

public youGraphDfs2(int total){ this.total=total; this.arrList=new ArrayList<>(total+1); //total +1 arrList.add(new ArrayList<>()); for (int i=1;i<=total;i++){ arrList.add(new ArrayList<>()); } }

接着就是添加边,邻接表法构造有向图,就是arrList中的每个元素代表一个顶点,顶点又是一个列表,每个顶点的列表存储顶点的邻居顶点,又因为是有向图不需要双向添加,只需要添加一次即可,然后再进行深度优先遍历。

public void addEdge(int i,int j){ arrList.get(i).add(j); //添加用list操作方法,get和add }

深度优先遍历,有两个方法,两个方法的本质是一样的都是递归遍历,其二是封装调用函数。其一:

public void dfs(int start,boolean[] visit){ visit[start]=true; System.out.print("V"+start+" "); //邻接表深度优先是队列形式 for(int neighbor:arrList.get(start)){ if(!visit[neighbor]){ dfs(neighbor,visit); } }

其二:

public void dfs(int start){ boolean[] visit=new boolean[total+1]; dfsUtil(start,visit); } public void dfsUtil(int i,boolean[] visit){ visit[i]=true; System.out.print("V"+i+" "); //!!遍历它所有的邻居节点,就是不断的先遍历第一个列表找到每一个的邻居 for(int neighbor:arrList.get(i)){ if(!visit[neighbor]){ dfsUtil(neighbor,visit); } }

完整代码展示:

package 算法; import java.util.ArrayList; import java.util.List; public class youGraphDfs2 { //链表法写 private int total; private List<List<Integer>> arrList; public youGraphDfs2(int total){ this.total=total; this.arrList=new ArrayList<>(total+1); //total +1 arrList.add(new ArrayList<>()); for (int i=1;i<=total;i++){ arrList.add(new ArrayList<>()); } } public void addEdge(int i,int j){ arrList.get(i).add(j); //添加用list操作方法,get和add } public void dfs(int start,boolean[] visit){ visit[start]=true; System.out.print("V"+start+" "); //邻接表深度优先是队列形式 for(int neighbor:arrList.get(start)){ if(!visit[neighbor]){ dfs(neighbor,visit); } } // public void dfs(int start){ // boolean[] visit=new boolean[total+1]; // dfsUtil(start,visit); // } // public void dfsUtil(int i,boolean[] visit){ // visit[i]=true; // System.out.print("V"+i+" "); // //!!遍历它所有的邻居节点,就是不断的先遍历第一个列表找到每一个的邻居 //// for(int j=1;j<=total;j++){ //// if(arrList.get(i).get()) //// } // //for // for(int neighbor:arrList.get(i)){ // if(!visit[neighbor]){ // dfsUtil(neighbor,visit); // } // } // } public static void main(String[] args) { youGraphDfs2 y=new youGraphDfs2(5); y.addEdge(1, 2); y.addEdge(1, 4); y.addEdge(4, 3); y.addEdge(3, 2); y.addEdge(3, 5); y.addEdge(2, 5); boolean[] visit=new boolean[y.total+1]; y.dfs(1,visit); } }
版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/2/6 21:23:28

3.1 符号主义:基于逻辑的推理系统、知识表示与专家系统

3.1 符号主义&#xff1a;基于逻辑的推理系统、知识表示与专家系统 符号主义&#xff0c;亦称为逻辑主义或“老式人工智能”&#xff0c;是人工智能发展史上第一个形成完整体系并长期占据主导地位的研究范式。其核心假设在于&#xff1a;人类智能&#xff0c;特别是高阶认知功…

作者头像 李华
网站建设 2026/2/6 8:45:01

企业选对会议服务商:7个关键维度避坑指南

企业选对会议服务商&#xff1a;7个关键维度避坑指南 在数字化转型浪潮下&#xff0c;会议活动已从简单的场地与人员组织&#xff0c;演变为一个集技术集成、创意策划与精准执行于一体的复杂系统工程。企业选择会议服务商&#xff0c;实质上是选择一位能够驾驭技术变革、保障活…

作者头像 李华
网站建设 2026/2/6 23:32:16

泰克示波器 4 系列 MSO 在嵌入式开发中的实测分析

嵌入式系统广泛应用于消费电子、工业控制、汽车电子等领域。嵌入式开发人员需要面对复杂的硬件电路、复杂的软件代码以及各种通信协议。泰克 4 系列 MSO 结合了示波器、逻辑分析仪、协议分析仪等多种功能&#xff0c;可以帮助开发人员快速定位问题、验证设计并优化性能。泰克 4…

作者头像 李华
网站建设 2026/2/9 5:21:04

LCR测试仪温度漂移补偿的解决方案

LCR测试仪是电子测量中重要的仪器&#xff0c;广泛应用于元器件的参数测试&#xff0c;如电感&#xff08;L&#xff09;、电容&#xff08;C&#xff09;和电阻&#xff08;R&#xff09;。然而&#xff0c;温度变化会导致待测元件参数的漂移&#xff0c;进而影响测试结果的准…

作者头像 李华
网站建设 2026/2/7 20:43:25

C++医学图像处理经典ITK库用法详解<四>: 图像分割模块功能

1、ITK库概述ITK (Insight Segmentation and Registration Toolkit) 是一个开源的跨平台软件开发工具包&#xff0c;主要用于图像处理&#xff0c;特别是生物医学图像处理领域。该工具包提供了一套丰富的图像处理算法&#xff0c;特别是在图像分割和配准方面具有强大的功能。IT…

作者头像 李华
网站建设 2026/2/2 23:35:03

C++医学图像处理经典ITK库用法详解<五>: 数学运算与变换模块功能

1、ITK库概述ITK (Insight Segmentation and Registration Toolkit) 是一个开源的跨平台软件开发工具包&#xff0c;主要用于图像处理&#xff0c;特别是生物医学图像处理领域。该工具包提供了一套丰富的图像处理算法&#xff0c;特别是在图像分割和配准方面具有强大的功能。IT…

作者头像 李华