C#数据结构与算法揭秘11

简介:

这节,我们说一说,图的基本源代码的源代码实现。具体情况,请听我一一给大家娓娓道来。

图的基本操作用一个接口来表示,为表示图的基本操作,同时给出了顶点类的实现。由于顶点只保存自身信息,所以顶点类 Node<T>很简单,里面只有一个字段 data。

顶点的类 Node<T>的实现如下所示。
public Class Node<T>
{
private T data; //数据域

//构造器
public Node(T v)
{
data = v;
}

//数据域属性
public T Data
{
get
{
return data;
}
set
{
data = value;

}
}

结构如图所示:


}

图的接口IGraph<T>的定义如下所示。
public interface IGraph<T>
{
//获取顶点数
int GetNumOfVertex();

初始条件:图存在;
操作结果:返回图中的顶点数  由于用到循环的计数的方式。所以其算法的时间的复杂度是O(n2) 如图所示:

//获取边或弧的数目
int GetNumOfEdge();

初始条件:图存在;
操作结果:返回图中的边或弧的数目.由于用到循环的计数的方式。所以其算法的时间的复杂度是O(n2) 如图所示:

//在两个顶点之间添加权为v的边或弧
void SetEdge(Node<T> v1, Node<T> v2, int v);

初始条件:图存在,顶点 v1 和 v2 是图的两个顶点;
操作结果:在顶点 v1 和 v2 之间添加一条边或弧并设边或弧的值为 v。由于用到循环的发送方式,时间复杂度是O(n2) 如图所示:



//删除两个顶点之间的边或弧
void DelEdge(Node<T> v1, Node<T> v2);

初始条件:图存在,顶点 v1 和 v2 是图的两个顶点并且 v1 和 v2 之间有一条边或弧;
操作结果:删除顶点 v1 和 v2 之间的边或弧。  如图所示:

//判断两个顶点之间是否有边或弧
bool IsEdge(Node<T> v1, Node<T> v2);

初始条件:图存在,顶点 v1 和 v2 是图的两个顶点;
操作结果:如果 v1 和 v2 之间有一条边或弧,返回 true,否则返回 false。 由于用到了循环,算法的时间的复杂度是O(n2),如图所示:

}

讨论了这些图的结源代码基本实现,我们进入了下一个议题,讨论了图的存储结构。

图是一种复杂的数据结构,顶点之间是多对多的关系,即任意两个顶点之间都可能存在联系。 所以, 无法以顶点在存储区的位置关系来表示顶点之间的联系,即顺序存储结构不能完全存储图的信息,但可以用数组来存储图的顶点信息。要存储顶点之间的联系必须用链式存储结构或者二维数组。图的存储结构有多种,这里只介绍两种基本的存储结构:邻接矩阵和邻接表。

什么是邻接矩阵,所谓邻接矩阵(Adjacency Matrix)是用两个数组来表示图,一个数组是一维数组,存储图中顶点的信息,一个数组是二维数组,即矩阵,存储顶点之间相邻的信息,也就是边(或弧)的信息,这是邻接矩阵名称的由来。

假设图G=(V,E)中有n个顶点,即V={v0,v1,…,vn-1},用矩阵A[i][j]表示边
(或弧)的信息。矩阵A[i][j]是一个n×n的矩阵,矩阵的元素为:
A[i][j]=1若(v[i],v[j])是E(G)的边和元素

A[i][j]=0若(v[i],v[j])不是E(G)的边和元素

若 G 是网,则邻接矩阵可定义为:

A[i][j]=wij若(v[i],v[j])是E(G)的边和元素

A[i][j]=∞若(v[i],v[j])不是E(G)的边和元素

其中,wij 表示边(vi,vj)或弧<vi,vj>上的权值;∞表示一个计算机允许的大于
所有边上权值的数。

    

