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

简介:

这节,我们来重点讨论一下 这个树形结构的相应的源代码的实现了。

真的我们首先介绍一下无向图邻接表类的实现来说明图的邻接表类的实现。 

无向图邻接表的邻接表结点类 adjListNode<T>有两个成员字段,一个是1adjvex,存储邻接顶点的信息,类型是整型;一个是 next,存储下一个邻接表结点的地址,类型是 adjListNode<T>。adjListNode<T>的实现如下所示。

public class adjListNode<T>
{
private int adjvex; //邻接顶点,连接定点
private adjListNode<T> next; //下一个邻接表结点  指向邻接表结点 

//邻接顶点属性
public int Adjvex
{
get
{

return adjvex;
}
set
{
adjvex = value;
}
}

//下一个邻接表结点属性
public adjListNode<T> Next
{
get
{
return next;
}
set
{
next = value;
}
}

//构造器    指向 邻接顶点

//下一个结点为空。
public adjListNode(int vex)
{
adjvex = vex;
next = null;
}

具体情况,如图所示:


}

 而具体的图连接表应该是这样的。

无向图邻接表的顶点结点类 VexNode<T>有两个成员字段,一个 data,它存储图的顶点本身的信息,类型是 Node<T>;一个是 firstAdj,存储顶点的邻接表的第1个结点的地址,类型是 adjListNode<T>。VexNode<T>的实现如下所示。

public class VexNode<T>
{
private Node<T> data; //图的顶点   存储的图的顶点
private adjListNode<T> firstAdj; //邻接表的第1个结点

//图的顶点属性
public Node<T> Data
{
get
{
return data;
}
set

{
data = value;
}
}

//邻接表的第1个结点属性
public adjListNode<T> FirstAdj
{
get
{
return firstAdj;
}
set
{
firstAdj = value;
}
}

//构造器
public VexNode()
{
data = null;
firstAdj = null;
}

//构造器
public VexNode(Node<T> nd)
{
data = nd;
firstAdj = null;
}

//构造器
public VexNode(Node<T> nd, adjListNode<T> alNode)
{
data = nd;
firstAdj = alNode;
}

这个具体的情况,如图所示:


}

无向图邻接表类 GraphAdjList<T>有一个成员字段 adjList, 表示邻接表数组,数组元素的类型是 VexNode<T>。 GraphAdjList<T>实现了接口 IGraph<T>中的方法。与无向图邻接矩阵类 GraphAdjMatrix<T>一样,GraphAdjList<T>实现了两个成员方法 IsNode 和 GetIndex。功能与 GraphAdjMatrix<T>一样。无向图表GraphAdjList<T>的源代码实现如下所示。

