图论03-【无权无向】-图的深度优先DFS遍历-路径问题/检测环/二分图

本文主要是介绍图论03-【无权无向】-图的深度优先DFS遍历-路径问题/检测环/二分图,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1. 代码仓库
  • 2. 单源路径
    • 2.1 思路
    • 2.2 主要代码
  • 3. 所有点对路径
    • 3.1 思路
    • 3.2 主要代码
  • 4. 路径问题的优化-提前结束递归
    • 4.1 思路
    • 4.2 主要代码
  • 5. 检测环
    • 5.1 思路
    • 5.2 主要代码
  • 6. 二分图
    • 6.1 思路
    • 6.2 主要代码
      • 6.2.1 遍历每个联通分量
      • 6.2.2 递归判断相邻两点的颜色是否一致

1. 代码仓库

https://github.com/Chufeng-Jiang/Graph-Theory

2. 单源路径

2.1 思路

  1. 构造visited数组和pre数组
    1.1 visited数组记录当前节点是否访问过
    也可以不使用visited数组,pre数组全部初始化为-1,联通的顶点对应的pre数组的值为前一个节点,pre数组中值为-1的都是不连通的顶点。
    1.2 pre数组记录当前节点的前一个节点
  2. 使用pre数组对终点进行反推回源点,并记录
  3. 将终点到原点的路径,反序输出