从图的邻接矩阵表示法可以看出这种表示法的特点是:
(1)无向图或无向网的邻接矩阵一定是一个对称矩阵。因此,在具体存放邻接矩阵时只需存放上(或下)三角矩阵的元素即可。
(2)可以很方便地查找图中任一顶点的度。对于无向图或无向网而言,顶点 vi 的度就是邻接矩阵中第 i 行或第 i 列中非 0 或非∞的元素的个数。对于有向图或有向网而言,顶点 vi 的入度是邻接矩阵中第 i 列中非 0 或非∞的元素的个数,顶点 vi 的出度是邻接矩阵中第 i 行中非 0 或非∞的元素的个数。
(3)可以很方便地查找图中任一条边或弧的权值,只要 A[i][j]为 0 或∞,就说明顶点 vi 和 vj 之间不存在边或弧。但是,要确定图中有多少条边或弧,则必须按行、按列对每个元素进行检测,所花费的时间代价是很大的。这是用邻接矩阵存储图的局限性。
下面以无向图的邻接矩阵类的实现来说明图的邻接矩阵表示的类的实现。
无向图邻接矩阵类 GraphAdjMatrix<T>中有三个成员字段, 一个是 Node<T>类型的一维数组 nodes,存

无向图邻接矩阵类 GraphAdjMatrix<T>的实现如下所示。
public class GraphAdjMatrix<T> : IGraph<T>
{
private Node<T>[] nodes; //顶点数组
private int numEdges; //边的数目
private int[ ,] matrix; //邻接矩阵数组
如图所示:


//构造器
public GraphAdjMatrix (int n)
{

nodes = new Node<T>[n];
matrix = new int[n,n];
numEdges = 0;
}

//获取索引为index的顶点的信息
public Node<T> GetNode(int index)
{
return nodes[index];
}

//设置索引为index的顶点的信息 算法的复杂度的是O(1) 
public void SetNode(int index, Node<T> v)
{
nodes[index] = v;
}

//边的数目属性
public int NumEdges
{
get
{
return numEdges;
}
set
{
numEdges = value;
}
}

//获取matrix[index1, index2]的值 算法的复杂度是O(1)
public int GetMatrix(int index1, int index2)
{
return matrix[index1, index2];
}

//设置matrix[index1, index2]的值 算法的复杂度是O(1)
public void SetMatrix(int index1, int index2)
{
matrix[index1, index2] = 1;
}

//获取顶点的数目 算法的复杂度是O(1)
public int GetNumOfVertex()

{
return nodes.Length;
}

//获取边的数目  算法的复杂度是O(1)
public int GetNumOfEdge()
{
return numEdges;
}

//判断v是否是图的顶点  算法的复杂度是O(n)
public bool IsNode(Node<T> v)
{
//遍历顶点数组
foreach (Node<T> nd in nodes)
{
//如果顶点nd与v相等,则v是图的顶点,返回true
if (v.Equals(nd))
{
return true;
}
}

return false;
}

//获取顶点v在顶点数组中的索引  算法的复杂度是O(n)
public int GetIndex(Node<T> v)
{
int i = -1;

//遍历顶点数组
for (i = 0; i < nodes.Length; ++i)
{
//如果顶点v与nodes[i]相等,则v是图的顶点,返回索引值i。
if (nodes[i].Equals(v))
{
return i;
}
}
return i;
}

//在顶点v1和v2之间添加权值为v的边 算法是O(n2)

public void SetEdge(Node<T> v1, Node<T> v2,int v)
{
//v1或v2不是图的顶点
if (!IsNode(v1) || !IsNode(v2))
{
Console.WriteLine("Node is not belong to Graph!");
return;
}

//不是无向图
if(v != 1)
{
Console.WriteLine("Weight is not right!");
return;
}

//矩阵是对称矩阵
matrix[GetIndex(v1), GetIndex(v2)] = v;
matrix[GetIndex(v2), GetIndex(v1)] = v;
++numEdges;
}

//删除顶点v1和v2之间的边
public void DelEdge(Node<T> v1, Node<T> v2)
{
//v1或v2不是图的顶点
if (!IsNode(v1) || !IsNode(v2))
{
Console.WriteLine("Node is not belong to Graph!");
return;
}

//顶点v1与v2之间存在边
if (matrix[GetIndex(v1), GetIndex(v2)] == 1)
{
//矩阵是对称矩阵
matrix[GetIndex(v1), GetIndex(v2)] = 0;
matrix[GetIndex(v2), GetIndex(v1)] = 0;
--numEdges;
}
}

//判断顶点v1与v2之间是否存在边  算法的复杂度是O(1)
public bool IsEdge(Node<T> v1, Node<T> v2)

{
//v1或v2不是图的顶点
if (!IsNode(v1) || !IsNode(v2))
{
Console.WriteLine("Node is not belong to Graph!");
return false;
}

//顶点v1与v2之间存在边
if (matrix[GetIndex(v1), GetIndex(v2)] == 1)
{
return true;
}
else //不存在边
{
return false;
}
}

如图所示:

}

