当前位置: 首页 > news >正文

C#,图论与图算法,输出无向图“欧拉路径”的弗勒里(Fleury Algorithm)算法和源程序

1 欧拉路径

欧拉路径是图中每一条边只访问一次的路径。欧拉回路是在同一顶点上开始和结束的欧拉路径。

这里展示一种输出欧拉路径回路的算法。

以下是Fleury用于打印欧拉轨迹或循环的算法(源)。

  1. 1、确保图形有0个或2个奇数顶点。
  2. 2、如果有0个奇数顶点,则从任意位置开始。如果有两个奇数顶点,请从其中一个开始。
  3. 3、沿边一次一条。如果要在桥和非桥之间进行选择,请始终选择非桥。
  4. 4、边缘用完时停止。

这个想法是,“不要过桥”,这样我们就可以回到一个顶点并遍历其余的边。

2 算法

在下面的代码中,假设给定的图具有欧拉轨迹或回路。主要焦点是打印欧拉轨迹或回路。我们可以使用isEulerian()首先检查给定图中是否存在欧拉轨迹或回路。

我们首先找到必须是奇点的起点(如果有奇点),并将其存储在变量“u”中。如果奇数顶点为零,则从顶点“0”开始。我们调用printEulerUtil()来打印从u开始的Euler tour。我们遍历u的所有相邻顶点,如果只有一个相邻顶点,我们会立即考虑它。如果有多个相邻顶点,则仅当边u-v不是桥时,才考虑相邻v。如何确定给定的边是否是桥?我们计算从u可到达的几个顶点。我们移除边u-v,然后再次计算从u可到达的顶点的数量。如果可到达顶点的数量减少,则边u-v是一个桥。为了计算可到达的顶点,我们可以使用BFS或DFS,我们在上面的代码中使用了DFS。函数DFSCount(u)返回可从u访问的多个顶点。

处理完边(包括在Euler教程中)后,我们将其从图形中移除。要删除边,我们将邻接列表中的顶点条目替换为-1。请注意,简单地删除节点可能不起作用,因为代码是递归的,并且父调用可能位于邻接列表的中间。

参考:

C#,图(Graph)的数据结构设计与源代码icon-default.png?t=O83Ahttps://blog.csdn.net/beijinghorn/article/details/125133711?spm=1001.2014.3001.5501

3 源代码:

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public partial class Graph{private void RemoveEdge(int u, int v){Adjacency[u].Remove(v);Adjacency[v].Remove(u);}private void Euler_Tour(){int u = 0;for (int i = 0; i < Node_Number; i++){if (Adjacency[i].Count % 2 == 1){u = i;break;}}Euler_Tour_Utility(u);}public List<string> Tours = new List<string>();private void Euler_Tour_Utility(int u){for (int i = 0; i < Adjacency[u].Count; i++){int v = Adjacency[u][i];if (Is_Valid_Next_Edge(u, v)){Tours.Add(u + " - " + v + " ");RemoveEdge(u, v);Euler_Tour_Utility(v);}}}private bool Is_Valid_Next_Edge(int u, int v){if (Adjacency[u].Count == 1){return true;}bool[] isVisited = new bool[this.Node_Number];int count1 = DFS_Count_Reach(u, isVisited);RemoveEdge(u, v);isVisited = new bool[this.Node_Number];int count2 = DFS_Count_Reach(u, isVisited);AddEdge(u, v);return (count1 > count2) ? false : true;}private int DFS_Count_Reach(int v, bool[] isVisited){isVisited[v] = true;int count = 1;foreach (int i in Adjacency[v]){if (!isVisited[i]){count = count + DFS_Count_Reach(i, isVisited);}}return count;}}public static partial class GraphDrives{public static string Euler_Tours(){StringBuilder sb = new StringBuilder();Graph g1 = new Graph(4);g1.AddEdge(0, 1);g1.AddEdge(0, 2);g1.AddEdge(1, 2);g1.AddEdge(2, 3);sb.AppendLine("Graph 1 Euler_Tours:<br>");sb.AppendLine(String.Join("<br>", g1.Tours.ToArray()) + "<br>");Graph g2 = new Graph(3);g2.AddEdge(0, 1);g2.AddEdge(1, 2);g2.AddEdge(2, 0);sb.AppendLine("Graph 2 Euler_Tours:<br>");sb.AppendLine(String.Join("<br>", g2.Tours.ToArray()) + "<br>");Graph g3 = new Graph(5);g3.AddEdge(1, 0);g3.AddEdge(0, 2);g3.AddEdge(2, 1);g3.AddEdge(0, 3);g3.AddEdge(3, 4);g3.AddEdge(3, 2);g3.AddEdge(3, 1);g3.AddEdge(2, 4);sb.AppendLine("Graph 3 Euler_Tours:<br>");sb.AppendLine(String.Join("<br>", g3.Tours.ToArray()) + "<br>");return sb.ToString();}}
}

