图论与算法（4）图的深度优先遍历应用

1. 无向图的联通分量个数

1.1 联通分量个数

无向图的联通分量个数是指图中无法通过边连接到其他分量的顶点集合的个数。可以通过深度优先搜索或广度优先搜索来计算无向图的联通分量个数。

1.2 记录联通分量

（1）多个联通量的数：

7 6
0 1
0 2
1 3
1 4
2 3
2 6
5

（2）查询联通分量个数代码

public class CC {private Graph G;                // 顶点数private boolean [] visited;     // 边数private int cccount = 0;             // 联通分量个数public CC(Graph G){this.G = G;visited = new boolean[G.V()];for (int v = 0; v < G.V(); v++ ){if (!visited[v]){dfs(v);cccount++;}}}private void dfs(int v){visited[v] = true;for (int w : G.adj(v)) {if (!visited[w]) {dfs(w);}}}public int count(){return cccount;}
}

结果：

    public static void main(String[] args) {Graph graph = new Graph("cc.txt");CC cc = new CC(graph);System.out.println(cc.count());}执行结果：
2Process finished with exit code 0

在CC类中，私有成员变量G表示图对象，visited表示顶点访问标记数组，cccount表示联通分量个数。在dfs方法中的递归过程中，会一直深入到无法再继续深入为止，然后回溯到上一层顶点，继续搜索其他未访问过的顶点。每次完成dfs(v)的递归调用后，联通分量个数cccount加1，表示找到了一个新的联通分量。

1.3 记录每个顶点所属联通分量

将boolean[] visited改为int[] visited，并使用visited数组来记录每个顶点所属的联通分量ID，进行如下修改：

  1. 在构造函数CC中，将visited数组的类型修改为int[]，并初始化数组元素为-1，表示尚未分配联通分量ID。
  2. 在dfs方法中，将visited[v]设置为cccount，表示顶点v属于当前联通分量ID。
  3. 在count方法中，返回cccount。
  4. 添加一个新的方法getComponentID(int v)，用于获取顶点v所属的联通分量ID。
/**CC类用于计算无向图的联通分量个数。* @author wushaopei* @create 2023-06-03 21:49*/
public class CC_INT {private Graph G;                // 顶点数private int [] visited;     // 边数private int cccount = 0;             // 联通分量个数public CC_INT(Graph G){this.G = G;visited = new int[G.V()];   // 初始化顶点访问标记数组，默认为falsefor (int i = 0; i < visited.length; i++){visited[i] = -1;}for (int v = 0; v < G.V(); v++ ){if (visited[v] == -1){dfs(v, cccount);cccount++;   // 搜索完成后，联通分量个数加1}}}private void dfs(int v, int ccid){visited[v] = ccid;for (int w : G.adj(v)) {if (visited[w] == -1) {dfs(w, ccid);}}}public int count(){return cccount;}public boolean isConnected(int v, int w){G.validateVertex(v);G.validateVertex(w);return visited[v] == visited[w];}public static void main(String[] args) {Graph graph = new Graph("cc.txt");CC_INT cc = new CC_INT(graph);System.out.println(cc.isConnected(0,5));}
}

测试顶点是否属于同一个联通量上：

false

返回每个联通分量中的顶点列表：

    public ArrayList<Integer>[] components(){ArrayList<Integer>[] res = new ArrayList[cccount];for (int i = 0; i < cccount; i ++)res[i] = new ArrayList<>();for (int v = 0; v < G.V(); v ++)res[visited[v]].add(v);return res;}

这段代码是在CC类中添加了一个新的方法components()，用于返回每个联通分量中的顶点列表。

执行结果：

0 : 0 1 2 3 4 6 
1 : 5 Process finished with exit code 0

2. 路径问题

如果两个顶点在同一个联通分量中，那么它们之间一定存在路径。联通分量是指图中的一组顶点，这些顶点之间可以相互连通，通过边进行路径的传递。

