C#，图论与图算法，图（Graph）的数据结构设计与源代码

因为后面即将发布的大量有关“图”的算法与源代码都需要用到下面的这些基础数据，为避免大家去下载，特意先发布于此。

一、图（Graph）的基础知识

图（Graph）是一组对象的图示，其中一些对象对通过链接连接。互连对象由称为顶点的点表示，连接顶点的链接称为边。

形式上，图是一对集（V，E），其中V是顶点集，E是连接顶点对的边集。

图形数据结构

数学图可以用数据结构表示。我们可以使用顶点数组和二维边数组来表示图。在继续之前，让我们先熟悉一些重要的术语−

顶点− 图的每个节点都表示为一个顶点。在以下示例中，带标签的圆表示顶点。因此，A到G是顶点。我们可以使用下图所示的数组来表示它们。这里A可以通过索引0来标识。B可以使用索引1等进行识别。

边− 边表示两个顶点之间的路径或两个顶点之间的线。在以下示例中，从A到B、B到C等的线表示边。我们可以使用二维数组来表示数组，如下图所示。这里AB可以表示为第0行第1列的1，BC可以表示为第1行第2列的1，依此类推，其他组合保持为0。

邻接关系− 如果两个节点或顶点通过边相互连接，则它们是相邻的。在以下示例中，B与A相邻，C与B相邻，依此类推。

路径− 路径表示两个顶点之间的边序列。

二、图的基本操作

以下是图形的基本主要操作：

添加顶点 — 将顶点添加到图形中。

添加边 — 在图形的两个顶点之间添加边。

显示顶点 — 显示图形的顶点。

遍历 — 深度优先遍历，宽度优先遍历；

布局 — 图的布局算法

三、图的相关数据

1、节点

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
    /// <summary>
    /// 图的结点（坐标）信息
    /// </summary>
    public class Node
    {
        /// <summary>
        /// 编号
        /// </summary>
        public int Id { get; set; } = 0;
        /// <summary>
        /// X坐标
        /// </summary>
        public double X { get; set; } = 0.0;
        /// <summary>
        /// Y坐标
        /// </summary>
        public double Y { get; set; } = 0.0;
        //public int Weight { get; set; } = 0;
        /// <summary>
        /// 默认构造函数
        /// </summary>
        public Node() 
		{
		}

		public Node(int id) 
		{
			Id = id;
		}

        /// <summary>
        /// 长度（原点距离）
        /// </summary>
        public double Length
        {
            get
            {
                double len = LengthSquare;
                if (Math.Abs(len) < float.Epsilon) return 0.0;
                return Math.Sqrt(len);
            }
        }

        /// <summary>
        /// 长度平方
        /// </summary>
        public double LengthSquare
        {
            get
            {
                return (X * X) + (Y * Y);
            }
        }

        /// <summary>
        /// 缩放
        /// </summary>
        /// <param name="rate"></param>
        public void Scale(double rate)
        {
            X *= rate;
            Y *= rate;
        }

        /// <summary>
        /// 移动到目的点
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        public void MoveTo(double x, double y)
        {
            X = x;
            Y = y;
        }

        /// <summary>
        /// 移动
        /// </summary>
        /// <param name="delta"></param>
        public void Move(Node delta)
        {
            this.X += delta.X;
            this.Y += delta.Y;
        }

        /// <summary>
        /// 加号重载
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static Node operator +(Node a, Node b)
        {
            Node c = new Node();
            c.X = a.X + b.X;
            c.Y = a.Y + b.Y;
            return c;
        }

        /// <summary>
        /// 减号重载
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static Node operator -(Node a, Node b)
        {
            Node c = new Node();
            c.X = a.X - b.X;
            c.Y = a.Y - b.Y;
            return c;
        }
    }
}

