【算法基础实验】图论-基于DFS的连通性检测

基于DFS的连通性检测

理论基础

在图论中,连通分量是无向图的一个重要概念,特别是在处理图的结构和解析图的组成时。连通分组件表示图中的一个子图,在这个子图中任意两个顶点都是连通的,即存在一条路径可以从一个顶点到达另一个顶点,并且这个子图是最大的,即不能通过添加更多的顶点来增加连通性。对于有向图,这通常被称为强连通分量。

基于DFS的连通分量算法

书中4.1.6节提到的基于深度优先搜索(DFS)的连通分量算法用于识别和处理无向图中的连通分量。这个算法的基本思想是使用DFS遍历图中的每个顶点,同时记录哪些顶点是连通的。

算法步骤

  1. 初始化:为每个顶点准备一个标记数组 marked[] 来记录每个顶点是否被访问过,另外用一个数组 id[] 来记录每个顶点所属的连通分量的标识符。还需要一个计数器 count 来统计连通分量的数量。
  2. DFS遍历:从任意未被访问的顶点开始,执行DFS遍历。在遍历过程中,标记所有可达的顶点为已访问,同时将这些顶点的 id[] 设置为当前的连通分量标识符。
  3. 连通分量标识:每次在DFS遍历开始前增加连通分量计数器 count,并将遍历过程中访问的所有顶点的连通分量标识设置为这个计数器的值。
  4. 重复执行:重复上述过程,直到图中的所有顶点都被访问过。

应用

  • 图的结构分析:识别图中的独立部分或者紧密相关的群组。
  • 网络设计:确定网络中的独立组件,以优化设计和提高稳定性。
  • 社交网络:识别社交网络中的社区或者群组。

通过这种基于DFS的连通分量算法,可以有效地解析和处理图的结构,对于复杂网络的分析尤其有用。

数据结构

private boolean[] marked
private int[] id
private int count
myBag
myGraph

实验数据和算法流程

这里使用tinyG.txt来构成实验用的无向图

注意算法流程中count,marked[],id[]的变化

请添加图片描述