public class GraphAdjList<T> : IGraph<T>
{
//邻接表数组
private VexNode<T>[] adjList;

//索引器
public VexNode<T> this[int index]
{
get
{
return adjList[index];
}
set
{
adjList[index] = value;
}
}

//构造器 构建成一个相应的图表
public GraphAdjList(Node<T>[] nodes)
{
adjList = new VexNode<T>[nodes.Length];
for (int i = 0; i < nodes.Length; ++i )
{
adjList[i].Data = nodes[i];
adjList[i].FirstAdj = null;
}
}

//获取顶点的数目
public int GetNumOfVertex()
{
return adjList.Length;


算法思路:求无向图的顶点数比较简单,直接返回 adjList 数组的长度就可以了。算法的复杂度是O(1)
//获取边的数目

public int GetNumOfEdge()
{
int i = 0;

//遍历邻接表数组
foreach (VexNode<T> nd in adjList)
{
adjListNode<T> p = nd.FirstAdj;

while (p != null)
{
++i;
p = p.Next
}
}

return i / 2;
}

算法思路:求无向图的边数比求顶点数要复杂一些,需要求出所有顶点的邻接表的结点的个数,然后除以2。算法的时间的复杂度是O(n2)


//判断v是否是图的顶点
public bool IsNode(Node<T> v)
{
//遍历邻接表数组
foreach (VexNode<T> nd in adjList)
{
//如果v等于nd的data,则v是图中的顶点,返回true
if (v.Equals(nd.Data))
{
return true;
}
}

return false;
}

算法思路:首先判断顶点 v1 和 v2 是否是图的顶点。如果 v1 和 v2 不是图的顶点,不作处理。否则,在顶点 v1(或 v2)的邻接表中查找是否存在 adjVex的值等于 v2(或 v1)在 adjList 中的序号的结点,如果存在,则返回 true,否则返回 false。


//获取顶点v在邻接表数组中的索引
public int GetIndex(Node<T> v)
{
int i = -1;

//遍历邻接表数组
for (i = 0; i < adjList.Length; ++i)
{
//邻接表数组第i项的data值等于v,则顶点v的索引为i
if (adjList[i].Data.Equals(v))
{
return i;
}
}
return i;
}

//在顶点v1和v2之间添加权值为v的边
public void SetEdge(Node<T> v1, Node<T> v2,int v)
{
//v1或v2不是图的顶点或者v1和v2之间存在边
if (!IsNode(v1) || !IsNode(v2) || IsEdge(v1,v2))
{
Console.WriteLine("Node is not belong to Graph!");
return;
}

//权值不对
if(v != 1)
{
Console.WriteLine("Weight is not right!");
return;
}

//处理顶点v1的邻接表
adjListNode<T> p = new adjListNode<T>(GetIndex(v2));

//顶点v1没有邻接顶点
if (adjList[GetIndex(v1)].FirstAdj == null)
{
adjList[GetIndex(v1)].FirstAdj = p;
}
//顶点v1有邻接顶点
else
{
p.Next = adjList[GetIndex(v1)].FirstAdj;
adjList[GetIndex(v1)].FirstAdj = p;
}

//处理顶点v2的邻接表
p = new adjListNode<T>(GetIndex(v1));

//顶点v2没有邻接顶点
if (adjList[GetIndex(v2)].FirstAdj == null)
{
adjList[GetIndex(v2)].FirstAdj = p;
}
//顶点v1有邻接顶点
else
{
p.Next = adjList[GetIndex(v2)].FirstAdj;

adjList[GetIndex(v2)].FirstAdj = p;
}
}

算法思路: 首先判断顶点 v1 和 v2 是否是图的顶点和 v1 和 v2 是否存在边。如果 v1 和 v2 不是图的顶点和 v1 和 v2 存在边,不作处理。然后,判断 v 的值是否为1, 为1不作处理。 否则, 先分配一个邻接表结点, 其adjvex域是v2在adjList数组中的索引号,然后把该结点插入到顶点 v1 的邻接表的表头;然后再分配一个邻接表结点,其 adjvex 域是 v1 在 adjList 数组中的索引号,然后把该结点插入到顶点 v2 的邻接表的表头。
本算法是把邻接表结点插入到顶点邻接表的表头,当然,也可以插入到邻接表的表尾,或者按照某种要求插入,只是对插入这个操作而言,在表的头部插入是最简单的,而本书在后面关于图的处理,如图的深度优先遍历和广度优先遍历等,对图的顶点没有特殊要求,所以采用了在邻接表的头部插入结点。如果对图的顶点有特殊要求,则需要按照一定的要求进行插入,需要修改这里的代码。由于存在循环遍历,所以的算法的时间的复杂度是O(n2)


//删除顶点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 (IsEdge(v1,v2))
{
//处理顶点v1的邻接表中的顶点v2的邻接表结点
adjListNode<T> p = adjList[GetIndex(v1)].FirstAdj;
adjListNode<T> pre = null;

while (p != null)
{
if (p.Adjvex != GetIndex(v2))
{
pre = p;
p = p.Next;
}
}

pre.Next = p.Next;

//处理顶点v2的邻接表中的顶点v1的邻接表结点
p = adjList[GetIndex(v2)].FirstAdj;
pre = null;

while (p != null)
{
if (p.Adjvex != GetIndex(v1))
{
pre = p;
p = p.Next;
}
}

 

算法思路:首先判断顶点 v1 和 v2 是否是图的顶点以及 v1 和 v2 是否存在边。如果 v1 和 v2 不是图的顶点或 v1 和 v2 不存在边,不作处理。否则,先在顶点 v1 的邻接表中删除 adjVex 的值等于顶点 v2 在 adjList 数组中的序号结点,然后删除顶点 v2 的邻接表中 adjVex 的值等于顶点 v1 在 adjList 数组中的序号结点。由于用到了遍历的,时间的复杂度是O(n2)

 

//判断v1和v2之间是否存在边
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;
}

adjListNode<T> p = adjList[GetIndex(v1)].FirstAdj;
while (p != null)
{
if (p.Adjvex == GetIndex(v2))
{
return true;
}

p = p.Next;
}

return false;
}

具体情况,如图所示:


}

以上就是图的基本实现的论述,下届,我们继续介绍图遍历,敬请关注。。。。。。。。。。。。。。。。

目录
相关文章
|
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