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

简介:

这节,我们来看看一下什么了,来看看图的遍历吧!

首先,搞清楚,图的遍历的基本的含义了。

图的遍历是指从图中的某个顶点出发,按照某种顺序访问图中的每个顶点,使每个顶点被访问一次且仅一次。图的遍历与树的遍历操作功能相似。图的遍历是图的一种基本操作,并且图的许多其他操作都是建立在遍历操作的基础之上的。遍历示意图,如图所示:

然而,图的遍历要比树的遍历复杂得多。这是因为图中的顶点之间是多对多的关系,图中的任何一个顶点都可能和其它的顶点相邻接。所以,在访问了某个顶点之后, 从该顶点出发, 可能沿着某条路径遍历之后, 又回到该顶点上。 例如,在下图中,由于图中存在回路,因此在访问了 A、B、C、D、E之后,沿着边<E,A>为图中顶点的数目。数组中元素的初始值全为 0,表示顶点都没有被访问过,如果顶点vi 被访问,visited[i-1]为 1。

图的遍历有深度优先遍历和广度优先遍历两种方式,它们对图和网都适用。 

首先,介绍了一些优先遍历。

图的深度优先遍历(Depth_First Search)类似于树的先序遍历,是树的先序遍历的推广。

我们先回顾一下树的先序遍历,如图所示:

他先序遍历结果是ABDEFCFG。

那图的图的深度优先遍历,究竟是那样的。

假设初始状态是图中所有顶点未曾被访问过, 则深度优先遍历可从图中某个顶点v出发,访问此顶点,然后依次从v的未被访问的邻接顶点出发深度优先遍历图,直至图中所有和v路径相通的顶点都被遍历过。若此时图中尚有未被访问的顶点,则另选图中一个未被访问的顶点作为起始点,重复上述过程,直到图中所有顶点都被访问到为止。

下图(a)所示的无向图的深度优先遍历的过程如下图(b)所示。假设从顶点 v1出发,在访问了顶点 v1之后,选择邻接顶点 v2,因为 v2未被访问过,所以从 v2出发进行深度优先遍历。依次类推,接着从 v4、v8、v5出发进行深度优先遍历。当访问了 v5之后,由于 v5的邻接顶点 v2和 v8都已被访问,所以遍历退回到 v8。由于同样的理由,遍历继续退回到 v4、v2 直到 v1。由于 v1 的另一个邻接顶点 v3未被访问,所以又从 v3开始进行深度优先遍历,这样得到该图的深度优先遍历的顶点序列v1→v2→v4→v8→v5→v3→v6→v7。

显然,这是一个递归的过程。下面以无向图的邻接表存储结构为例来实现图的深度优先遍历算法。在类中增设了一个整型数组的成员字段visited,它的初始值全为 0, 表示图中所有的顶点都没有被访问过。 如果顶点vi被访问, visited[i-1]为1。并且,把该算法作为无向图的邻接表类 GraphAdjList<T>的成员方法。

由于增设了成员字段 visited,所以在类的构造器中添加以下代码。

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;
}

//以下为添加的代码

//所有的结点,都没有访问过。 都赋值为0
visited = new int[adjList.Length];
for (int i = 0; i < visited.Length; ++i)
{
visited[i] = 0;
}
}

由于,他是循环遍历,他的时间的复杂度是O(n).

无向图的深度优先遍历算法的实现如下:   
public void DFS()
{
for (int i = 0; i < visited.Length; ++i)
{
if (visited[i] == 0)
{
DFSAL(i);
}
}
}

//从某个顶点出发进行深度优先遍历
public void DFSAL(int i)
{
visited[i] = 1;
adjListNode<T> p = adjList[i].FirstAdj;

while (p != null)
{
if (visited[p.Adjvex] == 0)
{
DFSAL(p.Adjvex);
}

p = p.Next;
}
}

分析上面的算法,在遍历图时,对图中每个顶点至多调用一次DFS方法,因为一旦某个顶点被标记成已被访问,就不再从它出发进行遍历。因此,遍历图的过程实质上是对每个顶点查找其邻接顶点的过程。 其时间复杂度取决于所采用的存储结构。当图采用邻接矩阵作为存储结构时,查找每个顶点的邻接顶点的时间复杂度为O(n2),其中,n为图的顶点数。而以邻接表作为图的存储结构时,查找邻接顶点的时间复杂度为O(e),其中,e为图中边或弧的数目。因此,当以邻接表作为存储结构时,深度优先遍历图的时间复杂度为O(n+e)。具体情况,如图所示:

下面介绍广度遍历。

图的广度优先遍历(Breadth_First Search)类似于树的层序遍历。 我们回顾一下树的层次遍历,如图所示:

树的层次遍历结果为ABCDEFG。

那图的光序遍历为

假设从图中的某个顶点 v 出发,访问了 v 之后,依次访问 v 的各个未曾访问的邻接顶点。然后分别从这些邻接顶点出发依次访问它们的邻接顶点,并使“先被访问的顶点的邻接顶点”先于“后被访问的顶点的邻接顶点”被访问,直至图中所有已被访问的顶点的邻接顶点都被访问。若此时图中尚有顶点未被访问,则另选图中未被访问的顶点作为起点,重复上述过程,直到图中所有的顶点都被访问为止。换句话说,广度优先遍历图的过程是以某个顶点 v 作为起始点,由近至远,依次访问和 v 有路径相通且路径长度为 1,2,…的顶点。

图(a)所示的无向图的广度优先遍历的过程如图(b)所示。假设从顶点 v1开始进行广度优先遍历,首先访问顶点 v1和它的邻接顶点 v2和 v3,然后依次访问 v2 的邻接顶点 v4 和 v5,以及 v3 的邻接顶点 v6 和 v7,最后访问 v4b的邻接顶点 v8。由于这些顶点的邻接顶点都已被访问,并且图中所有顶点都已被访问,由此完成了图的遍历,得到的顶点访问序列为:v1→v2→v3→v4→v5→v6→v7→v8,其遍历过程如下图(b)所示。


和深度优先遍历类似,在广度优先遍历中也需要一个访问标记数组,我们采用与深度优先遍历同样的数组。并且,为了顺序访问路径长度为 1,2,…的顶点,需在算法中附设一个队列来存储已被访问的路径长度为 1,2,…的顶点。 以邻接表作为存储结构的无向图的广度优先遍历算法的实现如下, 队列是循环顺序队列。

public void BFS()
{
for (int i = 0; i < visited.Length; ++i)
{

//所有结点的都没有遍历
if (visited[i] == 0)
{
BFSAL(i);
}
}
}

//从某个顶点出发进行广度优先遍历
public void BFSAL(int i)
{
visited[i] = 1;
CSeqQueue<int> cq = new CSeqQueue<int>(visited.Length);

while (!cq.IsEmpty())
{
int k = cq.Out();
adjListNode<T> p = adjList[k].FirstAdj;

while (p != null)
{
if (visited[p.Adjvex] == 0)
{
visited[p.Adjvex] = 1;
cq.In(p.Adjvex);
}

p = p.Next;
}
}
}

算法的复杂度是O(n2),具体情况,如图所示:

 

cq.In(i);

分析上面的算法,每个顶点至多入队列一次。遍历图的过程实质上是通过边或弧查找邻接顶点的过程,因此,广度优先遍历算法的时间复杂度与深度优先遍历相同,两者的不同之处在于对顶点的访问顺序不同。

这就是图的遍历,极其算法的实现,下届,我们讨论图的应用。

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