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

简介:

  好久, 没写blog了,今天,多写点。 

    上节说到那里了,是不是说图的遍历,这节,我们来通过图的具体的应用了。

    首先,看看最小生成树的应用了。 什么是最小生成树了?

   由生成树的定义可知,无向连通图的生成树不是唯一的,对连通图的不同遍历就得到不同的生成树。图 b 所示是图 (a)所示的无向连通图的部分生成树。

   

 所谓最小生成树是 如果是一个无向连通网, 那么它的所有生成树中必有一棵边的权值总和最小的生成树,我们称这棵生成树为最小代价生成树(Minimum Cost Spanning Tree).

许多应用问题都是一个求无向连通网的最小生成树问题。例如,要在 n个城市之间铺设光缆, 铺设光缆的费用很高, 并且各个城市之间铺设光缆的费用不同。一个目标是要使这 n个城市的任意两个之间都可以直接或间接通信, 另一个目标是要使铺设光缆的总费用最低。如果把 n个城市看作是图的 n个顶点,两个城市之间铺设的光缆看作是两个顶点之间的边, 这实际上就是求一个无向连通网的最小生成树问题。

由最小生成树的定义可知, 构造有 n个顶点的无向连通网的最小生成树必须满足以下三个条件: 

(1)构造的最小生成树必须包括 n个顶点;
(2)构造的最小生成树有且仅有 n-1条边;
(3)构造的最小生成树中不存在回路。
构造最小生成树的方法有许多种,典型的方法有两种,一种是普里姆(Prim)算法,一种是克鲁斯卡尔(Kruskal)算法。

 

一普里姆(Prim)算法

 

假设 G=(V,E)为一无向连通网,其中,V 为网中顶点的集合,E 为网中边的集合。设置两个新的集合 U 和 T,其中,U 为 G 的最小生成树的顶点的集合,T 为 G 的最小生成树的边的集合。普里姆算法的思想是:令集合 U 的初值为 U={u1}(假设构造最小生成树时从顶点 u1开始) ,集合 T 的初值为 T={}。从所有的顶点 u∈U 和顶点 v∈V-U 的带权边中选出具有最小权值的边(u,v) ,将顶点 v 加入集合 U 中,将边(u,v)加入集合 T 中。如此不断地重复直到 U=V 时,最小生成树构造完毕。此时,集合 U 中存放着最小生成树的所有顶点,集合 T中存放着最小生成树的所有边。

以下图(a)为例,说明用普里姆算法构造图的无向连通网的最小生成树的过程。

 

为了分析问题的方便,无向连通网如图(a)所示。 初始时, 算法的集合 U={A}, 集合 V-U={B,C,D,E}, 集合 T={},如图(b)所示。在所有 u 为集合 U 中顶点、v 为集合 V-U 中顶点的边(u,v)中寻找具有最小权值的边,寻找到的边是(A,D),权值为 20,把顶点 B 加入到集合U 中, 把边(A,D)加入到集合 T 中, 如图 (c)所示。 在所有 u为集合 U 中顶点、v 为集合 V-U 中顶点的边(u,v)中寻找具有最小权值的边, 寻找到的边是(D,E), 权值为 10,把顶点 E 加入到集合 U 中,把边(D,E)加入到集合 T 中,如图(d)所示。随后依次从集合 V-U 中加入到集合 U 中的顶点为 B、C,依次加入到集合T中的边为(A,B)(权值为 60) 、(E,C) (权值为 70) ,分别如图 (e)、(f)所示。最后得到的图(f)所示就是原无向连通网的最小生成树。

本书以无向网的邻接矩阵类 NetAdjMatrix<T>来实现普里姆算法。NetAdjMatrix<T>类的成员字段与无向图邻接矩阵类 GraphAdjMatrix<T>的成员字段一样,不同的是,当两个顶点间有边相连接时,matirx 数组中相应元素的值是边的权值,而不是 1

无向网邻接矩阵类 NetAdjMatrix<T>源代码的实现如下所示:


public class NetAdjMatrix<T> : IGraph<T>//继承与图形的接口  
    { 
        private Node<T>[] nodes;      //顶点数组     存取相应的结点的 泛型数组
        private int numEdges;         //边的数目     上图边数字是6
        private int[,] matrix;       //邻接矩阵数组      存取相应的互相的权值
 
        //构造器  进行数据的初始化  边的数目是0
        public NetAdjMatrix (int n) 
        { 
            nodes = new Node<T>[n]; 
            matrix = new int[n,n]; 
            numEdges = 0; 
        } 
 
        //获取索引为index的顶点的信息    算法的时间复杂度是O(1)
        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, int v) 
         { 
           matrix[index1, index2] = v; 
         } 
          //获取顶点的数目 算法的时间的复杂度是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) 
            { 
                //如果顶点nd与v相等,则v是图的顶点,返回索引值 
                if (nodes[i].Equals(v)) 
                { 
                    return i; 
                } 
  } 
            return i; 
        } 
 
        //在顶点v1、v2之间添加权值为v的边 
        //添加相应的权值的v的边,  这是一个对称矩阵。

        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; 
            } 
 
            //矩阵是对称矩阵 
            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)] != int.MaxValue) 
            { 
                //矩阵是对称矩阵 
                matrix[GetIndex(v1), GetIndex(v2)] = int.MaxValue; 
                matrix[GetIndex(v2), GetIndex(v1)] = int.MaxValue; 
                --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)] != int.MaxValue) 
            { 
                return true; 
            } 
            Else  //v1和v2之间不存在边 
            { 
                return false; 
            } 
        } 
} 

 具体如图所示:

 

为实现普里姆算法, 需要设置两个辅助一维数组 lowcost和 closevex, lowcost用来保存集合 V-U 中各顶点与集合 U 中各顶点构成的边中具有最小权值的边的权值;closevex 用来保存依附于该边的在集合 U 中的顶点。假设初始状态时,U={u1}(u1为出发的顶点) ,这时有 lowcost[0]=0,它表示顶点 u1已加入集合 U中。数组 lowcost 元素的值是顶点 u1 到其他顶点所构成的直接边的权值。然后不断选取权值最小的边(ui,uk)(ui∈U,uk∈V-U),每选取一条边,就将 lowcost[k]置为 0,表示顶点 uk 已加入集合 U 中。由于顶点 uk 从集合 V-U 进入集合 U 后,这两个集合的内容发生了变化, 就需要依据具体情况更新数组lowcost和closevex中部分元素的值。把普里姆算法 PrimNetAdjMatrix<T>类的成员方法,实现的源代码如下:


public int[] Prim() 
    { 
        int[] lowcost = new int[nodes.Length];   //权值数组 保存权值的数组
        int[] closevex = new int[nodes.Length];  //顶点数组 保存 相应各个顶点的数组
        int mincost = int.MaxValue;              //最小权值 默认是 int的最大值 表示无穷大
 
        //辅助数组初始化   对摸个  权值数组赋值   保存 最小值
        for (int i = 1; i < nodes.Length; ++i) 
        { 
            lowcost[i] = matrix[0, i]; 
            closevex[i] = 0; 
        } 
 
        //某个顶点加入集合U 
        lowcost[0] = 0; 
        closevex[0] = 0; 
       //判断最小的权值通过的顶点的循环就此开始
      for(int i=0; i<nodes.Length; ++i) 
        { 
            int k = 1; 
            int j = 1; 
 
            //选取权值最小的边和相应的顶点 
            while(j < nodes.Length) 
            { 
                if (lowcost[j] < mincost && lowcost[j] != 0) 
                { 
                    k = j; 
                } 
                ++j; 
            } 
 
            //新顶点加入集合U 
            lowcost[k] = 0; 
 
            //重新计算该顶点到其余顶点的边的权值    
            for (j = 1; j < nodes.Length; ++j) 
            { 
                if (matrix[k, j] < lowcost[j]) 
                { 
                    lowcost[j] = matrix[k, j]; 
                    closevex[j] = k; 
                } 
            } 
        } 
 
        return closevex; 
  
} 
//我们明显的看出来,由于用到了双重循环,其算法的时间的复杂度是O(n^2)

具体实现,如图所示:

 

 

在普里姆算法中,第一个for循环的执行次数为n-1,第二个for循环中又包括了一个while循环和一个for循环,执行次数为 2(n-1)2,所以普里姆算法的时间复杂度为O(n2)。

这节,我们队图的引用做了一个抛砖引玉的介绍,主要是普利姆算法,解决 最小生成树问题。下节,我们介绍一下克鲁斯卡尔算法解决最小生成树的问题,和其他的应用。对图做一个总结等等。



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