相关文章:

C#,图论与图算法,输出无向图“欧拉路径”的弗勒里(Fleury Algorithm)算法和源程序

1 欧拉路径 欧拉路径是图中每一条边只访问一次的路径。欧拉回路是在同一顶点上开始和结束的欧拉路径。 这里展示一种输出欧拉路径或回路的算法。 以下是Fleury用于打印欧拉轨迹或循环的算法&#xff08;源&#xff09;。 1、确保图形有0个或2个奇数顶点。2、如果有0个奇数顶…...

计算机网络之---OSI七层模型

为什么会有七层模型 OSI七层模型的出现源于计算机网络技术的发展需求&#xff0c;主要解决以下几个问题&#xff1a; 标准化与互操作性 随着计算机网络的快速发展&#xff0c;不同厂商、不同技术之间的设备和系统需要能够无缝通信。而不同厂商在网络硬件、软件、协议等方面存在…...

mysql的mvcc理解

人阅读 一、说到mvcc就少不了事务隔离级别&#xff08;大白话解释&#xff09; 序列化&#xff08;SERIALIZABLE&#xff09;&#xff1a;事务之间完全隔离&#xff0c;当成一个序列&#xff0c;一个一个执行。 1 可重复读&#xff08;REPEATABLE READ&#xff09;&#xff…...

leetcode 面试经典 150 题:两数之和

链接两数之和题序号1题型数组解题方法1. 哈希表&#xff0c;2. 暴力法难度简单熟练度✅✅✅✅✅ 题目 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数&#xff0c;并返回它们的数组下标。 你可以假设每种输…...

nexus搭建maven私服

说到maven私服每个公司都有&#xff0c;比如我上一篇文章介绍的自定义日志starter&#xff0c;就可以上传到maven私服供大家使用&#xff0c;每次更新只需deploy一下就行&#xff0c;以下就是本人搭建私服的步骤 使用docker安装nexus #拉取镜像 docker pull sonatype/nexus3:…...

理解 Tomcat 架构

前言 Tomcat 是一个轻量级的 Web 容器&#xff0c;被广泛应用于 Java Web 开发中。通过它&#xff0c;我们可以轻松地部署和运行 Web 应用。在本文中&#xff0c;我们将深入分析 Tomcat 的核心架构&#xff0c;同时结合一段代码&#xff0c;手动实现一个简化的 Tomcat 服务&am…...

python3GUI--大屏可视化-传染病督导平台 By:PyQt5

文章目录 一&#xff0e;前言二&#xff0e;预览三&#xff0e;软件组成&开发心得1.样式&使用方法2.左侧表格实现3.设计4.学习5.体验效果 四&#xff0e;代码分享1.环形渐变进度组件2.自定义图片的背景组件 五&#xff0e;总结 大小&#xff1a;60.9 M&#xff0c;软件…...

如何选择适合的证件照制作软件,让您的照片制作更轻松

在当今数字化的时代&#xff0c;制作证件照不再需要专门前往照相馆。选择一款合适的证件照制作软件&#xff0c;您可以在家中轻松完成标准证件照的拍摄与制作。然而&#xff0c;面对市面上琳琅满目的软件&#xff0c;找到最适合您需求的软件并不简单。本文将为您详细介绍选择证…...

工作效率提升:使用Anaconda Prompt 创建虚拟环境总结

目录 完整顺序命令流程&#xff08;直接照着改就行&#xff09;详细步骤解析&#xff08;想要详细解析的看过来&#xff09;1. 创建一个用于存储 Conda 环境的目录&#xff08;可选&#xff09;2. 创建新的 Conda 虚拟环境并指定路径3. 激活新创建的环境4. 安装 Jupyter Notebo…...

Python自动化实战 —— 使用Selenium进行Web自动化

为了完成一项重复的任务&#xff0c;你需要在网站上进行大量的点击和操作&#xff0c;每次都要浪费大量的时间和精力。Python的Selenium库就可以自动化完成这些任务。 在本篇文章中&#xff0c;我们将会介绍如何使用Python的Selenium库进行Web自动化&#xff0c;以及如何将它应…...

【前端】【HTML】入门基础知识

参考视频&#xff1a;【狂神说Java】HTML5完整教学通俗易懂_哔哩哔哩_bilibili 一、基本结构 二、基本标签 <h1>&#xff1a;一级标题&#xff0c;通常用于页面的主标题&#xff0c;字体较大且醒目。 <h2>&#xff1a;二级标题&#xff0c;用于副标题或主要章节标…...