单源路径问题是指在给定的图中，找到从单个源顶点到其他所有顶点的路径。下面是使用广度优先搜索（BFS）来解决单源路径问题的步骤：

public class SingleSourcePath {private Graph G;           // 图对象private int s;             // 源顶点private boolean[] visited; // 记录顶点是否访问过private int[] pre;         // 记录每个顶点在路径中的前一个顶点public SingleSourcePath(Graph G, int s){G.validateVertex(s);this.G = G;this.s = s;visited = new boolean[G.V()]; // 初始化visited数组，默认所有顶点未访问pre = new int[G.V()];         // 初始化pre数组，默认所有顶点前一个顶点为-1for (int i = 0; i < pre.length; i++) {pre[i] = -1;}dfs(s, s); // 调用深度优先搜索方法，从源顶点s开始遍历图}private void dfs(int v, int parent){visited[v] = true;  // 标记当前顶点为已访问pre[v] = parent;    // 设置当前顶点的前一个顶点为parentfor (int w : G.adj(v)) {if (!visited[w]) {dfs(w, v);  // 递归遍历当前顶点的未访问过的邻接顶点}}}public boolean isConnectedTo(int t){G.validateVertex(t); // 验证目标顶点t的有效性return visited[t];   // 返回目标顶点t是否与源顶点s相连}public Iterable<Integer> path(int t){ArrayList<Integer> res = new ArrayList<>();if (!isConnectedTo(t)) return res; // 若目标顶点t与源顶点s不相连，则返回空路径int cur = t;while (cur != s){res.add(cur);          // 将当前顶点加入路径中cur = pre[cur];        // 更新当前顶点为其前一个顶点}res.add(s);                // 将源顶点s加入路径中Collections.reverse(res);  // 反转路径列表，得到从源顶点s到目标顶点t的路径return res;                // 返回路径列表}public static void main(String[] args) {Graph graph = new Graph("cc.txt");SingleSourcePath sspath = new SingleSourcePath(graph, 0);System.out.println("0 -> 6 : " + sspath.path(6)); // 打印从顶点0到顶点6的路径}
}

在构造函数中，使用深度优先搜索（DFS）从源顶点s开始遍历图，并记录每个顶点在路径中的前一个顶点。通过isConnectedTo(t)方法可以判断目标顶点t是否与源顶点s相连，通过path(t)方法可以获取从源顶点s到目标顶点t的路径。在path(t)方法中，根据记录的前一个顶点信息

3. 从v开始遍历，看是否可以达到t

import java.util.ArrayList;
import java.util.Collections;/*** @author wushaopei* @create 2023-06-03 21:49*/
public class Path {private Graph G;           // 图对象private int s;             // 源顶点private int t;private boolean[] visited; // 记录顶点是否访问过private int[] pre;         // 记录每个顶点在路径中的前一个顶点public Path(Graph G, int s, int t){G.validateVertex(s);this.G = G;this.s = s;this.t = t;visited = new boolean[G.V()]; // 初始化visited数组，默认所有顶点未访问pre = new int[G.V()];         // 初始化pre数组，默认所有顶点前一个顶点为-1for (int i = 0; i < pre.length; i++) {pre[i] = -1;}dfs(s, s); // 调用深度优先搜索方法，从源顶点s开始遍历图for (boolean e: visited)System.out.print(e + " ");System.out.println();}private boolean dfs(int v, int parent){visited[v] = true;  // 标记当前顶点为已访问pre[v] = parent;    // 设置当前顶点的前一个顶点为parentif (v == t) return true;for (int w : G.adj(v)) {if (!visited[w]) {if (dfs(w, v))  // 递归遍历当前顶点的未访问过的邻接顶点return true;}}return false;}public boolean isConnected(){return visited[t];   // 返回目标顶点t是否与源顶点s相连}public Iterable<Integer> path(){ArrayList<Integer> res = new ArrayList<>();if (!isConnected()) return res; // 若目标顶点t与源顶点s不相连，则返回空路径int cur = t;while (cur != s){res.add(cur);          // 将当前顶点加入路径中cur = pre[cur];        // 更新当前顶点为其前一个顶点}res.add(s);                // 将源顶点s加入路径中Collections.reverse(res);  // 反转路径列表，得到从源顶点s到目标顶点t的路径return res;                // 返回路径列表}public static void main(String[] args) {Graph graph = new Graph("cc.txt");Path sspath = new Path(graph, 0, 6);System.out.println("0 -> 6 : " + sspath.path()); // 打印从顶点0到顶点6的路径Path sspath2 = new Path(graph, 0, 6);System.out.println("0 -> 1 : " + sspath2.path()); // 打印从顶点0到顶点6的路径}
}