2.2 主要代码

   public SingleSourcePath(Graph G, int s){ //单源路径,要把源s传进来,而且只考虑与s连通的顶点,不连通的不考虑G.validateVertex(s);this.G = G;this.s = s;visited = new boolean[G.V()];pre = new int[G.V()];dfs(s, s);}private void dfs(int v, int parent){ //参数一:当前顶点; 参数二:上一个顶点visited[v] = true;pre[v] = parent;for(int w: G.adj(v)) //跟v相邻的所有顶点,相当于v是源,遍历与当前顶点相邻的所有点if(!visited[w])dfs(w, v); //(顶点,源)}public Iterable<Integer> path(int t){ //从源到t的路径ArrayList<Integer> res = new ArrayList<Integer>();if(!isConnectedTo(t)) return res;	int cur = t; // 从t往回找while(cur != s){res.add(cur); //添加当前节点(循环内不包含源)cur = pre[cur]; //pre[cur]的值是cur的上一个节点}res.add(s); //添加源Collections.reverse(res);return res;}

3. 所有点对路径

3.1 思路

对所有顶点进行遍历,创建每一个点的单源路径数组。

3.2 主要代码

public AllPairsPath(Graph G){this.G = G;paths = new SingleSourcePath[G.V()];for(int v = 0; v < G.V(); v ++)paths[v] = new SingleSourcePath(G, v);
}

4. 路径问题的优化-提前结束递归

4.1 思路

在填充visited和pre数组的时候,如果遇到了目标节点,直接结束。剩下的节点不进行处理。

if(v == t) return true; //程序出口,当到达t顶点时,返回true提前结束递归,而不仅仅是返回return

4.2 主要代码

    private boolean dfs(int v, int parent){visited[v] = true;pre[v] = parent;if(v == t) return true; //程序出口,当到达t顶点时,返回true提前结束递归,而不仅仅是返回returnfor(int w: G.adj(v)) //遍历与v相邻的顶点if(!visited[w]) //如果相邻的顶点没有被访问过if(dfs(w, v)) //递归遍历相邻的顶点,如果到达 v==t,则值为truereturn true; //提前返回truereturn false; // 转一圈没法达到t,就可以返回false}

5. 检测环

5.1 思路

从某一点v出发,找到了点w,w被访问过,并且w不是v的前一个节点

5.2 主要代码

public CycleDetection(Graph G){this.G = G;visited = new boolean[G.V()];//要对所有的连通分量进行环检测for(int v = 0; v < G.V(); v ++)if(!visited[v])  //如果没有访问过if(dfs(v, v)){ //则进行深度搜索,如果深度搜索出来的是true,说明有环,则进入循环breakhasCycle = true;break;}
}private boolean dfs(int v, int parent){visited[v] = true;for(int w: G.adj(v))if(!visited[w]){ //case1:如果w没有被访问过if(dfs(w, v)) //如果dfs返回true,则说明有环。因为dfs有环才会返回true,那么进入if选择语句return true提前结束return true;}else if(w != parent) // case2:从v出发,找到了w,w还被访问过,并且w不是v的前一个节点return true; // 此时找到了环//其他的情况,找一圈没有找到环,返回falsereturn false;
}

6. 二分图

在这里插入图片描述

6.1 思路

二分图可以通过染色过程把顶点区分开,
[-1:顶点还没染色]
[0:一种颜色]
[1:另外一种颜色]

6.2 主要代码

6.2.1 遍历每个联通分量

  1. dfs(v, 0) 返回true代表相连的两点颜色不一样,暂未出现矛盾;
  2. dfs(v, 0) 返回false代表相连的两点颜色一样,不符合二分图的定义,因此进入if语句块,设置isBipartite = false;并且提前结束循环。
for(int v = 0; v < G.V(); v ++)if(!visited[v]) //如果没有被访问// 起始的时候把v统一染成0色,如果dfs返回的false,进入下面结构体,否则跳出执行v++if(!dfs(v, 0)){ isBipartite = false; // 检测出错了,就设置成falsebreak; // 后续的循环就不需要进行了}

6.2.2 递归判断相邻两点的颜色是否一致

private boolean dfs(int v, int color){  //参数一:顶点   参数二:颜色visited[v] = true;colors[v] = color;//依次判断相邻顶点w的颜色for(int w: G.adj(v))if(!visited[w]){ //如果w没有被访问过,则进入判断if(!dfs(w, 1 - color)) //如果v的颜色是0,那么w的颜色应该是1。如果v的颜色是1,那么w的颜色应该是0.return false; //如果相邻的两个顶点颜色一样,那么就不是二分图}else if(colors[w] == colors[v]) //如果相邻的两个顶点颜色一样,那么就不是二分图return false;return true;
}

这篇关于图论03-【无权无向】-图的深度优先DFS遍历-路径问题/检测环/二分图的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/261428

相关文章

线上Java OOM问题定位与解决方案超详细解析

《线上JavaOOM问题定位与解决方案超详细解析》OOM是JVM抛出的错误,表示内存分配失败,:本文主要介绍线上JavaOOM问题定位与解决方案的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录一、OOM问题核心认知1.1 OOM定义与技术定位1.2 OOM常见类型及技术特征二、OOM问题定位工具

python获取指定名字的程序的文件路径的两种方法

《python获取指定名字的程序的文件路径的两种方法》本文主要介绍了python获取指定名字的程序的文件路径的两种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要... 最近在做项目,需要用到给定一个程序名字就可以自动获取到这个程序在Windows系统下的绝对路径,以下

Vue3绑定props默认值问题

《Vue3绑定props默认值问题》使用Vue3的defineProps配合TypeScript的interface定义props类型,并通过withDefaults设置默认值,使组件能安全访问传入的... 目录前言步骤步骤1:使用 defineProps 定义 Props步骤2:设置默认值总结前言使用T

深度解析Python中递归下降解析器的原理与实现

《深度解析Python中递归下降解析器的原理与实现》在编译器设计、配置文件处理和数据转换领域,递归下降解析器是最常用且最直观的解析技术,本文将详细介绍递归下降解析器的原理与实现,感兴趣的小伙伴可以跟随... 目录引言:解析器的核心价值一、递归下降解析器基础1.1 核心概念解析1.2 基本架构二、简单算术表达

深度解析Java @Serial 注解及常见错误案例

《深度解析Java@Serial注解及常见错误案例》Java14引入@Serial注解,用于编译时校验序列化成员,替代传统方式解决运行时错误,适用于Serializable类的方法/字段,需注意签... 目录Java @Serial 注解深度解析1. 注解本质2. 核心作用(1) 主要用途(2) 适用位置3

SpringBoot路径映射配置的实现步骤

《SpringBoot路径映射配置的实现步骤》本文介绍了如何在SpringBoot项目中配置路径映射,使得除static目录外的资源可被访问,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一... 目录SpringBoot路径映射补:springboot 配置虚拟路径映射 @RequestMapp

Java MCP 的鉴权深度解析

《JavaMCP的鉴权深度解析》文章介绍JavaMCP鉴权的实现方式,指出客户端可通过queryString、header或env传递鉴权信息,服务器端支持工具单独鉴权、过滤器集中鉴权及启动时鉴权... 目录一、MCP Client 侧(负责传递,比较简单)(1)常见的 mcpServers json 配置

Web服务器-Nginx-高并发问题

《Web服务器-Nginx-高并发问题》Nginx通过事件驱动、I/O多路复用和异步非阻塞技术高效处理高并发,结合动静分离和限流策略,提升性能与稳定性... 目录前言一、架构1. 原生多进程架构2. 事件驱动模型3. IO多路复用4. 异步非阻塞 I/O5. Nginx高并发配置实战二、动静分离1. 职责2

解决升级JDK报错:module java.base does not“opens java.lang.reflect“to unnamed module问题

《解决升级JDK报错:modulejava.basedoesnot“opensjava.lang.reflect“tounnamedmodule问题》SpringBoot启动错误源于Jav... 目录问题描述原因分析解决方案总结问题描述启动sprintboot时报以下错误原因分析编程异js常是由Ja

Maven中生命周期深度解析与实战指南

《Maven中生命周期深度解析与实战指南》这篇文章主要为大家详细介绍了Maven生命周期实战指南,包含核心概念、阶段详解、SpringBoot特化场景及企业级实践建议,希望对大家有一定的帮助... 目录一、Maven 生命周期哲学二、default生命周期核心阶段详解(高频使用)三、clean生命周期核心阶