代码实现

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;public class myCC {private boolean[] marked;private int[] id;private int count;public myCC(myGraph G){marked = new boolean[G.V()];id = new int[G.V()];for(int s=0;s<G.V();s++){if(!marked[s]){dfs(G,s);//这里是精髓所在,每次dfs回到这里就说明互相连通的一组顶点已经完成遍历,//也就确定了一个连通分量count++;                }}}private void dfs(myGraph G, int v){marked[v] = true;id[v] = count;for(int w:G.adj(v)){if(!marked[w]){dfs(G,w);}}}public boolean connected(int v, int w){return id[v]==id[w];}public int id(int v){return id[v];}public int count(){return count;}public static void main(String[] args){myGraph G = new myGraph(new In(args[0]));myCC cc = new myCC(G);int M = cc.count();StdOut.println(M + " components");myBag<Integer>[] components = (myBag<Integer>[]) new myBag[M];for(int i=0;i<M;i++){components[i] = new myBag<Integer>();}for(int v=0;v<G.V();v++){components[cc.id(v)].add(v);}for(int i=0;i<M;i++){for(int v:components[i]) StdOut.print(v+" ");StdOut.println();}}
}

代码详解

这段代码实现了一个基于深度优先搜索(DFS)的连通分量(CC)类 myCC,用于确定无向图中所有的连通分量。下面是详细的代码解释:

类定义和变量


public class myCC {private boolean[] marked;  // 标记数组,用于标记每个顶点是否已经被访问过private int[] id;          // 每个顶点所属的连通分量标识private int count;         // 连通分量的数量
  • marked 数组用于记录图中的每个顶点是否已经被访问。
  • id 数组用于存储每个顶点所属的连通分量的ID。
  • count 用于计数图中连通分量的总数。

构造函数


public myCC(myGraph G){marked = new boolean[G.V()];id = new int[G.V()];for(int s = 0; s < G.V(); s++) {if (!marked[s]) {dfs(G, s);count++;  // 完成一个连通分量的搜索后,增加连通分量的计数}}
}

构造函数遍历图中的所有顶点,对于每个未标记的顶点,执行DFS来标记和记录所有能从该顶点访问到的顶点,这些顶点构成一个连通分量。每次DFS调用结束后,连通分量数 count 加一。

DFS 方法


private void dfs(myGraph G, int v){marked[v] = true;id[v] = count;for (int w : G.adj(v)) {if (!marked[w]) {dfs(G, w);}}
}

dfs 方法标记顶点 v 为已访问,并将其连通分量ID设置为当前的 count。然后递归地访问所有与顶点 v 直接相连的未标记顶点。

连通分量的辅助方法


public boolean connected(int v, int w) { return id[v] == id[w]; }
public int id(int v) { return id[v]; }
public int count() { return count; }

这些方法提供了:

  • connected(v, w) 检查两个顶点是否属于同一个连通分量。
  • id(v) 返回顶点 v 的连通分量ID。
  • count() 返回图中连通分量的总数。

主方法


public static void main(String[] args){myGraph G = new myGraph(new In(args[0]));myCC cc = new myCC(G);int M = cc.count();StdOut.println(M + " components");myBag<Integer>[] components = (myBag<Integer>[]) new myBag[M];for (int i = 0; i < M; i++) {components[i] = new myBag<Integer>();}for (int v = 0; v < G.V(); v++) {components[cc.id(v)].add(v);}for (int i = 0; i < M; i++) {for (int v : components[i]) StdOut.print(v + " ");StdOut.println();}
}

主方法使用 myCC 类来处理一个从文件读取的图,并输出所有的连通分量。这里,连通分量被存储在一个 myBag 数组中,每个 myBag 对象存储一个连通分量的所有顶点,然后输出每个连通分量的顶点。

这段代码是一个完整的图连通分量识别实现,使用DFS作为基本的遍历策略。

实验

代码编译

javac myCC.java

运行代码

将实验数据tinyG.txt导入代码后,myCC可以检测到3个连通分量,并逐行将连通分量中的元素打印出来

java myCC ..\data\tinyG.txt               
3 components
6 5 4 3 2 1 0
8 7
12 11 10 9

参考资料

算法(第4版)人民邮电出版社

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

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

相关文章

【Webgl_glslThreejs】搬运分享shader_飘落心形

来源网站 https://www.shadertoy.com/view/4sccWr效果预览 代码演示 将shadertory上的代码转成了threejs可以直接用的代码&#xff0c;引入文件的material&#xff0c;并在创建mesh或已有物体上使用material即可&#xff0c;使用时请注意uv对齐。 import { DoubleSide, Shad…

深度学习从入门到精通—Transformer

1.绪论介绍 1.1 传统的RNN网络 传统的RNN&#xff08;递归神经网络&#xff09;主要存在以下几个问题&#xff1a; 梯度消失和梯度爆炸&#xff1a;这是RNN最主要的问题。由于序列的长距离依赖&#xff0c;当错误通过层传播时&#xff0c;梯度可以变得非常小&#xff08;消失…

(MSFT.O)微软2024财年Q3营收619亿美元

在科技的浩渺宇宙中&#xff0c;一颗璀璨星辰再度闪耀其光芒——(MSFT.O)微软公司于2024财政年度第三季展现出惊人的财务表现&#xff0c;实现总营业收入达到令人咋舌的6190亿美元。这一辉煌成就不仅突显了微软作为全球技术领导者之一的地位&#xff0c;更引发了业界内外对这家…

第十五届蓝桥杯题解-数字接龙

题意&#xff1a;经过所有格子&#xff0c;并且不能进行交叉&#xff0c;走的下一个格子必须是当前格子值1%k&#xff0c;输出路径最小的那一条&#xff08;有8个方向&#xff0c;一会粘图&#xff09; 思路&#xff1a;按照8个方向设置偏移量进行dfs&#xff0c;第一个到达终…

C/C++ 入门(7)string类(STL)

个人主页&#xff1a;仍有未知等待探索-CSDN博客 专题分栏&#xff1a;C 请多多指教&#xff01; 目录 一、标准库中的string 1、了解 2、string类常用接口说明 1、常见的构造函数 2、容量操作 ​编辑 3、访问及遍历操作 4、修改操作 5、非成员函数 二、string类实现 …

LeetCode57. 插入区间

LeetCode57.插入区间 题目思路: 代码 /* 前置知识&#xff1a; vector<vector<int>> a,b; 二维vector数组是可以将二维中的一维vector数组给push_back的&#xff0c; 不是只有单个元素才可以&#xff0c;整个一维的vector数组也可以 b[0] {1,2,3},b[1] {4,5,6}…

【AIGC调研系列】大型语言模型如何减少幻觉生成

在解读大型语言模型&#xff08;LLMs&#xff09;中的长格式事实性问题时&#xff0c;我们首先需要认识到这些模型在生成内容时可能会产生与既定事实不一致的情况&#xff0c;这种情况通常被称为“幻觉”[2][3]。这种现象不仅可能导致信息的误传&#xff0c;还可能对社会造成误…

封装 H.264 视频为 FLV 格式然后推流

封装 H.264 视频为 FLV 格式并通过 RTMP 推流 flyfish 协议 RTMP (Real-Time Messaging Protocol) RTSP (Real Time Streaming Protocol) SRT (Secure Reliable Transport) WebRTC RTMP&#xff08;Real Time Messaging Protocol&#xff09;是一种用于实时音视频流传输的协…

indexDB 大图缓存

背景 最近在项目中遇到了一个问题&#xff1a;由于大屏背景图加载速度过慢&#xff0c;导致页面黑屏时间过长&#xff0c;影响了用户的体验。从下图可以看出加载耗时将近一分钟 IndexDB 主要的想法就是利用indexDB去做缓存&#xff0c;优化加载速度&#xff1b;在这之前&am…

C语言——内存函数的实现与模拟

1. memcpy 函数 与strcpy 函数类似 1.头文件 <string.h> 2.基本格式 • 函数memcpy从source的位置开始向后复制num个 字节 的数据到destination指向的内存位置。 • 这个函数在遇到 \0 的时候并不会停下来。 • 如果source和destination有任何的重叠&#xff0…

C# WinForm —— 10 单选按钮与复选框的介绍与使用

单选按钮 RadioButton 一组单选按钮中&#xff0c;只能选择一个&#xff0c;互相排斥 常用属性、事件&#xff1a; 属性用途(Name)单选按钮的ID&#xff0c;在代码里引用的时候会用到,一般以 rb开头Text单选按钮旁边显示的 文本信息Checked单选按钮的勾选状态Appearance控制单…

SpringCloud系列(18)--将服务提供者Provider注册进Consul

前言&#xff1a;在上一章节中我们把服务消费者Consumer注册进了Zookeeper&#xff0c;并且成功通过服务消费者Consumer调用了服务提供者Provider&#xff0c;而本章节则是关于如何将服务提供者Provider注册进Consul里 准备环境&#xff1a; 先安装Consul&#xff0c;如果没有…

【OceanBase诊断调优】—— 4013 内存爆问题的排查

本文介绍 4013 内存爆问题的排查。 内存爆的类型 内存爆主要分为五类&#xff0c;可以通过关键词 OOPS 确定内存爆的类型。 内存爆的类型日志信息&#xff08;关键字为 [OOPS]&#xff09;SINGLE_ALLOC_SIZE_OVERFLOWsingle alloc size large than 4G is not allowed(alloc_…

vue项目使用百度地图

打开百度地图开放平台 百度地图开放平台 | 百度地图API SDK | 地图开发 在控制台新建应用 复制访问应用的ak 可修改地图样式 使用部分 <!-- 引入地图 --><div class"main-aside"><div id"b-map-container"></div></div> …

案例-部门管理-删除

黑马程序员JavaWeb开发教程 文章目录 一、查看页面原型二、查看接口文档三、开发1、Controller2、Service&#xff08;1&#xff09;service接口层&#xff08;3&#xff09;service实现层 3、Mapper4、Postman 一、查看页面原型 二、查看接口文档 三、开发 1、Controller 因…

SpringWebFlux RequestBody多出双引号问题——ProxyPin抓包揪出真凶

缘起 公司有个服务做埋点收集的&#xff0c;可以参考我之前的文章埋点日志最终解决方案&#xff0c;今天突然发现有些数据日志可以输出&#xff0c;但是没法入库。 多出的双引号 查看Flink日志发现了JSON解析失败&#xff0c;Flink是从Kafka拿数据&#xff0c;Kafka本身不处…

Magnet for Mac:高效窗口管理工具

Magnet for Mac是一款专为Mac用户设计的窗口管理工具&#xff0c;旨在帮助用户更高效地管理和布局多个应用程序窗口&#xff0c;提升工作效率。 Magnet for Mac v2.14.0中文免激活版下载 这款软件拥有直观易用的界面和丰富的功能&#xff0c;支持用户将屏幕分割成多个区域&…

【漏洞分析】浅析android手游lua脚本的加密与解密(一)

主要用到的工具和环境&#xff1a; 1 win7系统一枚 2 quick-cocos2d-x的开发环境&#xff08;弄一个开发环境方便学习&#xff0c;而且大部分lua手游都是用的cocos2d-x框架&#xff0c;还有一个好处&#xff0c;可以查看源码关键函数中的特征字符串&#xff0c;然后在IDA定位到…

Electron中使用Prisma(以SQLite为例)

1、安装 Prisma 打开终端&#xff0c;执行以下命令安装 Prisma CLI&#xff1a; npm install prisma -g 2、初始化 Prisma 项目 在工作目录中执行以下命令来初始化一个新的 Prisma 项目&#xff1a; prisma init 这将创建一个新的文件夹&#xff0c;包含了必要的文件和目…

vue echarts折线图 折线堆积图和折线面积图

vue echarts折线图 折线堆积图和折线面积图 1、折线堆积图和折线面积图的结合&#xff1b; 上代码 <template><section><divid"performaceLineChart"ref"performaceLineChartRef"style"width: 100%; height: 500px"></d…