上述代码，新增了一个顶点目标顶点t作为构造函数的参数，用于指定要寻找路径的目标顶点。将isConnectedTo()方法更名为isConnected()，用于判断源顶点s和目标顶点t是否相连。在dfs()方法中，增加了一个判断条件if (v == t) return true;，当当前顶点v等于目标顶点t时，直接返回true，表示找到了源顶点到目标顶点的路径。

在main()方法中，创建了一个新的Path对象sspath2，用于寻找从顶点0到顶点1的路径。

这个版本的代码在功能上与前一个版本基本相同，不同之处在于可以指定目标顶点，且通过isConnected()方法判断源顶点和目标顶点是否相连，而不再需要单独调用path()方法来判断路径是否存在。

4. 检测无向图中的环

/*** @author wushaopei* @create 2023-06-04 22:53*/
import java.util.*;public class CycleDetection {private Graph G;               // 图对象private boolean[] visited;     // 记录顶点是否访问过private boolean hasCycle;      // 是否存在环public CycleDetection(Graph G) {this.G = G;visited = new boolean[G.V()];hasCycle = false;for (int v = 0; v < G.V(); v++) {if (!visited[v]) {if (dfs(v, v)) {hasCycle = true;break;}}}}// 从顶点v开始，判断图中是否有环private boolean dfs(int v, int parent) {visited[v] = true;for (int w : G.adj(v)) {if (!visited[w]) {if (dfs(w, v)) return true;} else if (w != parent) {// 如果顶点w已经被访问过，并且w不是当前顶点v的父节点，说明存在环return true;}}return false;}public boolean hasCycle() {return hasCycle;}public static void main(String[] args) {Graph graph = new Graph("cc.txt");CycleDetection cycleDetection = new CycleDetection(graph);System.out.println("Has cycle: " + cycleDetection.hasCycle());Graph graph2 = new Graph("cc2.txt");CycleDetection cycleDetection2 = new CycleDetection(graph2);System.out.println("Has cycle: " + cycleDetection2.hasCycle());}
}

检测的数cc.txt、cc2.txt：

检测结果：

Connected to the target VM, address: '127.0.0.1:50987', transport: 'socket'
Has cycle: true
Has cycle: false
Disconnected from the target VM, address: '127.0.0.1:50987', transport: 'socket'Process finished with exit code 0

5. 二分图

5.1 概述

二分图，也称为二部图或二分图，是一种特殊的图结构。它的顶点集可以分为两个互不相交的子集，使得同一个子集内的顶点之间没有边相连。换句话说，可以用两种颜色对顶点进行着色，使得任意一条边的两个顶点颜色不相同。

二分图具有许多应用，例如任务分配、时间表调度、匹配问题等。在计算机科学中，判断一个图是否为二分图是一个重要的问题。

二分图的判断可以使用多种算法，其中一种常见的算法是使用深度优先搜索（DFS）或广度优先搜索（BFS）。

染色

染色是判断图是否为二分图的常用方法之一。该方法基于以下原理：如果一个图是二分图，那么可以用两种颜色对图的顶点进行染色，使得相邻顶点的颜色不同。

二分图检测

下面是一个用DFS判断无向图是否为二分图的代码：