PHP获取局域网ip(192.168)

有时候&#xff0c;程序中&#xff0c;需要获取本机内网ip的情况&#xff0c;经过各种资料查找&#xff0c;最终确定一下代码&#xff1a; //获取内网ipfunction getLocalIP() {exec("ipconfig /all",$arr);$res mb_convert_encoding($arr, UTF-8, GBK);$ip ;fore…...

点击底部的 tabBar 属于 wx.switchTab 跳转方式,目标页面的 onLoad 不会触发(除非是第一次加载)

文章目录 1. tabBar 的跳转方式2. tabBar 跳转的特点3. 你的配置分析4. 生命周期触发情况5. 总结 很多人不明白什么是第一次加载&#xff0c;两种情况讨论&#xff0c;第一种情况假设我是开发者&#xff0c;第一次加载就是指点击微信开发者工具上边的编译按钮&#xff0c;每点击…...

基于PLC的酒店热水供应控制系统设计

摘 要 酒店的热水量需求比较大,热水加热消耗能源比较多,为了实现清洁能源加热实现热水供应,系统设计以太阳能作为主要能源来源,以电加热作为辅助能源来源进行系统的设计.通过集热器、储水箱、循环泵等设备组成酒店热水供水系统。通过控制温度传感器的信号&#xff0c;实现恒温…...

博客内所有项目均可在面包多平台进行购买

本人已入住面包多平台&#xff1a;我的 - 面包多 已有资料&#xff1a;...

《Mcal》--MCU模块

一、MCU模块的主要功能 控制系统时钟的产生。控制系统通用模块&#xff0c;该模块会涉及到Adc、Ftm等外设的配置。控制外设时钟。控制MCU运行的模式。初始化定义RAM Section。 比较重要的是时钟的配置。 二、系统时钟的配置 1、芯片时钟树 要想弄明白时钟配置&#xff0c;需…...

C语言:枚举类型

一、枚举类型的声明 枚举顾名思义就是一一列举。我们可以把可能的取值一一列举。比如我们现实生活中&#xff1a; 星期一到星期日是有限的7天&#xff0c;可以一一列举 &#xff1b;性别有&#xff1a;男、女、保密&#xff0c;也可以一一列举 &#xff1b;月份有12个月&#x…...

spring boot 多数据源集成mysql、postgresql、phoenix、doris等

如何搭建多数据源项目只要以下简单几步; 一. 创建核心在config.datasource文件夹里 二. 引入相对应的jar包 三. 创建数据库连接配置 四. 写逻辑代码进行验证 1.DataSource package com.irootech.config.datasource;import java.lang.annotation.*;Target({ElementType.MET…...

USB基础 -- USB 控制传输(Control Transfer)的重传机制

USB 控制传输&#xff08;Control Transfer&#xff09;的重传机制 1. 控制传输的事务结构 控制传输分为三个阶段&#xff0c;每个阶段都有自己的事务&#xff0c;并可能触发重传机制&#xff1a; 设置阶段&#xff08;Setup Stage&#xff09;&#xff1a;主机发送 8 字节的…...

云计算基础,虚拟化原理

文章目录 一、虚拟化1.1 什么是虚拟化1.2 虚拟化类型 二 、存储虚拟化2.1 存储指标2.2 存储类型2.3 存储协议2.4 RAID 三、内存 i/O虚拟化3.1 内存虚拟化基本概念地址空间转换原理内存共享与隔离原理 3.2 I/O 虚拟化基本概念模拟&#xff08;Emulation&#xff09;方式半虚拟化…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

9-Oracle 23 ai Vector Search 特性 知识准备

很多小伙伴是不是参加了 免费认证课程&#xff08;限时至2025/5/15&#xff09; Oracle AI Vector Search 1Z0-184-25考试&#xff0c;都顺利拿到certified了没。 各行各业的AI 大模型的到来&#xff0c;传统的数据库中的SQL还能不能打&#xff0c;结构化和非结构的话数据如何和…...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...

2.3 物理层设备

在这个视频中&#xff0c;我们要学习工作在物理层的两种网络设备&#xff0c;分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间&#xff0c;需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质&#xff0c;假设A节点要给…...

数据分析六部曲?

引言 上一章我们说到了数据分析六部曲&#xff0c;何谓六部曲呢&#xff1f; 其实啊&#xff0c;数据分析没那么难&#xff0c;只要掌握了下面这六个步骤&#xff0c;也就是数据分析六部曲&#xff0c;就算你是个啥都不懂的小白&#xff0c;也能慢慢上手做数据分析啦。 第一…...