当前位置: 首页 > 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();}}
}

http://www.lryc.cn/news/518845.html

相关文章:

  • 计算机网络之---OSI七层模型
  • mysql的mvcc理解
  • leetcode 面试经典 150 题:两数之和
  • nexus搭建maven私服
  • 理解 Tomcat 架构
  • python3GUI--大屏可视化-传染病督导平台 By:PyQt5
  • 如何选择适合的证件照制作软件,让您的照片制作更轻松
  • 工作效率提升:使用Anaconda Prompt 创建虚拟环境总结
  • Python自动化实战 —— 使用Selenium进行Web自动化
  • 【前端】【HTML】入门基础知识
  • PHP获取局域网ip(192.168)
  • 点击底部的 tabBar 属于 wx.switchTab 跳转方式,目标页面的 onLoad 不会触发(除非是第一次加载)
  • 基于PLC的酒店热水供应控制系统设计
  • 博客内所有项目均可在面包多平台进行购买
  • 《Mcal》--MCU模块
  • C语言:枚举类型
  • spring boot 多数据源集成mysql、postgresql、phoenix、doris等
  • USB基础 -- USB 控制传输(Control Transfer)的重传机制
  • 云计算基础,虚拟化原理
  • 浮点数在C语言开发中为什么不精确?
  • ChatGPT网络错误如何解决
  • Vue3初学之插槽(slot)使用
  • 使用PVE快速创建虚拟机集群并搭建docker环境
  • 带格式 pdf 翻译
  • 【C++】C++11(一)
  • 初学stm32 --- ADC单通道采集
  • 【动态规划篇】欣赏概率论与镜像法融合下,别出心裁探索解答括号序列问题
  • Java(day7)
  • Word 转成pdf及打印的开源方案支持xp
  • LabVIEW软件侵权分析与应对