2、边

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
	public class Edge
	{
		/// <summary>
		/// 起点（第一点）编号
		/// </summary>
		public int First { get; set; } = -1;
		/// <summary>
		/// 终点（第二点）编号
		/// </summary>
		public int Second { get; set; } = -1;
		/// <summary>
		/// 权值
		/// </summary>
		public int Weight { get; set; } = 0;
		/// <summary>
		/// 默认构造函数
		/// </summary>
		public Edge()
		{
		}
		/// <summary>
		/// 两点构造函数
		/// </summary>
		/// <param name="f"></param>
		/// <param name="s"></param>
		public Edge(int f, int s)
		{
			First = f;
			Second = s;
		}
		/// <summary>
		/// 两点及权值构造函数
		/// </summary>
		/// <param name="f"></param>
		/// <param name="s"></param>
		/// <param name="w"></param>
		public Edge(int f, int s, int w)
		{
			First = f;
			Second = s;
			Weight = w;
		}
	}
}

3、图

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
	public partial class Graph
	{
		/// <summary>
		/// 是否为有向图？
		/// </summary>
		public bool Direction { get; set; } = false;
		/*
		/// <summary>
		/// 节点编码的起始编号0或1
		/// </summary>
		public int Node_Index_Start { get; set; } = 0;
		/// <summary>
		/// 节点编码的结束编号
		/// </summary>
		public int Node_Index_End { get; set; } = 0;
		*/
		/// <summary>
		/// 节点总数
		/// </summary>
		public int Node_Number { get; set; } = 0;
		/*
		/// <summary>
		/// 连线编码的起始编号0或1
		/// </summary>
		public int Edge_Start { get; set; } = 0;
		*/
		/// <summary>
		/// 连接线总数
		/// </summary>
		public int Edge_Number { get; set; } = 0;
		/// <summary>
		/// 节点编码列表
		/// </summary>
		public List<Node> Nodes { get; set; } = new List<Node>();
		/// <summary>
		/// 连接线列表
		/// </summary>
		public List<Edge> Edges { get; set; } = new List<Edge>();
		/// <summary>
		/// 节点邻接表
		/// </summary>
		public List<int>[] Adjacency { get; set; } = null;
		/// <summary>
		/// 邻接矩阵
		/// </summary>
		public int[,] Matrix { get; set; } = null;

		public Graph()
		{
		}

		public Graph(int v, int e = 0, bool direct = false)
		{
			Direction = direct;
			Node_Number = v;
			Edge_Number = e;
			Adjacency = new List<int>[Node_Number + 1];
			for (int i = 0; i <= Node_Number; i++)
			{
				Adjacency[i] = new List<int>();
			}
		}

		public void AddEdge(int a, int b)
		{
			Adjacency[a].Add(b);
			if (Direction == false)
			{
				Adjacency[b].Add(a);
			}
		}

		public void AddEdge(int a, int b, int w)
		{
			AddEdge(a, b);
			Edges.Add(new Edge(a, b, w));
		}

		public void AddEdge(int idx, int a, int b, int w)
		{
			Edges[idx] = new Edge(a, b, w);
		}

		public void AddNode(int a)
		{
			if (!Nodes.Exists(t => t.Id == a))
			{
				Nodes.Add(new Node(a));
			}
		}

		/// <summary>
		/// 按三元组构造图数据
		/// 三元数组为: {source,destination,weight}
		/// </summary>
		/// <param name="ternary_array">三元数据</param>
		public Graph(int[,] ternary_array, bool dir = false)
		{
			// 有向图？无向图？
			Direction = dir;

			Nodes = new List<Node>();
			Edges = new List<Edge>();
			Edge_Number = ternary_array.GetLength(0);
			for (int i = 0; i < ternary_array.GetLength(0); i++)
			{
				int n1 = ternary_array[i, 0];
				int n2 = ternary_array[i, 1];
				int wt = ternary_array[i, 2];
				AddEdge(n1, n2, wt);
			}
		}

		/// <summary>
		/// 按关联矩阵数据构建图
		/// [N x N]，元素=0，无连接，>0 有连接线及weight
		/// </summary>
		/// <param name="v">节点数</param>
		/// <param name="e">连边数</param>
		/// <param name="matrix">关联矩阵</param>
		public Graph(int[,] matrix)
		{
			Node_Number = matrix.GetLength(0);
			Nodes = new List<Node>();
			Edges = new List<Edge>();
			Matrix = new int[Node_Number, Node_Number];
			for (int i = 0; i < Node_Number; i++)
			{
				for (int j = 0; j < Node_Number; j++)
				{
					if (matrix[i, j] > 0)
					{
						AddEdge(i, j, matrix[i, j]);
						Matrix[i, j] = matrix[i, j];
					}
				}
			}
		}

		public Edge FindEdge(int a, int b)
        {
			foreach (Edge e in Edges)
			{
				if (e.First == a && e.Second == b)
				{
					return e;
				}
				if (Direction == false)
				{
					if (e.First == b && e.Second == a)
					{
						return e;
					}
				}
			}
			return null;
        }

		/// <summary>
		/// 按邻接表的构造函数
		/// </summary>
		/// <param name="adj"></param>
		public Graph(List<List<int>> adj, bool dir = false)
		{
			// 有向图？无向图？
			Direction = dir;

			Node_Number = adj.Count;
			Nodes = new List<Node>();
			Edges = new List<Edge>();

			// 邻接矩阵
			Adjacency = adj.ToArray();

			int idx = 1;
			foreach (List<int> xu in adj)
			{
				foreach (int xv in xu)
				{
					AddEdge(idx, xv);
				}
				idx++;
			}
		}

		/// <summary>
		/// 邻接表 转为 邻接矩阵
		/// 1 起步！
		/// </summary>
		/// <returns></returns>
		public int[,] AdjacencyMatrix()
		{
			if (Matrix == null)
			{
				Matrix = new int[Node_Number + 1, Node_Number + 1];
				int idx = 0;
				foreach (List<int> xu in Adjacency)
				{
					// 因为 Adjacency[0] 没有被使用！跳过！
					if (idx > 0)
					{
						foreach (int xv in xu)
						{
							Matrix[idx, xv] = 1;
						}
					}
					idx++;
				}
			}
			return Matrix;
		}
	}
}