import java.util.ArrayList;/*** @author wushaopei* @create 2023-06-03 21:49*/
public class BipartitionDetection {private Graph G;           // 顶点数private boolean [] visited;         // 边数private int[] colors;private boolean isBipartite = true;public BipartitionDetection(Graph G){this.G = G;visited = new boolean[G.V()];colors = new int[G.V()];for (int i = 0; i < G.V(); i ++)colors[i] = -1;for (int v = 0; v < G.V(); v++ ){if (!visited[v]){if (!dfs(v, 0))isBipartite = false;}}}private boolean dfs(int v, int color){visited[v] = true;colors[v] = color;for (int w : G.adj(v)) {if (!visited[w]) {if (!dfs(w, color == 0? 1:0)) return false;}else if (colors[v] == colors[w]) return false;}return true;}public boolean isBipartite(){return isBipartite;}public static void main(String[] args) {Graph graph = new Graph("cc.txt");BipartitionDetection bipartitionDetection = new BipartitionDetection(graph);System.out.println(bipartitionDetection.isBipartite());}
}

以上代码使用DFS进行图的遍历，并在遍历过程中对顶点进行染色。初始时，将第一个顶点的颜色设为0，然后递归地遍历该顶点的邻接顶点，并将它们染色为与当前顶点颜色不同的颜色（0或1）。如果发现某个顶点的邻接顶点已经被访问过，并且颜色与当前顶点相同，则图不是二分图，返回false。如果遍历结束后没有发现冲突，则图是二分图，返回true。

使用染色法进行二分图的判断具有简单直观的思路，时间复杂度为O(V+E)，其中V为顶点数，E为边数。该方法在实际应用中也有较好的效果。

6. 扩展

DFS还有图同构、NP难等知识点。

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

linux 应用程序 键盘,在Linux下安装Noted：适用于Linux的键盘驱动的笔记应用程序...

linux 应用程序 键盘,在Linux下安装Noted：适用于Linux的键盘驱动的笔记应用程序...

得益于Pop!_OS 20.04和Regolith Linux之类的发行版&#xff0c;键盘驱动的台式机环境逐渐风行一时。Noted是一个新的笔记应用程序&#xff0c;可在Linux和macOS上免费使用&#xff0c;该应用程序是受Notational Velocity(流行的macOS开源笔记记录应用程序)启发的&#xff0c;其…
阅读更多...
xheditor可视化富文本编辑器

xheditor可视化富文本编辑器

简洁易用的基于jQuery的富文本编辑器xheditor从CSDN上已经改版退出了&#xff0c;新版的Markdown编辑器将原版的编辑文章相关SEO的设置也设为自动获取了&#xff0c;总的感觉现在的编辑器没有原来那么方便了。本文来自http://xheditor.com/&#xff0c;纪念在CSDN上用过感觉最好…
阅读更多...
Guitar Pro中文版免费激活注册机码V2021.20.7下载地址问题疑难解答

Guitar Pro中文版免费激活注册机码V2021.20.7下载地址问题疑难解答

很多玩音乐的小伙伴都有一个共同的难题&#xff0c;目前很多编曲软件都是由国外引进来的&#xff0c;自然是以英文版为主&#xff0c;那作为国人的我们使用起来自然就不是那么容易&#xff0c;当然技术在更新&#xff0c;这个问题自然也是要有解决的方案的&#xff0c;今天小编…
阅读更多...
好用的Mac窗口管理器：Rectangle for Mac

好用的Mac窗口管理器：Rectangle for Mac

Rectangle Mac中文版是一个基于Spectacle应用程序的开源窗口管理器&#xff0c;用Swift编写&#xff0c;能够使用键盘快捷键移动窗口并调整其大小。Rectangle mac中文免费版适用于绝大数应用,并拥有维护良好的开源库,持续更新.欢迎大家下载体验Rectangle mac窗口管理器 Spectac…
阅读更多...
Affinity Photo for Mac中文破解版永久激活方法

