图遍历算法

news/2024/4/19 14:43:55/文章来源:https://blog.csdn.net/qq_62525547/article/details/136549041

        图的遍历算法有两种:深度优先遍历、广度优先遍历算法。

        深度优先遍历算法就是从起始结点开始,只要有相邻且未被访问的结点就要直接进行访问,直到最后不能向下遍历为止,再回溯寻找下一个策略。

        广度优先遍历算法,就是从起点开始向下一层一层的进行遍历,直到最后没有结点。

一、图的结点和边的相关类定义

        顶点:

package graph;import java.util.List;/*** 顶点类*/
public class Vertex {String name;List<Edge> edges;boolean flag;//是否被访问过int inDegree;//结点的入度public Vertex() {}public Vertex(String name, List<Edge> edges) {this.name = name;this.edges = edges;}public Vertex(String name) {this.name = name;}public String getName() {return name;}public void setName(String name) {this.name = name;}public List<Edge> getEdges() {return edges;}public void setEdges(List<Edge> edges) {this.edges = edges;}
}

        边:

package graph;/*** 边类*/
public class Edge {Vertex vertex;int weight;public Edge() {}public Edge(Vertex vertex) {this.vertex = vertex;}public Edge(Vertex vertex, int weight) {this.vertex = vertex;this.weight = weight;}public Vertex getVertex() {return vertex;}public void setVertex(Vertex vertex) {this.vertex = vertex;}public int getWeight() {return weight;}public void setWeight(int weight) {this.weight = weight;}
}

  二、深度优先遍历算法