POWER BY TRUFFER.CN

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

zabbix企业微信接入结合海螺问问编写的shell脚本

zabbix企业微信接入结合海螺问问编写的shell脚本

前言 博客懒得写详细了&#xff0c;视频剪的累死了&#xff0c;看视频就好了 白帽小丑的个人空间-白帽小丑个人主页-哔哩哔哩视频 shell脚本 #!/bin/bash #set -x CorpID"" #我的企业下面的CorpID Secret"" #创建的应用那…
阅读更多...
web canvas系列——快速入门上手绘制二维空间点、线、面

web canvas系列——快速入门上手绘制二维空间点、线、面

文章目录 ⭐前言⭐基本用法&#x1f496;设置一个 canvas 2D 上下文&#x1f496;绘制矩形常用方法属性&#x1f496;绘制一个红蓝交替的矩形 &#x1f496;绘制路径常用方法属性&#x1f496;画一个点&#x1f496;画一条线&#x1f496;画一个三角形面&#x1f496;画一个笑脸…
阅读更多...
Nginx高级技术: 代理缓存配置

Nginx高级技术: 代理缓存配置

一、缓存说明 Nginx缓存&#xff0c;Nginx 提供了一个强大的反向代理和 HTTP 服务器功能&#xff0c;同时也是一个高效的缓存服务器。一般情况下系统用到的缓存有以下三种&#xff1a; 1、服务端缓存&#xff1a;缓存存在后端服务器&#xff0c;如 redis。 2、代理缓存&#…
阅读更多...
【QT入门】VS2019+QT的开发环境配置

【QT入门】VS2019+QT的开发环境配置

声明&#xff1a;该专栏为本人学习Qt知识点时候的笔记汇总&#xff0c;希望能给初学的朋友们一点帮助(加油&#xff01;) 往期回顾&#xff1a; 【QT入门】什么是qt&#xff0c;发展历史&#xff0c;特征&#xff0c;应用&#xff0c;QtCreator-CSDN博客【QT入门】Windows平台下…
阅读更多...
【Vue】Request模块 - axios 封装Vuex的持久化存储