二。连接存储:

邻接表 (Adjacency List) 是图的一种顺序存储与链式存储相结合的存储结构,类似于树的孩子链表表示法。 顺序存储指的是图中的顶点信息用一个顶点数组来存储,一个顶点数组元素是一个顶点结点,顶点结点有两个域,一个是数据域data,存放与顶点相关的信息,一个是引用域 firstAdj,存放该顶点的邻接表的第一个结点的地址。顶点的邻接表是把所有邻接于某顶点的顶点构成的一个表,它是采用链式存储结构。所以,我们说邻接表是图的一种顺序存储与链式存储相结合的存储结构。其中,邻接表中的每个结点实际上保存的是与该顶点相关的边或弧的信息,它有两个域,一个是邻接顶点域 adjvex,存放邻接顶点的信息,实际上就是邻接顶点在顶点数组中的序号;一个是引用域 next,存放下一个邻接顶点的结点的地址。顶点结点和邻接表结点的结构如下图所示。

目录
相关文章
|
3月前
|
存储 运维 监控
基于 C# 语言的 Dijkstra 算法在局域网内监控软件件中的优化与实现研究
本文针对局域网监控系统中传统Dijkstra算法的性能瓶颈,提出了一种基于优先队列和邻接表优化的改进方案。通过重构数据结构与计算流程,将时间复杂度从O(V²)降至O((V+E)logV),显著提升大规模网络环境下的计算效率与资源利用率。实验表明,优化后算法在包含1000节点、5000链路的网络中,计算时间缩短37.2%,内存占用减少21.5%。该算法适用于网络拓扑发现、异常流量检测、故障定位及负载均衡优化等场景,为智能化局域网监控提供了有效支持。
84 5
|
4月前
|
存储 算法 安全
如何控制上网行为——基于 C# 实现布隆过滤器算法的上网行为管控策略研究与实践解析
在数字化办公生态系统中,企业对员工网络行为的精细化管理已成为保障网络安全、提升组织效能的核心命题。如何在有效防范恶意网站访问、数据泄露风险的同时,避免过度管控对正常业务运作的负面影响,构成了企业网络安全领域的重要研究方向。在此背景下,数据结构与算法作为底层技术支撑,其重要性愈发凸显。本文将以布隆过滤器算法为研究对象,基于 C# 编程语言开展理论分析与工程实践,系统探讨该算法在企业上网行为管理中的应用范式。
137 8
|
4月前
|
存储 监控 算法
解析公司屏幕监控软件中 C# 字典算法的数据管理效能与优化策略
数字化办公的时代背景下,企业为维护信息安全并提升管理效能,公司屏幕监控软件的应用日益普及。此软件犹如企业网络的 “数字卫士”,持续记录员工电脑屏幕的操作动态。然而,伴随数据量的持续增长,如何高效管理这些监控数据成为关键议题。C# 中的字典(Dictionary)数据结构,以其独特的键值对存储模式和高效的操作性能,为公司屏幕监控软件的数据管理提供了有力支持。下文将深入探究其原理与应用。
97 4
|
5月前
|
机器学习/深度学习 监控 算法
员工上网行为监控软件中基于滑动窗口的C#流量统计算法解析​
在数字化办公环境中,员工上网行为监控软件需要高效处理海量网络请求数据,同时实时识别异常行为(如高频访问非工作网站)。传统的时间序列统计方法因计算复杂度过高,难以满足低延迟需求。本文将介绍一种基于滑动窗口的C#统计算法,通过动态时间窗口管理,实现高效的行为模式分析与流量计数。
135 2
|
5月前
|
人工智能 运维 算法
基于 C# 深度优先搜索算法的局域网集中管理软件技术剖析
现代化办公环境中,局域网集中管理软件是保障企业网络高效运行、实现资源合理分配以及强化信息安全管控的核心工具。此类软件需应对复杂的网络拓扑结构、海量的设备信息及多样化的用户操作,而数据结构与算法正是支撑其强大功能的基石。本文将深入剖析深度优先搜索(Depth-First Search,DFS)算法,并结合 C# 语言特性,详细阐述其在局域网集中管理软件中的应用与实现。
126 3
|
3月前
|
监控 算法 数据处理
内网实时监控中的 C# 算法探索:环形缓冲区在实时数据处理中的关键作用
本文探讨了环形缓冲区在内网实时监控中的应用,结合C#实现方案,分析其原理与优势。作为固定长度的循环队列,环形缓冲区通过FIFO机制高效处理高速数据流,具备O(1)时间复杂度的读写操作,降低延迟与内存开销。文章从设计逻辑、代码示例到实际适配效果展开讨论,并展望其与AI结合的潜力,为开发者提供参考。
183 2
|
3月前
|
监控 算法 安全
公司电脑监控软件关键技术探析:C# 环形缓冲区算法的理论与实践
环形缓冲区(Ring Buffer)是企业信息安全管理中电脑监控系统设计的核心数据结构,适用于高并发、高速率与短时有效的多源异构数据处理场景。其通过固定大小的连续内存空间实现闭环存储,具备内存优化、操作高效、数据时效管理和并发支持等优势。文章以C#语言为例,展示了线程安全的环形缓冲区实现,并结合URL访问记录监控应用场景,分析了其在流量削峰、关键数据保护和高性能处理中的适配性。该结构在日志捕获和事件缓冲中表现出色,对提升监控系统效能具有重要价值。
97 1
|
4月前
|
存储 监控 算法
基于 C# 的局域网计算机监控系统文件变更实时监测算法设计与实现研究
本文介绍了一种基于C#语言的局域网文件变更监控算法,通过事件驱动与批处理机制结合,实现高效、低负载的文件系统实时监控。核心内容涵盖监控机制选择(如事件触发机制)、数据结构设计(如监控文件列表、事件队列)及批处理优化策略。文章详细解析了C#实现的核心代码,并提出性能优化与可靠性保障措施,包括批量处理、事件过滤和异步处理等技术。最后,探讨了该算法在企业数据安全监控、文件同步备份等场景的应用潜力,以及未来向智能化扩展的方向,如文件内容分析、智能告警机制和分布式监控架构。
125 3
|
4月前
|
存储 监控 算法
局域网上网记录监控的 C# 基数树算法高效检索方案研究
在企业网络管理与信息安全领域,局域网上网记录监控是维护网络安全、规范网络行为的关键举措。随着企业网络数据量呈指数级增长,如何高效存储和检索上网记录数据成为亟待解决的核心问题。基数树(Trie 树)作为一种独特的数据结构,凭借其在字符串处理方面的卓越性能,为局域网上网记录监控提供了创新的解决方案。本文将深入剖析基数树算法的原理,并通过 C# 语言实现的代码示例,阐述其在局域网上网记录监控场景中的具体应用。
124 7
|
4月前
|
存储 监控 算法
基于 C# 时间轮算法的控制局域网上网时间与实践应用
在数字化办公与教育环境中,局域网作为内部网络通信的核心基础设施,其精细化管理水平直接影响网络资源的合理配置与使用效能。对局域网用户上网时间的有效管控,已成为企业、教育机构等组织的重要管理需求。这一需求不仅旨在提升员工工作效率、规范学生网络使用行为,更是优化网络带宽资源分配的关键举措。时间轮算法作为一种经典的定时任务管理机制,在局域网用户上网时间管控场景中展现出显著的技术优势。本文将系统阐述时间轮算法的核心原理,并基于 C# 编程语言提供具体实现方案,以期深入剖析该算法在局域网管理中的应用逻辑与实践价值。
103 5