Affinity Photo for Mac中文破解版永久激活方法

Affinity Photo for Mac中文破解版是一款可以和PS媲美的专业修图软件&#xff0c;专为Mac用户设计&#xff0c;affinity photo中文版采用最佳 PSD支持技术&#xff0c;支持您需要的所有图片处理调整和修改的功能&#xff0c;是一款非常不错的专业图像编辑软件。小编现为大家带来…
阅读更多...
toad 连接mysql8.0_toad for mysql免费版

toad 连接mysql8.0_toad for mysql免费版

MySQL是一种关系型数据库, 想对其进行专业的管理就来下载toad for mysql免费版吧! 它是一款非常好用MySQL数据库管理工具, 它能够帮助我们更加有效的编写SQL语句. 拥有自动执行数据库对象、版本控制集成、宏记录和回放等超多功能, 需要就来下载toad for mysql免费版吧! toad fo…
阅读更多...
iStat Menus 6 for Mac中文破解版激活方法无需激活码

iStat Menus 6 for Mac中文破解版激活方法无需激活码

iStat Menus 6 Mac 中文破解版是Mac OS平台上十分优秀的一款系统与硬件监控软件&#xff0c;通过istat menus for mac 我们可以实时掌握自己的Mac电脑情况&#xff0c;可以查看硬件温度、查看即时网速、显示CPU使用率等等&#xff0c;非常实用。小编现为大家带来istat menus ma…
阅读更多...
3dsmax记录

3dsmax记录

title: 3dsmax记录 categories: 3dsmax tags: [max, ta, 记录] date: 2018-06-02 14:16:18 comments: false 3dsmax记录&#xff0c;我的通神之路 前篇 3D MAX 2016从入门到精通视频教程 - https://www.bilibili.com/video/av39501981/?p82Autodesk 3dsMax 2018中文汉化破解版…
阅读更多...
Audition CC 2019 for Mac中文破解版永久激活方法附破解补丁

Audition CC 2019 for Mac中文破解版永久激活方法附破解补丁

Adobe Audition CC 2019 for Mac中文破解版全新上线&#xff0c;这是Adobe公司出品的一款专业数字音频编辑软件&#xff0c;提供先进的音频混音、编辑和效果处理功能&#xff0c;专为音频和视频专业人员设计。新版audition cc 2019 增加降噪和减少混响效果&#xff0c;多轨剪辑…
阅读更多...
[科普]为什么360会报键盘记录

[科普]为什么360会报键盘记录

转自&#xff1a;http://blog.xunleihd.com/360.html 本文只用了比较浅显的实验方法解释为什么破解版会被报风险&#xff0c;不深入讨论杀毒原理&#xff0c;我也并没有对360真实原理做过深入分析&#xff0c;感谢kpdd的指正。 做一个实验1、下载官方原版迅雷7.9.6.4502安装2、…
阅读更多...
bartender 10.1破解版|bartender条码打印10.1

bartender 10.1破解版|bartender条码打印10.1

点击下载出处&#xff1a;BarTender10.1破解版 bartender10.1破解版是一款专业的条码打印软件&#xff0c;在行业内广受好评&#xff0c;通过使用bartender我们可以将标签设计这个复杂的过程变得更简便&#xff0c;在设计中快速调整&#xff0c;即刻打印&#xff0c;非常迅速&…
阅读更多...
隐形的监控——无线键盘侦听

隐形的监控——无线键盘侦听

在用户使用计算机时&#xff0c;键盘是信息输入的主要媒介&#xff0c;键盘输入包含大量的私人机密信息&#xff0c;包括帐号密码等&#xff0c;所以键盘侦听被各种攻击者所大量采用&#xff0c;成为一种普遍但是破坏力强大的攻击方式。键盘侦听主要通过键盘记录器来实现&#…
阅读更多...
httpwatch professional 破解版v9.4.17

httpwatch professional 破解版v9.4.17