【Vue】Request模块 - axios 封装Vuex的持久化存储

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;Vue ⛺️稳中求进&#xff0c;晒太阳 Request模块 - axios 封装 使用axios来请求后端接口&#xff0c;一般会对axios进行一些配置&#xff08;比如配置基础地址&#xff0c;请求响应拦截器…
阅读更多...
金鸣表格文字识别大师：解决医学文档PDF生僻字识别难题的利器

金鸣表格文字识别大师：解决医学文档PDF生僻字识别难题的利器

在医学领域&#xff0c;文档资料常常涉及到大量的专业术语和生僻字&#xff0c;例如唑吡坦、哌替啶、氟桂利嗪等。这些专业词汇对于非专业人士来说可能较为陌生&#xff0c;但在医学研究和临床实践中却具有不可或缺的重要性。然而&#xff0c;当这些生僻字出现在PDF文档中&…
阅读更多...
Rust学习02：推荐一本入门书，免费的

Rust学习02：推荐一本入门书，免费的

都说Rust的学习曲线很陡峭&#xff0c;试过才知雀实不容易。 先说我的基础&#xff0c;非科班&#xff0c;自学Python&#xff0c;写过几个小程序。 我买书从来不扣扣嗖嗖的&#xff0c;所以先啃了几本Rust的入门书&#xff0c;包括&#xff1a; Tim McNamara的《Rust实战》&am…
阅读更多...
单片机第四季-第一课：RTOS

单片机第四季-第一课：RTOS

1&#xff0c;RTOS来龙去脉 操作系统是什么&#xff1f; 以人类社会类比&#xff0c;小公司三四个人都是干活的&#xff0c;大公司有几万人其中有几千人从事管理工作&#xff0c;他们的工作是让其他人的干活效率更高。 51单片机为什么没有操作系统&#xff0c;因为51的性能太…
阅读更多...
Github 2024-03-17 php开源项目日报 Top9

Github 2024-03-17 php开源项目日报 Top9

根据Github Trendings的统计，今日(2024-03-17统计)共有9个项目上榜。根据开发语言中项目的数量，汇总情况如下： 开发语言项目数量PHP项目9Blade项目2Laravel：表达力和优雅的 Web 应用程序框架 创建周期：4631 天开发语言：PHP, BladeStar数量：75969 个Fork数量：24281 次关…
阅读更多...
校园闲置物品交易网站 |基于springboot框架+ Mysql+Java+Tomcat的校园闲置物品交易网站设计与实现(可运行源码+设计文档)

校园闲置物品交易网站 |基于springboot框架+ Mysql+Java+Tomcat的校园闲置物品交易网站设计与实现(可运行源码+设计文档)

推荐阅读100套最新项目 最新ssmjava项目文档视频演示可运行源码分享 最新jspjava项目文档视频演示可运行源码分享 最新Spring Boot项目文档视频演示可运行源码分享 目录 前台功能效果图 用户功能模块 管理员功能登录前台功能效果图 系统功能设计 数据库E-R图设计 lunwen…
阅读更多...
用 Visual Studio 调试器中查看内存中图像

用 Visual Studio 调试器中查看内存中图像

返回目录&#xff1a;OpenCV系列文章目录&#xff08;持续更新中......&#xff09; 前一篇&#xff1a;OpenCV4.9.0在windows系统下的安装 后一篇&#xff1a;OpenCV-Java 开发简介 ​警告 本教程可以包含过时的信息。 Image Watch 是 Microsoft Visual Studio 的插件&a…
阅读更多...
蓝桥：保险箱（Python，动态规划）

蓝桥：保险箱（Python，动态规划）

问题描述&#xff1a; 小蓝有一个保险箱&#xff0c;保险箱上共有 n 位数字。小蓝可以任意调整保险箱上的每个数字&#xff0c;每一次操作可以将其中一位增加 1 或减少 1。当某位原本为 9 或 0 时可能会向前&#xff08;左边&#xff09;进位/退位&#xff0c;当最高位&#x…
阅读更多...
Rancher操作手册（v2.7.5-rc1）