package graph;import java.util.LinkedList;
import java.util.List;public class DFS {public static void main(String[] args) {Vertex v1=new Vertex("v1",new LinkedList<>());Vertex v2=new Vertex("v2",new LinkedList<>());Vertex v3=new Vertex("v3",new LinkedList<>());Vertex v4=new Vertex("v4",new LinkedList<>());Vertex v5=new Vertex("v5",new LinkedList<>());Vertex v6=new Vertex("v6",new LinkedList<>());v1.edges.add(new Edge(v3,9));v1.edges.add(new Edge(v2,7));v1.edges.add(new Edge(v6,14));v2.edges.add(new Edge(v4,15));v3.edges.add(new Edge(v4,11));v3.edges.add(new Edge(v6,2));v4.edges.add(new Edge(v5,6));v6.edges.add(new Edge(v5,9));//        dfs(v1);dfs2(v1);}//递归方式从一个结点开始深度遍历整个图public static void dfs(Vertex v){v.flag=true;System.out.println(v.name);for(Edge edge:v.edges){if(!edge.vertex.flag){dfs(edge.vertex);}}}//非递归方式从一个结点开始深度遍历整个图public static void dfs2(Vertex vertex){LinkedList<Vertex> stack=new LinkedList<>();stack.push(vertex);while (!stack.isEmpty()){Vertex pop = stack.pop();pop.flag=true;System.out.println(pop.name);for (Edge edge : pop.edges) {if(!edge.vertex.flag){stack.push(edge.vertex);}}}}
}

三、广度优先遍历算法

package graph;import java.util.LinkedList;
import java.util.List;public class BFS {public static void main(String[] args) {Vertex v1=new Vertex("v1",new LinkedList<>());Vertex v2=new Vertex("v2",new LinkedList<>());Vertex v3=new Vertex("v3",new LinkedList<>());Vertex v4=new Vertex("v4",new LinkedList<>());Vertex v5=new Vertex("v5",new LinkedList<>());Vertex v6=new Vertex("v6",new LinkedList<>());v1.edges.add(new Edge(v3,9));v1.edges.add(new Edge(v2,7));v1.edges.add(new Edge(v6,14));v2.edges.add(new Edge(v4,15));v3.edges.add(new Edge(v4,11));v3.edges.add(new Edge(v6,2));v4.edges.add(new Edge(v5,6));v6.edges.add(new Edge(v5,9));bfs(v1);}public static void bfs(Vertex vertex){LinkedList<Vertex> queue=new LinkedList<>();queue.offer(vertex);vertex.flag=true;while (!queue.isEmpty()){Vertex poll = queue.poll();System.out.println(poll.name);for (Edge edge : poll.edges) {if(!edge.vertex.flag){edge.vertex.flag=true;queue.offer(edge.vertex);}}}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_997524.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

面试经典150题——环形链表

Suffering, for the weak is the tomb of death, and for the strong is the soil of germinal ambition.​ 1. 题目描述 2. 题目分析与解析 2.1 思路一 这个题目就是判断一个链表有没有环&#xff0c;其实我们之讲过一个题目&#xff0c;就实现了判断链表有没有环的步骤&a…

spring boot集成neo4j实现简单的知识图谱

一、neo4j介绍 随着社交、电商、金融、零售、物联网等行业的快速发展&#xff0c;现实社会织起了了一张庞大而复杂的关系网&#xff0c;传统数据库很难处理关系运算。大数据行业需要处理的数据之间的关系随数据量呈几何级数增长&#xff0c;急需一种支持海量复杂数据关系运算的…

九:多播和广播

1 多播 &emsp 多播(Multicast )方式的数据传输是基于UDP完成的。 因此&#xff0c;与UDP服务器端/客户端的实现方式非常接近。 区别在于&#xff0c; UDP数据传输以单一目标进行&#xff0c;而多播数据同时传递到加入(注册)特定组的大量主机。 换言之&#xff0c;采用多播…

DFT应用:计算线性卷积

目录 一、计算两个有限长序列的线性卷积示例 二、无限长序列和有限长序列的卷积(重叠相加法) 实验1&#xff1a;数据实验 实验2&#xff1a;纯净语音加混响(音效) 二、无限长序列和有限长序列的卷积(重叠保留法) 实验1&#xff1a;数据实验 三、小结 一、计算两个有限长序…

[⑥5G NR]: 无线接口协议,信道映射学习

5G系统整体包括核心网、接入网以及终端部分&#xff0c;接入网与终端间通过无线空口协议栈进行连接。无线接口可分为三个协议层&#xff1a;物理层&#xff08;L1&#xff09;、数据链路层&#xff08;L2&#xff09;和网络层&#xff08;L3&#xff09;。 L1&#xff1a;物理…

利用OpenCV 抽取视频的图片,并制作目标检测数据集

1、前言 目标检测中&#xff0c;图片的数据可以从视频中抽取&#xff0c;而OpenCV的VideoCapture可以实现这样的操作 需要的库文件 opencv pip下载&#xff1a; pip install opencv-contrib-python 更换镜像源下载&#xff1a; pip install opencv-contrib-python -i htt…

Linux 理解操作系统

目录 一、冯诺依曼体系结构 二、操作系统 1、概念 2、设计OS的目的 3、定位 4、先描述再组织 5、系统调用和库函数概念 一、冯诺依曼体系结构 计算机&#xff0c;都是有一个个的硬件组件组成&#xff1a; 输入单元&#xff1a;包括键盘, 鼠标&#xff0c;扫描仪, 写板等…

寻找旋转排序数组中的最小值[中等]

优质博文IT-BLOG-CN 一、题目 已知一个长度为n的数组&#xff0c;预先按照升序排列&#xff0c;经由1到n次 旋转 后&#xff0c;得到输入数组。例如&#xff0c;原数组nums [0,1,2,4,5,6,7]在变化后可能得到&#xff1a; 【1】若旋转4次&#xff0c;则可以得到[4,5,6,7,0,1,2…

Flink ExecuteGraph构建源码解析

文章目录 前言ExecutionGraph中的主要抽象概念源码核心代码入口源码核心流程&#xff1a; 前言 在JobGraph构建过程中分析了JobGraph的构建过程&#xff0c;本文分析ExecutionGraph的构建过程。JobManager(JobMaster) 根据 JobGraph 生成 ExecutionGraph。ExecutionGraph是JobG…

C++前置声明的学习

【C】C中前置声明的应用与陷阱_前置生命如何使用-CSDN博客 首先&#xff0c;这样写会报错&#xff1a; #pragma once #include "A.h" class B {A a; public:B(void);~B(void); };#include "B.h" B::B(void) { }B::~B(void) { } #pragma once #include &…

URL?后参数有特殊字符问题

前端对于URL的参数不做处理 不处理、用URLDecoder.decode()处理、用URLEncoder.encode()处理、用URLEncoder.encode()处理后再用URLDecoder.decode()处理 结果 前端对于URL的参数用encodeURIComponent(‘XF-OPPZZD-26*316’)处理 结果 前端不处理有&字符时 结果会把后…

前端网络请求异步处理——Promise使用记录

Promise是ES6中新增的一个处理复杂异步请求的工具&#xff0c;其主要形式为&#xff1a; const baseUrl http://localhost:80 export const $request (param {}) > {console.log(请求参数, param)return new Promise((resolve, reject) > {wx.request({url: baseUrl …

海外服务器被DDOS攻击了该怎么办

在当今全球化的时代&#xff0c;越来越多的企业和组织选择将业务拓展至海外市场。然而&#xff0c;随着业务的扩大和网络的延伸&#xff0c;也面临着来自不同地区的网络威胁和攻击风险。如果您的海外服务器遭受了DDOS攻击&#xff0c;以下是一些应对措施&#xff1a; 一、立即断…

【Redis】Redis的应用场景

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;Redis ⛺️稳中求进&#xff0c;晒太阳 Redis的应用场景&#xff1a; 限流 要求10s内只能访问一次 RequestMapping("xian")public String xianLiu(String sign){String sign1 …

力扣刷题

文章目录 1. 双指针1.1 两数之和1.2 三数之和1.3 盛最多水的容器1.4 接雨水 2. 字串2.1 滑动窗口最大值 3. 动态规划4. 多维动态规划4.1 最长回文字串 1. 双指针 1.1 两数之和 思路&#xff1a;因为是有序数组&#xff0c; 1.2 三数之和 题目要求不能重复 思路&#xff1a;三…

简明固体物理--晶体的形成与晶体结构的描述

简明固体物理-国防科技大学 chapter 1 Formation of Crystal Contents and roadmapQuantum Mechanics and atomic structureElectronsOld quantum theoryMethod of Quantum MechanicsDistributing functions of micro-particles BindingCrystal structure and typical crystal…

YOLOv9(2):YOLOv9网络结构

1. 前言 本文仅以官方提供的yolov9.yaml来进行简要讲解。 讲解之前&#xff0c;还是要做一些简单的铺垫。 Slice层不做任何的操作&#xff0c;纯粹是做一个占位层。这样一来&#xff0c;在parse_model时&#xff0c;ch[n]可表示第n层的输出通道。 Detect和DDetect主要区别还…

Java开发从入门到精通(一):Java的基础语法进阶

Java大数据开发和安全开发 &#xff08;一&#xff09;Java注释符1.1 单行注释 //1.2 多行注释 /* */1.3 文档注释 /** */1.4 各种注释区别1.5 注释的特点1.5 注释的快捷键 &#xff08;二&#xff09;Java的字面量&#xff08;三&#xff09;Java的变量3.1 认识变量3.2 为什么…

例行性工作(at,crontab)

目录 单一执行的例行性工作at 语法 选项 时间格式 at的工作文件存放目录 at工作的日志文件 实例 命令总结&#xff1a; 循环执行的例行性工作crond 语法 选项 crontab工作调度对应的系统服务 crontab工作的日志文件 用户定义计划任务的文件所在目录 动态查看 crontab文件格式 文…

集合拆分Lists.partition的使用

集合拆分Lists.partition的使用 集合拆分Lists.partition的使用 需要的包 import com.google.common.collect.Lists;引入maven依赖 <dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>21.0</…