httpwatch 是一款功能非常强大的网页数据分析工具&#xff0c;它拥有缓存管理、数据和目录管理、消息头发送/接受、字符查询.POST、Cookies管理等功能&#xff0c;并且他还不需要代理服务器或一些复杂的网络监控工具就能够非常轻松的显示网页请求和回应的日志信息&#xff0c;…
阅读更多...
BCGControlBar库专业版,完整记录的MFC扩展类

BCGControlBar库专业版,完整记录的MFC扩展类

BCGControlBar库专业版,完整记录的MFC扩展类 BCGControlBar Library Professional (BCGControlBar Pro MFC) 是一个 MFC 扩展库&#xff0c;包含 300 多个经过精心设计、测试和完整记录的 MFC 扩展类&#xff0c;例如功能区、工具栏、菜单、控件以及自定义和可视化&#xff0c;…
阅读更多...
things 3 mac 破解版永久激活方法

things 3 mac 破解版永久激活方法

Things3 for Mac破解版是目前Mac平台上最好的任务管理应用程序&#xff0c;使用简单易用&#xff0c;而且设计美观。things3 mac 破解版功能强大具有工作安排&#xff0c;日志簿&#xff0c;任务管理&#xff0c;日程管理等实用功能&#xff0c;让用户可以更好的管理个人任务。…
阅读更多...
键盘输入保护器：KeyScrambler

键盘输入保护器：KeyScrambler

创新技术屏蔽数字资产 KeyScrambler 开创性的击键加密技术可在 Windows 操作系统、所有浏览器和数百个关键应用程序中实时深入地保护用户键入的信息。 值得信赖的软件让用户安心 KeyScrambler 已经被世界各地的专家、博主和用户测试和使用了 16 年&#xff0c;并被证明对最阴险…
阅读更多...
python你TM太皮了——区区30行代码就能记录键盘的一举一动

python你TM太皮了——区区30行代码就能记录键盘的一举一动

先看看效果 Like This↓ 一、公共WiFi 公用电脑什么的 在我们日常在线上工作、玩耍时&#xff0c;不论开电脑、登录淘宝、玩网游 统统都会用到键盘输入 在几乎所有网站&#xff0c;例如淘宝、百度、126邮箱等等 为了保护用户信息 登录时&#xff0c;输入框都是不可见的。…
阅读更多...
Android设备新型恶意软件，融合银行木马、键盘记录器和移动勒索软件等功能

Android设备新型恶意软件，融合银行木马、键盘记录器和移动勒索软件等功能

2019独角兽企业重金招聘Python工程师标准>>> 网络犯罪分子目前正在开发一种针对Android设备的新型恶意软件&#xff0c;它融合了银行木马、键盘记录器和移动勒索软件的功能。 根据来自ThreatFabric的安全研究人员称&#xff0c;这个恶意软件名为MysteryBot&#xff…
阅读更多...
ROS：古月居第一次作业（话题与服务编程、动作编程、TF编程）

ROS：古月居第一次作业（话题与服务编程、动作编程、TF编程）

一.话题与服务编程 话题与服务编程&#xff1a;通过代码新生一只海龟&#xff0c;放置在&#xff08;5,5&#xff09;点&#xff0c;命名为“turtle2”&#xff1b;通过代码订阅turtle2的实时位置并打印在终端&#xff1b;控制turtle2实现旋转运动&#xff1b; demo_turtle.l…
阅读更多...
RobotFramework+Eclispe环境安装篇

RobotFramework+Eclispe环境安装篇

环境安装是学习任何一个新东西的第一步&#xff0c;这一步没走舒坦&#xff0c;那后面就没有心情走下去了。 引用名句&#xff1a;工欲善其事必先利其器&#xff01;&#xff01; Robotframework&#xff1a;一款 自动化测试框架。 Eclipse&#xff1a;一款编辑工具。可以编…
阅读更多...
最新文章

Copyright @ 2022~2023