Rancher操作手册（v2.7.5-rc1）

1.登录 访问地址&#xff1a;10.66.55.132使用账号和密码登录。初始的页面是英文版本&#xff0c;可以点击左下方改为简体中文 登录成功后可以看到现有的集群。右上角可以进行新集群的创建和导入已有集群。点击箭头所指的蓝色集群名称可以进入集群。 2.集群仪表盘 进入到集…
阅读更多...
Tuxera NTFS 2023安装使用教程 Tuxera NTFS破解版 Tuxera NTFS for Mac优惠

Tuxera NTFS 2023安装使用教程 Tuxera NTFS破解版 Tuxera NTFS for Mac优惠

对于必须在Windows电脑和Mac电脑之间来回切换的Mac朋友来说&#xff0c;跨平台不兼容一直是一个巨大的障碍&#xff0c;尤其是当我们需要使用NTFS格式的硬盘在Windows和macOS之间共享文件时。因为Mac默认不支持写入NTFS磁盘。 为了解决这一问题&#xff0c;很多朋友会选择很便捷…
阅读更多...
Simulink|局部遮荫下光伏组件多峰值PSO-MPPT控制

Simulink|局部遮荫下光伏组件多峰值PSO-MPPT控制

目录 主要内容 1.光伏电池工程数学模型的输出特性程序 2.普通扰动观察法进行MPPT 3.基于粒子群寻优的多峰输出特性 4.PSO_MPPT仿真模型 程序下载链接 主要内容 在实际的光伏发电系统中,由于环境多变等因素的影响,当局部出现被遮挡情况时光伏阵列的功率-电压(P-U)特…
阅读更多...
SQLiteC/C++接口详细介绍之sqlite3类（十七）

SQLiteC/C++接口详细介绍之sqlite3类（十七）

返回目录&#xff1a;SQLite—免费开源数据库系列文章目录 上一篇&#xff1a;SQLiteC/C接口详细介绍之sqlite3类&#xff08;十六&#xff09; 下一篇&#xff1a; SQLiteC/C接口详细介绍之sqlite3类&#xff08;十八&#xff09; ​ 53.sqlite3_trace_v2 函数功能&#x…
阅读更多...
【ArcGISPro】道路数据下载并使用

【ArcGISPro】道路数据下载并使用

下载 下载链接： Geofabrik 下载服务器 这些数据通常 每天更新。 下载结果 arcmap用户下载工具 10.2：http://www.arcgis.com/home/item.html?id=16970017f81349548d0a9eead0ebba39 10.3：
阅读更多...
最细节操作 Linux LVM 逻辑卷管理

最细节操作 Linux LVM 逻辑卷管理

Linux LVM&#xff08;逻辑卷管理&#xff09; 周末愉快&#xff0c;今天带大家实战一下LVM! 一、LVM理论 LVM&#xff0c;即Logical Volume Manager&#xff0c;逻辑卷管理器&#xff0c;是一种硬盘的虚拟化技术&#xff0c;可以允许用户的硬盘资源进行灵活的调整和动态管理…
阅读更多...
Git版本管理--远程仓库

Git版本管理--远程仓库

前言&#xff1a; 本文记录学习使用 Git 版本管理工具的学习笔记&#xff0c;通过阅读参考链接中的博文和实际操作&#xff0c;快速的上手使用 Git 工具。 本文参考了引用链接博文里的内容。 引用: 重学Git-Git远程仓库管理_git remote add origin-CSDN博客 Git学习笔记&am…
阅读更多...
27-Java MVC 模式

27-Java MVC 模式

Java空对象模式 实现范例 MVC模式代表 Model-View-Controller&#xff08;模型-视图-控制器&#xff09; 模式MVC模式用于应用程序的分层开发 Model&#xff08;模型&#xff09; - 模型代表一个存取数据的对象或 JAVA POJO 它也可以带有逻辑&#xff0c;在数据变化时更新控制…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站