精华内容
下载资源
问答
  • 该程序运行为实现设计我们的学校的平面图,包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。 以方便进一步初次来观光和了解我们学校,找到...
  • 数据结构:图结构的实现

    万次阅读 多人点赞 2018-02-07 19:44:45
    图是一种很重要的数据结构解释。

    数据结构:图结构的实现

    图(Graph)是由顶点和连接顶点的边构成的离散结构。在计算机科学中,图是最灵活的数据结构之一,很多问题都可以使用图模型进行建模求解。例如:生态环境中不同物种的相互竞争、人与人之间的社交与关系网络、化学上用图区分结构不同但分子式相同的同分异构体、分析计算机网络的拓扑结构确定两台计算机是否可以通信、找到两个城市之间的最短路径等等。

    额,我都不研究这些问题。之所以重新回顾数据结构,仅仅是为了好玩。图(Graph)通常会放在树(Tree)后面介绍,树可以说只是图的特例,但是我觉得就基础算法而言,树比图复杂很多,而且听起来也没什么好玩的(左左旋、左右旋、右右旋、右左旋,好无聊~)。因此,我写的第一篇数据结构的笔记就从图开始。

    1 图的概念

    1.1 图的基础概念串讲

    图的结构很简单,就是由顶点 V V V 集和边 E E E 集构成,因此图可以表示成 G = ( V , E ) G=(V, E) G=(V,E)
    图1-1:无向图
    图1-1:无向图1

    图1-1就是无向图,我们可以说这张图中,有点集 V = { 1 , 2 , 3 , 4 , 5 , 6 } V=\{1, 2, 3, 4, 5, 6\} V={1,2,3,4,5,6},边集 E = { ( 1 , 2 ) , ( 1 , 5 ) , ( 2 , 3 ) , ( 2 , 5 ) , ( 3 , 4 ) , ( 4 , 5 ) , ( 4 , 6 ) } E=\{(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)\} E={(1,2),(1,5),(2,3),(2,5),(3,4),(4,5),(4,6)} 。在无向图中,边 ( u , v ) (u, v) (u,v)和边 ( v , u ) (v, u) (v,u)是一样的,因此只要记录一个就行了。简而言之,对称。
    图1-2:有向图
    图1-2:有向图 2
    有向图也很好理解,就是加上了方向性,顶点 ( u , v ) (u, v) (u,v)之间的关系和顶点 ( v , u ) (v,u) (v,u)之间的关系不同,后者或许不存在。例如,地图应用中必须存储单行道的信息,避免给出错误的方向。

    加权图:与加权图对应的就是无权图,如果觉得不好听,那就叫等权图。如果一张图不含权重信息,我们就认为边与边之间没有差别。不过,具体建模的时候,很多时候都需要有权重,比如对中国重要城市间道路联系的建模,总不能认为从北京去上海和从北京去广州一样远(等权)。

    还有很多细化的概念,有兴趣的自己了解咯。我觉得就没必要单独拎出来写,比如:无向图中,任意两个顶点间都有边,称为无向完全图;加权图起一个新名字,叫网(network)……然而,如无必要,毋增实体。

    两个重要关系:

    • 邻接(adjacency):邻接是两个顶点之间的一种关系。如果图包含 ( u , v ) (u,v) (u,v),则称顶点 v v v与顶点 u u u邻接。当然,在无向图中,这也意味着顶点 u u u与顶点 v v v邻接。
    • 关联(incidence):关联是边和顶点之间的关系。在有向图中,边 ( u , v ) (u,v) (u,v)从顶点 u u u开始关联到 v v v,或者相反,从 v v v关联到 u u u。注意,有向图中,边不一定是对称的,有去无回是完全有可能的。

    细化关联这个概念,就有了顶点的入度(in-degree)出度(out-degree)。无向图中,顶点的度就是与顶点相关联的边的数目,没有入度和出度。在有向图中,我们以图1-2为例,顶点10有2个入度, 3 → 10 3\rightarrow10 310 11 → 10 11\rightarrow10 1110,但是没有从10指向其它顶点的边,因此顶点10的出度为0。

    路径(path):依次遍历顶点序列之间的边所形成的轨迹。注意,依次就意味着有序,先1后2和先2后1不一样。

    简单路径:没有重复顶点的路径称为简单路径。说白了,这一趟路里没有出现绕了一圈回到同一点的情况,也就是没有
    图1-3:四顶点的有向带环图
    图1-3:四顶点的有向带环图3

    :包含相同的顶点两次或者两次以上。图1-3中的顶点序列 &lt; 1 , 2 , 4 , 3 , 1 &gt; &lt;1,2,4,3,1&gt; <1,2,4,3,1>,1出现了两次,当然还有其它的环,比如 &lt; 1 , 4 , 3 , 1 &gt; &lt;1,4,3,1&gt; <1,4,3,1>

    无环图:没有环的图,其中,有向无环图有特殊的名称,叫做DAG(Directed Acyline Graph)(最好记住,DAG具有一些很好性质,比如很多动态规划的问题都可以转化成DAG中的最长路径、最短路径或者路径计数的问题)。
    下面这个概念很重要:
    图1-4:两个连通分支
    图1-4:两个连通分支

    连通的:无向图中每一对不同的顶点之间都有路径。如果这个条件在有向图里也成立,那么就是强连通的。图1-4中的图不是连通的,我丝毫没有侮辱你智商的意思,我只是想和你说,这图是我画的,顶点标签有点小,应该看到a和d之间没有通路。

    • 连通分支:不连通的图是由2个或者2个以上的连通分支的并。这些不相交的连通子图称为图的连通分支
      图1-5:有向图的连通分支
      图1-5:有向图的连通分支

    • 有向图的连通分支:将有向图的方向忽略后,任何两个顶点之间总是存在路径,则该有向图是弱连通的有向图的子图是强连通的,且不包含在更大的连通子图中,则可以称为图的强连通分支

    图1-5中, a a a e e e没有到 { b , c , d } \{b,c,d\} {b,c,d}中的顶点的路径,所以各自是独立的连通分支。因此,图1-5中的图有三个强连通分支,用集合写出来就是: { { a } , { e } , { b , c , d } } \{\{a\}, \{e\}, \{b, c, d\}\} {{a},{e},{b,c,d}}(已经用不同颜色标出)。

    图1-6:关节点
    图1-6:关节点

    关节点(割点):某些特定的顶点对于保持图或连通分支的连通性有特殊的重要意义。如果移除某个顶点将使图或者分支失去连通性,则称该顶点为关节点。如图1-6中的c。

    双连通图:不含任何关节点的图。
    关节点的重要性不言而喻。如果你想要破坏互联网,你就应该找到它的关节点。同样,要防范敌人的攻击,首要保护的也应该是关节点。在资源总量有限的前提下,找出关节点并给予特别保障,是提高系统整体稳定性和鲁棒性的基本策略。

    桥(割边):和关节点类似,删除一条边,就产生比原图更多的连通分支的子图,这条边就称为割边或者

    1.2 一些有趣的图概念

    这一部分属于图论的内容,基础图算法不会用到,但是我觉得挺有意思的,小记如下。
    同构4:图看起来结构不一样,但它是一样的。假定有 G 1 G_1 G1 G 2 G_2 G2,那么你只要确认对于 G 1 G_1 G1中的所有的两个相邻点 a a a b b b,可以通过某种方式 f f f映射到 G 2 G_2 G2,映射后的两个点 f ( a ) f(a) f(a) f ( b ) f(b) f(b)也是相邻的。换句话说,当两个简单图同构时,两个图的顶点之间保持相邻关系的一一对应。
    图1-7:图的同构
    图1-7:图的同构

    图1-7就展示了图的同构,这里顶点个数很少判断图的同构很简单。我们可以把v1看成u1,自然我们会把u3看出v3。用数学的语言就是 f ( u 1 ) = v 1 f(u_1)=v_1 f(u1)=v1 f ( u 3 ) = v 3 f(u_3)=v_3 f(u3)=v3。u1的另外一个连接是到u2,v1的另外一个连接是到v4,不难从相邻顶点的关系验证 f ( u 2 ) = v 4 f(u_2)=v_4 f(u2)=v4 f ( u 4 ) = v 2 f(u_4)=v_2 f(u4)=v2

    欧拉回路(Euler Circuit):小学数学课本上的哥尼斯堡七桥问题,能不能从镇里的某个位置出发不重复的经过所有桥(边)并且返回出发点。这也就小学的一笔画问题,欧拉大神解决里这个问题,开创了图论。

    结论很简单:至少2个顶点的连通多重图存在欧拉回路的充要条件是每个顶点的度都是偶数。证明也很容易,大家有兴趣可以阅读相关资料。结论也很好理解,从某个起点出发,最后要回起点,中间无论路过多少次起点,都会再次离开,进、出的数目必然相等,故一定是偶数。

    哈密顿回路(Hamilton Circuit):哈密顿回路条件就比欧拉回路严格一点,不能重复经过点。你可能会感到意外,对于欧拉回路,我们可以轻而易举地回答,但是我们却很难解决哈密顿回路问题,实际上它是一个NP完全问题

    这个术语源自1857年爱尔兰数学家威廉·罗万·哈密顿爵士发明的智力题。哈密顿的智力题用到了木质十二面体(如图1-8(a)所示,十二面体有12个正五边形表面)、十二面体每个顶点上的钉子、以及细线。十二面体的20个顶点用世界上的不同城市标记。智力题要求从一个城市开始,沿十二面体的边旅行,访问其他19个城市,每个恰好一次,最终回到第一个城市。
    图1-8:哈密顿回路问题
    图1-8:哈密顿回路问题
    因为作者不可能向每位读者提供带钉子和细线的木质十二面体,所以考虑了一个等价的问题:对图1-8(b)的图是否具有恰好经过每个顶点一次的回路?它就是对原题的解,因为这个平面图同构于十二面体顶点和边。

    著名的**旅行商问题(TSP)**要求旅行商访问一组城市所应当选取的最短路线。这个问题可以归结为求完全图的哈密顿回路,使这个回路的边的权重和尽可能的小。同样,因为这是个NP完全问题,最直截了当的方法就检查所有可能的哈密顿回路,然后选择权重和最小的。当然这样效率几乎难以忍受,时间复杂度高达 O ( n ! ) O(n!) O(n!)

    在实际应用中,我们使用的启发式搜索等近似算法,可以完全求解城市数量上万的实例,并且甚至能在误差1%范围内估计上百万个城市的问题。

    关于旅行商问题目前的研究进展,可以到http://www.math.uwaterloo.ca/tsp/进一步了解。

    1.3 小结

    以为可以一带而过,结果写了那么多。也没什么好总结的了,当然这些也至是图论概念的一小部分,还有一些图可能我们以后也会见到,比如顺着图到网络流,就会涉及二分图,不过都很好理解,毕竟有图。

    2 图的表示

    2.1 邻接链表与邻接矩阵

    图最常见的表示形式为邻接链表邻接矩阵。邻接链接在表示稀疏图时非常紧凑而成为了通常的选择,相比之下,如果在稀疏图表示时使用邻接矩阵,会浪费很多内存空间,遍历的时候也会增加开销。但是,这不是绝对的。如果图是稠密图,邻接链表的优势就不明显了,那么就可以选择更加方便的邻接矩阵。

    还有,顶点之间有多种关系的时候,也不适合使用矩阵。因为表示的时候,矩阵中的每一个元素都会被当作一个表。

    2.1.1 存储问题

    如果使用邻接矩阵还要注意存储问题。矩阵需要 n 2 n^2 n2个元素的存储空间,声明的又是连续的空间地址。由于计算机内存的限制,存储的顶点数目也是有限的,例如:Java的虚拟机的堆的默认大小是物理内存的1/4,或者1G。以1G计算,那么创建一个二维的int[16384][16384]的邻接矩阵就已经超出内存限制了。含有上百万个顶点的图是很常见的, V 2 V^2 V2的空间是不能满足的。
    因此,偷个懒,如果对邻接矩阵感兴趣,可以自己找点资料。很容易理解的。

    2.1.2 邻接链表的实现

    邻接链表的实现会比邻接矩阵麻烦一点,但是邻接链表的综合能力,包括鲁棒性、拓展性都比邻接矩阵强很多。没办法,只能忍了。
    图1-9:邻接链表示意图
    图1-9:邻接链表示意图

    从图1-9不能看出邻接链表可以用线性表构成。顶点可以保持在数组或者向量(vector)中,邻接关系则用链表实现,利用链表高效的插入和删除,实现内存的充分利用。有利必有弊,邻接矩阵可以高效的判定两个顶点之间是否有邻接关系,邻接链表无疑要遍历一次链表。

    邻接链表的瓶颈在于链表的查找上,如果换成高效的查找结构,就可以进一步地提高性能。例如,把保存顶点邻接关系的链表换成通常以红黑树为基础set。如果一定要名副其实,就要叫成邻接集。类似的,顶点的保存也有“改进”方案。比如,使用vector通常用int表示顶点,也无法高效地进行顶点的插入删除。如果把顶点的保存换成链表,无疑可以高效地进行顶点的插入和删除,但是访问能力又会大打折扣。没错,我们可以使用set或者map来保存顶点信息。

    C++11中引入了以散列表为基础unordered_setunordered_map,就查找和插入而言,统计性能可能会高于红黑树,然而,散列表会带来额外的内存开销,这是值得注意的。

    具体问题,具体分析,图的结构不同,实现图的结构也应该随之不同。大概也是这个原因,像C++、Java、Python等语言,都不提供具体的Graph。举个例子,直接使用vector保存顶点信息,list保存邻接关系,使用的顶点id连续5。那么在添加边 O ( 1 ) O(1) O(1),遍历顶点的邻接关系 O ( V ) O(V) O(V)还有空间消耗 O ( V + E ) O(V+E) O(V+E)上都是最优的。当然,类似频繁删除边,添加边(不允许平行边),删除顶点,添加顶点,那么这种比较简易的结构就不太适合了。

    2.3 量化选择

    我们稍微量化一下稀疏图和稠密图的标准。当我们声称图的是稀疏的,我们近似地认为边的数量 ∣ E ∣ |E| E大致等于顶点的个数 ∣ V ∣ |V| V,在稠密图中,我们可以不难得到 ∣ E ∣ |E| E近似为 ∣ V 2 ∣ |V^2| V2。在此,我们不妨定义均衡图是边的数量为 ∣ V 2 ∣ / log ⁡ ∣ V ∣ |V^2|/\log |V| V2/logV的图。

    图算法中,根据图的结构,经常会有两个算法变种,时间复杂度也不尽相同。可能有一个是 O ( ( V + E ) log ⁡ V ) O((V+E)\log V) O((V+E)logV),另一个是 O ( V 2 + E ) O(V^2+E) O(V2+E)。选择哪个算法更为高效取决于图是否是稀疏的。

    图类型 O ( ( V + E ) log ⁡ V ) O((V+E)\log V) O((V+E)logV)比较关系 O ( V 2 + E ) O(V^2+E) O(V2+E)
    稀疏图: E E E O ( V ) O(V) O(V) O ( V log ⁡ V ) O(V\log V) O(VlogV)< O ( V 2 ) O(V^2) O(V2)
    均衡图: E E E O ( V 2 / log ⁡ V ) O(V^2/\log V) O(V2/logV) O ( V 2 + V log ⁡ V ) = O ( V 2 ) O(V^2+V\log V)=O(V^2) O(V2+VlogV)=O(V2)= O ( V 2 + V 2 / log ⁡ V ) = O ( V 2 ) O(V^2+V^2/\log V)=O(V^2) O(V2+V2/logV)=O(V2)
    稠密图: E E E O ( V 2 ) O(V^2) O(V2) O ( V 2 log ⁡ V ) O(V^2\log V) O(V2logV)> O ( V 2 ) O(V^2) O(V2)

    3 图的实现

    3.1 代码约定

    因为用Markdown,所以我怕有时候排版的时候空格出现问题,4空格调整太麻烦,加上可能4空格有时候不是特别紧凑,所以代码全部是2空格缩进。另外,我就不打算像教科书一样写那种一本正经的代码,拆成头文件加源文件。还有很多偷懒和不负责的地方,不过,换来了性能。还有,auto还是挺好用的,因此代码会用到少量C++11。

    3.2 想想需要什么功能

    3.2.1 图的数据结构

    就学习算法的目的而言,频繁添加和删除顶点是不需要的,因此代码实现时,为方便起见顶点仍然使用vector保存,边的话进阶点,使用set,这样就防止出现平行边了。还有,我比较放心自己,很多方法不加检查。还是那句话,具体问题,具体分析,具体实现。

    3.2.2 图的操作

    既然选择用vector+set,我们来考虑一下基本操作,至于那些后来算法用到的,后面再补充实现。

    数据成员:

    • 边的数量
    • 顶点的数量
    • vectorset构成的图结构

    功能:

    • 添加边
    • 删除边
    • 添加顶点
    • 删除顶点
    • 判断是否有邻接关系
    • 返回顶点的邻接集:不推荐直接使用这个,建议用迭代器
    • 迭代器begincbegin
    • 迭代器endcend

    其它

    • 构造:初始化n个顶点
    • 构造:从字符串读取文件中的图信息,便于加载图信息
    • 析构函数:都是使用STL和动态变量,不用我们操心
    • 数据成员的取值方法
    • 辅助方法:打印图

    3.3.3 声明与内联实现

    #include <iostream>
    #include <vector>
    #include <set>
    #include <list>
    #include <fstream>
    #include <limits>
    #include <queue>
    
    // 邻接集合
    typedef std::set<int> AdjSet;
    // 邻接集
    class Graph {
     protected:
      // 邻接表向量
      std::vector<AdjSet> vertices_;
      // 顶点数量
      int vcount_;
      // 边的数量
      int ecount_;
      bool directed_;
     public:
      Graph(bool directed = false)
        : ecount_(0), vcount_(0),
          vertices_(0), directed_(directed) {};
      Graph(int n, bool directed)
        : ecount_(0), vcount_(n),
          vertices_(n), directed_(directed) {};
      // 从文件中初始化
      Graph(const char *filename, bool directed);
      virtual ~Graph() {
        vertices_.clear();
        vcount_ = 0;
        ecount_ = 0;
      }
      // 取值函数
      virtual int vcount() const { return vcount_; };
      virtual int ecount() const { return ecount_; };
      virtual bool directed() const { return directed_; };
      // 某条边是否存在
      virtual bool IsAdjacent(const int &u, const int &v);
      // 约定:成功返回 0,不存在 -1,已存在 1
      // 添加边
      virtual int AddEdge(const int &u, const int &v);
      // 添加顶点
      virtual int AddVertex();
      // 删除边
      virtual int RemoveEdge(const int &u, const int &v);
      // 删除顶点
      virtual int RemoveVertex(const int &u);
      // 返回顶点的邻接集
      virtual std::set<int>& Adj(const int &u) { return vertices_[u]; }
      // 迭代器
      virtual AdjSet::const_iterator begin(const int u) { return vertices_[u].begin(); };
      virtual AdjSet::const_iterator end(const int u) { return vertices_[u].end(); };
      virtual AdjSet::const_iterator cbegin(const int u) const { return vertices_[u].cbegin(); };
      virtual AdjSet::const_iterator cend(const int u) const { return vertices_[u].cend(); };
    }; // class Graph
    

    3.3 开工

    因为图结构实现还是比较简单的,代码都很短。

    3.3.1 从文件中构造图

    文件格式,先顶点数量、边数量,然后顶点对表示边。缺省bool值默认无向
    例如

    6
    8
    0 1
    0 2
    0 5
    2 3
    2 4
    2 1
    3 5
    3 4
    

    代码实现:

    Graph::Graph(const char *filename, bool directed = false) {
      directed_ = directed;
      int a, b;
      // 默认能打开,如果想安全,使用if (!infile.is_open())作进一步处理
      std::ifstream infile(filename, std::ios_base::in);
      // 节点和边数量
      infile >> a >> b;
      vcount_ = a;
      ecount_ = b;
      vertices_.resize(vcount_);
      // 读取边
      for (int i = 0; i < ecount_; ++i) {
        infile >> a >> b;
        int v = a;
        int w = b;
        vertices_[v].insert(w);
        if (!directed_) {
          vertices_[w].insert(v);
        }
      }
      infile.close();
    }
    

    3.3.2 添加和删除顶点

    // 添加顶点
    int Graph::AddVertex() {
      std::set<int> temp;
      vertices_.push_back(temp);
      ++vcount_;
      return 0;
    }
    
    // 删除顶点
    int Graph::RemoveVertex(const int &u) {
      if (u > vertices_.size()) {
        return -1;
      }
      // 遍历图,寻找与顶点的相关的边
      // 无向图,有关的边一定在该顶点的邻接关系中
      if (!directed_) {
        int e = vertices_[u].size();
        vertices_.erase(vertices_.begin() + u);
        ecount_ -= e;
        --vcount_;
        return 0;
      } else {
        // 遍历图
        for (int i = 0; i < vertices_.size(); ++i) {
          RemoveEdge(i, u);
        }
        vertices_.erase(vertices_.begin() + u);
        --vcount_;
        return 0;
      }
      return -1;
    }
    

    3.3.3 添加和删除边

    // 添加边
    int Graph::AddEdge(const int &u, const int &v) {
      // 不绑安全带,使用需谨慎
      vertices_[u].insert(v);
      if (!directed_) {
        vertices_[v].insert(u);
      }
      ++ecount_;
      return 0;
    }
    
    // 删除边
    int Graph::RemoveEdge(const int &u, const int &v) {
      auto it_find = vertices_[u].find(v);
      if (it_find != vertices_[u].end()) {
        vertices_[u].erase(v);
        --ecount_;
      } else {
        return -1;
      }
      if (directed_) { return 0; }
      // 无向图删除反向边
      it_find = vertices_[v].find(u);
      if (it_find != vertices_[u].end()) {
        vertices_[v].erase(u);
      } else {
        // 人和人之间的信任呢?
        return -1;
      }
      return 0;
    }
    

    3.3.4 是否有邻接关系

    // 检查两个顶点之间是否有邻接关系
    bool Graph::IsAdjacent(const int &u, const int &v) {
      if (vertices_[u].count(v) == 1) {
        return true;
      }
      return false;
    }
    

    3.3.5 其它:打印图

    这个用到了cout,又考虑到非功能性方法,不建议放在类中。

    // 打印图
    void PrintGraph(const Graph &graph) {
      for (int i = 0; i < graph.vcount(); i++) {
        std::cout << i << " -->";
        for (auto it = graph.cbegin(i); it != graph.cend(i); ++it) {
          std::cout << " " << *it;
        }
        std::cout << std::endl;
      }
    }
    

    3.5 小结

    图是相当灵活的,我想这也是为什么STL库不提供Graph的原因。我们可以发现,利用STL的基础设施,我们可以很快的搭建Graph。至于选择什么基础设施,没有标准答案。对于不同的问题会有不同的最佳答案。我们只是演示,不对特定问题进行进行建模,可以不管什么性能,也没打算泛化(不造库,谢谢),不过分考虑实现和图操作分离问题。嗯,就这样咯,还是赶紧进入更加激动人心的图算法吧。

    后记

    我水平有限,错误难免,还望各位加以指正。

    参考资料

    1. Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest,等. 算法导论(原书第3版).
    2. Robert Sedgewick, Kevin Wayne. 算法(原书第4版).
    3. 邓俊辉. 数据结构(C++语言版)(第3版).
    4. Kenneth H.Rosen. Discrete Mathematics and Its Applications(Seventh Edition).
    5. 维基百科相关词条

    1. https://en.wikipedia.org/wiki/Graph_(discrete_mathematics) ↩︎

    2. https://en.wikipedia.org/wiki/Directed_graph ↩︎

    3. https://en.wikipedia.org/wiki/Directed_graph ↩︎

    4. 同构(isomorphism)这个词来自希腊语字根:“isos”表示相等;“morphe”表示形式。 ↩︎

    5. 注意这通常是可以做到的,这意味着我们只关注图的拓扑结构,不关心顶点id的意义。如果你非要在图中保存额外的信息,那么就应该使用树结构或者随机化的hash方案。 ↩︎

    展开全文
  • 30 个重要数据结构和算法完整介绍(建议收藏保存)

    千次阅读 多人点赞 2021-06-07 08:02:06
    数据结构和算法 (DSA)通常被认为...它包括 15 个最有用的数据结构和 15 个最重要的算法,可以帮助您在学习中和面试中取得好成绩并提高您的编程竞争力。后面等我还会继续对这些数据结构和算法进行进一步详细地研究讲解。

    在这里插入图片描述

    数据结构和算法 (DSA)
    通常被认为是一个令人生畏的话题——一种常见的误解。它们是技术领域最具创新性概念的基础,对于工作/实习申请者和有经验的程序员的职业发展都至关重要。掌握DSA意味着你能够使用你的计算和算法思维来解决前所未见的问题,并为任何科技公司的价值做出贡献(包括你自己的!)。通过了解它们,您可以提高代码的可维护性、可扩展性和效率。

    话虽如此,我决定在CSDN新星计划挑战期间将我所了解的数据结构和算法集中起来。本文旨在使 DSA 看起来不像人们认为的那样令人生畏。它包括 15 个最有用的数据结构和 15 个最重要的算法,可以帮助您在学习中和面试中取得好成绩并提高您的编程竞争力。后面等我还会继续对这些数据结构和算法进行进一步详细地研究讲解。

    目录

    一、数据结构

    1. 数组(Arrays)

    在这里插入图片描述

    数组是最简单也是最常见的数据结构。它们的特点是可以通过索引(位置)轻松访问元素。

    它们是做什么用的?

    想象一下有一排剧院椅。每把椅子都分配了一个位置(从左到右),因此每个观众都会从他将要坐的椅子上分配一个号码。这是一个数组。将问题扩展到整个剧院(椅子的行和列),您将拥有一个二维数组(矩阵)!

    特性

    • 元素的值按顺序放置,并通过从 0 到数组长度的索引访问;
    • 数组是连续的内存块;
    • 它们通常由相同类型的元素组成(这取决于编程语言);
    • 元素的访问和添加速度很快;搜索和删除不是在 O(1) 中完成的。

    2. 链表(Linked Lists)

    链表 1链表 2

    链表是线性数据结构,就像数组一样。链表和数组的主要区别在于链表的元素不存储在连续的内存位置。它由节点组成——实体存储当前元素的值和下一个元素的地址引用。这样,元素通过指针链接。

    它们是做什么用的?

    链表的一个相关应用是浏览器的上一页和下一页的实现。双链表是存储用户搜索显示的页面的完美数据结构。

    特性

    • 它们分为三种类型:单独的、双重的和圆形的;
    • 元素不存储在连续的内存块中;
    • 完美的优秀内存管理(使用指针意味着动态内存使用);
    • 插入和删除都很快;访问和搜索元素是在线性时间内完成的。

    3. 堆栈(Stacks)

    堆栈

    堆栈是一种抽象数据类型,它形式化了受限访问集合的概念。该限制遵循 LIFO(后进先出)规则。因此,添加到堆栈中的最后一个元素是您从中删除的第一个元素。

    堆栈可以使用数组或链表来实现。

    它们是做什么用的?

    现实生活中最常见的例子是在食堂中将盘子叠放在一起。位于顶部的板首先被移除。放置在最底部的盘子是在堆栈中保留时间最长的盘子。

    堆栈最有用的一种情况是您需要获取给定元素的相反顺序。只需将它们全部推入堆栈,然后弹出它们。

    另一个有趣的应用是有效括号问题。给定一串括号,您可以使用堆栈检查它们是否匹配。

    特性

    • 您一次只能访问最后一个元素(顶部的元素);
    • 一个缺点是,一旦您从顶部弹出元素以访问其他元素,它们的值将从堆栈的内存中丢失;
    • 其他元素的访问是在线性时间内完成的;任何其他操作都在 O(1) 中。

    4. 队列(Queues)

    队列 1
    队列 2
    队列是受限访问集合中的另一种数据类型,就像前面讨论的堆栈一样。主要区别在于队列是按照FIFO(先进先出)模型组织的:队列中第一个插入的元素是第一个被移除的元素。队列可以使用固定长度的数组、循环数组或链表来实现。

    它们是做什么用的?

    这种抽象数据类型 (ADT) 的最佳用途当然是模拟现实生活中的队列。例如,在呼叫中心应用程序中,队列用于保存等待从顾问那里获得帮助的客户——这些客户应该按照他们呼叫的顺序获得帮助。

    一种特殊且非常重要的队列类型是优先级队列。元素根据与它们关联的“优先级”被引入队列:具有最高优先级的元素首先被引入队列。这个 ADT 在许多图算法(Dijkstra 算法、BFS、Prim 算法、霍夫曼编码 - 更多关于它们的信息)中是必不可少的。它是使用堆实现的。

    另一种特殊类型的队列是deque 队列(双关语它的发音是“deck”)。可以从队列的两端插入/删除元素。

    特性

    • 我们只能直接访问引入的“最旧”元素;
    • 搜索元素将从队列的内存中删除所有访问过的元素;
    • 弹出/推送元素或获取队列的前端是在恒定时间内完成的。搜索是线性的。

    5. Map 和 哈希表(Hash Table)

    地图
    哈希表

    Maps (dictionaries)是包含键集合和值集合的抽象数据类型。每个键都有一个与之关联的值。

    哈希表是一种特殊类型的映射。它使用散列函数生成一个散列码,放入一个桶或槽数组:键被散列,结果散列指示值的存储位置。

    最常见的散列函数(在众多散列函数中)是模常数函数。例如,如果常量是 6,则键 x 的值是x%6。

    理想情况下,散列函数会将每个键分配给一个唯一的桶,但他们的大多数设计都采用了不完善的函数,这可能会导致具有相同生成值的键之间发生冲突。这种碰撞总是以某种方式适应的。

    它们是做什么用的?

    Maps 最著名的应用是语言词典。语言中的每个词都为其指定了定义。它是使用有序映射实现的(其键按字母顺序排列)。

    通讯录也是一张Map。每个名字都有一个分配给它的电话号码。

    另一个有用的应用是值的标准化。假设我们要为一天中的每一分钟(24 小时 = 1440 分钟)分配一个从 0 到 1439 的索引。哈希函数将为h(x) = x.小时*60+x.分钟。

    特性

    • 键是唯一的(没有重复);
    • 抗碰撞性:应该很难找到具有相同键的两个不同输入;
    • 原像阻力:给定值 H,应该很难找到键 x,使得h(x)=H;
    • 第二个原像阻力:给定一个键和它的值,应该很难找到另一个具有相同值的键;

    术语:

    • “map”:Java、C++;
    • “dictionary”:Python、JavaScript、.NET;
    • “associative array":PHP。

    因为maps 是使用自平衡红黑树实现的(文章后面会解释),所以所有操作都在 O(log n) 内完成;所有哈希表操作都是常量。

    6. 图表(Graphs)

    图表

    图是表示一对两个集合的非线性数据结构:G={V, E},其中 V 是顶点(节点)的集合,而 E 是边(箭头)的集合。节点是由边互连的值 - 描述两个节点之间的依赖关系(有时与成本/距离相关联)的线。

    图有两种主要类型:有向图和无向图。在无向图中,边(x, y)在两个方向上都可用:(x, y)和(y, x)。在有向图中,边(x, y)称为箭头,方向由其名称中顶点的顺序给出:箭头(x, y)与箭头(y, x) 不同。

    它们是做什么用的?

    图是各种类型网络的基础:社交网络(如 weixin、csdn、weibo),甚至是城市街道网络。社交媒体平台的每个用户都是一个包含他/她的所有个人数据的结构——它代表网络的一个节点。weixin 上的好友关系是无向图中的边(因为它是互惠的),而在 CSDN 或 weibo上,帐户与其关注者/关注帐户之间的关系是有向图中的箭头(非互惠)。

    特性

    图论是一个广阔的领域,但我们将重点介绍一些最知名的概念:

    • 无向图中节点的度数是它的关联边数;
    • 有向图中节点的内部/外部度数是指向/来自该节点的箭头的数量;
    • 从节点 x 到节点 y 的链是相邻边的连续,x 是它的左端,y 是它的右边;
    • 一个循环是一个链,其中 x=y;图可以是循环/非循环的;如果 V 的任意两个节点之间存在链,则图是连通的;
    • 可以使用广度优先搜索 (BFS) 或深度优先搜索 (DFS) 遍历和处理图,两者都在 O(|V|+|E|) 中完成,其中 |S| 是集合S 的基数;查看下面的链接,了解图论中的其他基本信息。

    7. 树(Trees)

    树木

    一棵树是一个无向图,在连通性方面最小(如果我们消除一条边,图将不再连接)和在无环方面最大(如果我们添加一条边,图将不再是无环的) . 所以任何无环连通无向图都是一棵树,但为了简单起见,我们将有根树称为树。

    根是一个固定节点,它确定树中边的方向,所以这就是一切“开始”的地方。叶子是树的终端节点——这就是一切“结束”的地方。
    一个顶点的孩子是它下面的事件顶点。一个顶点可以有多个子节点。一个顶点的父节点是它上面的事件顶点——它是唯一的。

    它们是做什么用的?

    我们在任何需要描绘层次结构的时候都使用树。我们自己的家谱树就是一个完美的例子。你最古老的祖先是树的根。最年轻的一代代表叶子的集合。

    树也可以代表你工作的公司中的上下级关系。这样您就可以找出谁是您的上级以及您应该管理谁。

    特性

    • 根没有父级;
    • 叶子没有孩子;
    • 根和节点 x 之间的链的长度表示 x 所在的级别;
    • 一棵树的高度是它的最高层(在我们的例子中是 3);
    • 最常用的遍历树的方法是 O(|V|+|E|) 中的 DFS,但我们也可以使用 BFS;使用 DFS 在任何图中遍历的节点的顺序形成 DFS 树,指示我们访问节点的时间。

    8. 二叉树(Binary Trees)和二叉搜索树(Binary Search Trees)

    BT
    BST

    二叉树是一种特殊类型的树:每个顶点最多可以有两个子节点。在严格二叉树中,除了叶子之外,每个节点都有两个孩子。具有 n 层的完整二叉树具有所有2ⁿ-1 个可能的节点。

    二叉搜索树是一棵二叉树,其中节点的值属于一个完全有序的集合——任何任意选择的节点的值都大于左子树中的所有值,而小于右子树中的所有值。

    它们是做什么用的?

    BT 的一项重要应用是逻辑表达式的表示和评估。每个表达式都可以分解为变量/常量和运算符。这种表达式书写方法称为逆波兰表示法 (RPN)。这样,它们就可以形成一个二叉树,其中内部节点是运算符,叶子是变量/常量——它被称为抽象语法树(AST)。

    BST 经常使用,因为它们可以快速搜索键属性。AVL 树、红黑树、有序集和映射是使用 BST 实现的。

    特性

    BST 有三种类型的 DFS 遍历:

    • 先序(根、左、右);
    • 中序(左、根、右);
    • 后序(左、右、根);全部在 O(n) 时间内完成;
    • 中序遍历以升序为我们提供了树中的所有节点;
    • 最左边的节点是 BST 中的最小值,最右边的节点是最大值;
    • 注意 RPN 是 AST 的中序遍历;
    • BST 具有排序数组的优点,但有对数插入的缺点——它的所有操作都在 O(log n) 时间内完成。

    9. AVL树(Adelson-Velsky and Landis Trees )

    AVL
    红黑

    所有这些类型的树都是自平衡二叉搜索树。不同之处在于它们以对数时间平衡高度的方式。

    AVL 树在每次插入/删除后都是自平衡的,因为节点的左子树和右子树的高度之间的模块差异最大为 1。 AVL 以其发明者的名字命名:Adelson-Velsky 和 ​​Landis。

    在红黑树中,每个节点存储一个额外的代表颜色的位,用于确保每次插入/删除操作后的平衡。

    在 Splay 树中,最近访问的节点可以快速再次访问,因此任何操作的摊销时间复杂度仍然是 O(log n)。

    它们是做什么用的?

    AVL 似乎是数据库理论中最好的数据结构。

    RBT(红黑树) 用于组织可比较的数据片段,例如文本片段或数字。在 Java 8 版本中,HashMap 是使用 RBT 实现的。计算几何和函数式编程中的数据结构也是用 RBT 构建的。

    在 Windows NT 中(在虚拟内存、网络和文件系统代码中),Splay 树用于缓存、内存分配器、垃圾收集器、数据压缩、绳索(替换用于长文本字符串的字符串)。

    特性

    • ANY自平衡BST中ANY操作的摊销时间复杂度为O(log n);
    • 在最坏的情况下,AVL 的最大高度是 1.44 * log2n(为什么?提示:考虑所有级别都已满的 AVL 的情况,除了最后一个只有一个元素);
    • AVLs 在实践中搜索元素是最快的,但是为了自平衡而旋转子树的成本很高;
    • 同时,由于没有旋转,RBT 提供了更快的插入和删除;
    • 展开树不需要存储任何簿记数据。

    10.堆(Heaps)

    在这里插入图片描述

    最小堆是一棵二叉树,其中每个节点的值都大于或等于其父节点的值:val[par[x]] <= val[x],具有堆的 xa 节点,其中val[ x]是它的值,par[x] 是它的父级。

    还有一个实现相反关系的最大堆。

    二叉堆是一棵完整的二叉树(它的所有层都被填充,除了最后一层)。

    它们是做什么用的?

    正如我们几天前讨论过的,优先队列可以使用二叉堆有效地实现,因为它支持 O(log n) 时间内的 insert()delete()extractMax()reduceKey() 操作。这样,堆在图算法中也是必不可少的(因为优先级队列)。

    任何时候您需要快速访问最大/最小项目,堆都是最好的选择。

    堆也是堆排序算法的基础。

    特性

    • 它总是平衡的:无论何时我们在结构中删除/插入一个元素,我们只需要“筛选”/“渗透”它直到它处于正确的位置;
    • 节点k > 1的父节点是[k/2](其中 [x] 是 x 的整数部分),其子节点是2k和2k+1;
    • 设置优先级队列的替代方案,ordered_map(在 C++ 中)或任何其他可以轻松允许访问最小/最大元素的有序结构;
    • 根优先,因此其访问的时间复杂度为O(1),插入/删除在O(log n)中完成;创建一个堆是在 O(n) 中完成的;O(n*log n)中的堆排序。

    11.字典树(Tries)

    trie

    trie 是一种高效的信息检索数据结构。也称为前缀树,它是一种搜索树,允许以 O(L) 时间复杂度插入和搜索,其中 L 是键的长度。

    如果我们将密钥存储在一个平衡良好的 BST 中,它将需要与 L * log n 成正比的时间,其中 n 是树中的密钥数量。这样,与 BST 相比,trie 是一种更快的数据结构(使用 O(L)),但代价是 trie 存储要求。

    它们是做什么用的?

    树主要用于存储字符串及其值。它最酷的应用程序之一是在 Google 搜索栏中键入自动完成和自动建议。特里是最好的选择,因为它是最快的选择:如果我们不使用特里,更快的搜索比节省的存储更有价值。

    通过在字典中查找单词或在同一文本中查找该单词的其他实例,也可以使用 trie 来完成键入单词的正字法自动更正。

    特性

    • 它有一个键值关联;键通常是一个单词或它的前缀,但它可以是任何有序列表;
    • 根有一个空字符串作为键;
    • 节点值与其子节点值之间的长度差为 1;这样,根的子节点将存储长度​​为 1 的值;作为结论,我们可以说来自第 k 层的节点 x 具有长度k 的值;
    • 正如我们所说,插入/搜索操作的时间复杂度是 O(L),其中 L 是键的长度,这比 BST 的 O(log n) 快得多,但与哈希表相当;

    空间复杂度实际上是一个缺点:O(ALPHABET_SIZE*L*n)

    12. 段树(Segment Trees)

    段树

    段树是一个完整的二叉树,可以有效地回答查询,同时仍然可以轻松修改其元素。

    给定数组中索引 i 上的每个元素代表一个用[i, i]间隔标记的叶子。将其子节点分别标记为[x, y]或[y, z]的节点将具有[x, z]区间作为标签。因此,给定 n 个元素(0-indexed),线段树的根将被标记为[0, n-1]。

    它们是做什么用的?

    它们在可以使用分而治之(我们将要讨论的第一个算法概念)解决的任务中非常有用,并且还可能需要更新其元素。这样,在更新元素时​​,包含它的任何区间也会被修改,因此复杂度是对数的。例如,n 个给定元素的总和/最大值/最小值是线段树最常见的应用。如果元素更新正在发生,二分搜索也可以使用段树。

    特性

    • 作为二叉树,节点 x 将2x和2x+1作为子节点,[x/2]作为父节点,其中[x]是x的整数部分;
    • 更新段树中整个范围的一种有效方法称为“延迟传播”,它也是在 O(log n) 中完成的(有关操作的实现,请参见下面的链接);
    • 它们可以是 k 维的:例如,有 q 个查询来查找一个矩阵的给定子矩阵的总和,我们可以使用二维线段树;
    • 更新元素/范围需要 O(log n) 时间;对查询的回答是恒定的(O(1));
    • 空间复杂度是线性的,这是一个很大的优势:O(4*n)。

    13. 树状数组(Fenwick Trees)

    少量

    fenwick 树,也称为二叉索引树 (BIT),是一种也用于高效更新和查询的数据结构。与 Segment Trees 相比,BITs 需要更少的空间并且更容易实现。

    它们是做什么用的?

    BIT 用于计算前缀和——第 i 个位置的元素的前缀和是从第一个位置到第 i 个元素的总和。它们使用数组表示,其中每个索引都以二进制系统表示。例如,索引 10 相当于十进制系统中的索引 2。

    特性

    • 树的构建是最有趣的部分:首先,数组应该是 1-indexed 要找到节点 x 的父节点,您应该将其索引 x 转换为二进制系统并翻转最右边的有效位;ex.节点 6 的父节点是 4;
    6 = 1*2²+1*2¹+0*2=> 1"1"0 (flip) 
    => 100 = 1*2²+0*2¹+0*2= 4;
    
    • 最后,ANDing 元素,每个节点都应该包含一个可以添加到前缀和的间隔;
    • 更新的时间复杂度仍然是 O(log n),查询的时间复杂度仍然是 O(1),但空间复杂度与线段树的 O(4*n) 相比是一个更大的优势:O(n)。

    14. 并查集(Disjoint Set Union)

    数据中心

    我们有 n 个元素,每个元素代表一个单独的集合。并查集 (DSU) 允许我们做两个操作:

    1.UNION — 组合任意两个集合(或者统一两个不同元素的集合,如果它们不是来自同一个集合);
    2.FIND — 查找元素来自的集合。

    它们是做什么用的?

    并查集(DSU) 在图论中非常重要。您可以检查两个顶点是否来自同一个连接组件,或者甚至可以统一两个连接组件。

    让我们以城市和城镇为例。由于人口和经济增长的邻近城市正在扩张,它们可以轻松创建大都市。因此,两个城市合并在一起,他们的居民住在同一个大都市。我们还可以通过调用 FIND 函数来检查一个人居住在哪个城市。

    特性

    • 它们用树表示;一旦两组组合在一起,两个根中的一个成为主根,另一个根的父代是另一棵树的叶子之一;
    • 一种实用的优化是通过高度压缩树木;这样,联合由最大的树组成,以轻松更新它们的两个数据(参见下面的实现);
    • 所有操作都在 O(1) 时间内完成。

    15. 最小生成树(Minimum Spanning Trees)

    MST

    给定一个连通图和无向图,该图的生成树是一个子图,它是一棵树并将所有节点连接在一起。单个图可以有许多不同的生成树。加权、连通和无向图的最小生成树 (MST) 是权重(成本)小于或等于其他所有生成树权重的生成树。生成树的权重是赋予生成树每条边的权重之和。

    它们是做什么用的?

    最小生成树(MST )问题是一个优化问题,一个最小成本问题。有了路线网,我们可以认为影响n个城市之间建立国道的因素之一是相邻两个城市之间的最小距离。

    国家路线就是这样,由道路网络图的 MST 表示。

    特性

    作为一棵树,具有 n 个顶点的图的 MST 具有 n-1 条边;可以使用以下方法解决:

    • Prim 算法 — 密集图的最佳选择(具有 n 个节点且边数接近n(n-1)/2)的图);
    • Kruskal 算法——主要使用;它是一种基于不相交集联合的贪心算法(我们后面也将讨论它);
    • 构建它的时间复杂度对于 Kruskal 来说是 O(n log n) 或 O(n log m)(这取决于图),对于 Prim 来说是 O(n²)。

    二、算法

    1.分治算法(Divide and Conquer)

    分而治之(DAC)本身并不是一个特定的算法,而是在深入研究其他主题之前需要了解的重要算法类别。它用于解决可以划分为与原始问题相似但规模较小的子问题的问题。然后 DAC 递归地求解它们,最后合并结果以找到问题的解决方案。

    它分为三个阶段:

    • 划分——将问题分解为子问题;
    • 用递归解决子问题;
    • 合并——子问题的结果到最终解决方案中。

    它是干什么用的?

    分治算法(DAC) 的一种实际应用是使用多个处理器进行并行编程,因此子问题在不同的机器上执行。

    DAC 是许多算法的基础,例如快速排序、合并排序、二分搜索或快速乘法算法。

    特性

    • 每个 DAC 问题都可以写成一个递推关系;因此,必须找到停止递归的基本情况;
    • 它的复杂度是T(n)=D(n)+C(n)+M(n),这意味着每个阶段都有不同的复杂度,具体取决于问题。

    2. 排序算法(Sorting Algorithms)

    排序算法用于根据元素上的比较运算符重新排列给定元素(来自数组或列表)。当我们提到一个排序数组时,我们通常会想到升序(比较运算符是“<”)。排序有多种类型,具有不同的时间和空间复杂度。其中一些是基于比较的,有些则不是。以下是最流行/最有效的排序方法:

    冒泡排序(Bubble Sort)

    冒泡排序是最简单的排序算法之一。它基于相邻元素之间的重复交换(如果它们的顺序错误)。它是稳定的,它的时间复杂度是 O(n²) 并且它需要 O(1) 辅助空间。

    计数排序(Counting Sort)

    计数排序不是基于比较的排序。它基本上是使用每个元素的频率(一种散列),确定最小值和最大值,然后在它们之间迭代以根据其频率放置每个元素。它在 O(n) 中完成,空间与数据范围成正比。如果输入范围不明显大于元素数量,则它是有效的。

    快速排序(Quick Sort)

    快速排序是分而治之的一个应用。它基于选择一个元素作为枢轴(第一个、最后一个或中间值),然后交换元素以将枢轴放置在所有小于它的元素和所有大于它的元素之间。它没有额外的空间和 O(n*log n) 时间复杂度——基于比较的方法的最佳复杂度。

    归并排序(Merge Sort)

    归并排序也是一个分而治之的应用程序。它将数组分成两半,对每一半进行排序,然后合并它们。它的时间复杂度也是 O(n*log n),所以它也像 Quick Sort 一样超快,但不幸的是它需要 O(n) 额外空间来同时存储两个子数组,最后合并它们。

    基数排序(Radix Sort)

    基数排序使用计数排序作为子程序,因此它不是基于比较的算法。我们怎么知道CS是不够的?假设我们必须对[1, n²] 中的元素进行排序。使用 CS,我们需要 O(n²)。我们需要一个线性算法——O(n+k),其中元素在[1, k]范围内。它从最不重要的一个(单位)开始,到最重要的(十、百等)对元素进行逐位排序。额外空间(来自 CS):O(n)。

    3. 搜索算法(Searching Algorithms)

    搜索算法旨在检查数据结构中元素的存在,甚至返回它。有几种搜索方法,但这里是最受欢迎的两种:

    线性搜索(Linear Search)

    该算法的方法非常简单:您从数据结构的第一个索引开始搜索您的值。您将它们一一比较,直到您的值和当前元素相等。如果该特定值不在 DS 中,则返回 -1。

    时间复杂度:O(n)

    二分查找(Binary Search)

    BS 是一种基于分而治之的高效搜索算法。不幸的是,它只适用于排序的数据结构。作为一种 DAC 方法,您连续将 DS 分成两半,并将搜索中的值与中间元素的值进行比较。如果它们相等,则搜索结束。无论哪种方式,如果您的值大于/小于它,搜索应该继续在右/左半部分。

    时间复杂度:O(log n)

    4. 埃氏筛法(Sieve of Eratosthenes)

    给定一个整数 n,打印所有小于或等于 n 的素数。
    Eratosthenes 筛法是解决这个问题的最有效的算法之一,它完美地适用于小于10.000.000 的n 。

    该方法使用频率列表/映射来标记[0, n]范围内每个数字的素数:如果 x 是素数,则ok[x]=0,否则ok[x]=1。

    我们开始从列表中选择每个素数,并用 1 标记列表中的倍数——这样,我们选择未标记的 (0) 数。最后,我们可以在 O(1) 中轻松回答任意数量的查询。

    经典算法在许多应用中都是必不可少的,但我们可以进行一些优化。首先,我们很容易注意到 2 是唯一的偶素数,因此我们可以单独检查它的倍数,然后在范围内迭代以找到从 2 到 2 的素数。其次,很明显,对于数字 x,我们之前在迭代 2、3 等时已经检查了 2x、3x、4x 等。这样,我们的乘数检查 for 循环每次都可以从 x² 开始。最后,即使这些倍数中有一半是偶数,而且我们也在迭代奇素数,因此我们可以在倍数检查循环中轻松地从 2x 迭代到 2x。

    空间复杂度:O(n)
    时间复杂度:O(n*log(log n)) 用于经典算法,O(n) 用于优化算法。

    5. 字符串匹配算法(Knuth-Morris-Pratt)

    给定长度为 n 的文本和长度为 m 的模式,找出文本中所有出现的模式。

    Knuth-Morris-Pratt 算法 (KMP) 是解决模式匹配问题的有效方法。
    天真的解决方案基于使用“滑动窗口”,每次设置新的起始索引时,我们都会比较字符与字符,从文本的索引 0 开始到索引 nm。这样,时间复杂度是 O(m*(n-m+1))~O(n*m)。

    KMP 是对朴素解决方案的优化:它在 O(n) 中完成,并且当模式具有许多重复的子模式时效果最佳。因此,它也使用滑动窗口,但不是将所有字符与子字符串进行比较,而是不断寻找当前子模式的最长后缀,这也是它的前缀。换句话说,每当我们在某些匹配后检测到不匹配时,我们就已经知道下一个窗口文本中的某些字符。因此,再次匹配它们是没有用的,因此我们重新开始匹配文本中具有该前缀后的字符的相同字符。我们怎么知道我们应该跳过多少个字符?好吧,我们应该构建一个预处理数组,告诉我们应该跳过多少个字符。

    6.贪婪算法(Greedy)

    Greedy 方法多用于需要优化且局部最优解导致全局最优解的问题。

    也就是说,当使用 Greedy 时,每一步的最优解都会导致整体最优解。然而,在大多数情况下,我们在一个步骤中做出的决定会影响下一步的决定列表。在这种情况下,必须用数学方法证明算法。Greedy 也会在一些数学问题上产生很好的解决方案,但不是全部(可能无法保证最佳解决方案)!

    贪心算法通常有五个组成部分:

    • 候选集——从中创建解决方案;
    • 选择函数——选择最佳候选人;
    • 可行性函数——可以确定候选人是否能够为解决方案做出贡献;
    • 一个目标函数——将候选人分配给(部分)解决方案;
    • 一个解决方案函数——从部分解决方案构建解决方案。

    分数背包问题

    给定n个物品的重量和价值,我们需要将这些物品放入容量为W的背包中,以获得背包中的最大总价值(允许取件物品:一件物品的价值与其重量成正比)。

    贪心方法的基本思想是根据它们的价值/重量比对所有项目进行排序。然后,我们可以添加尽可能多的整个项目。当我们发现一件比背包中剩余重量 (w1) 重 (w2) 的物品时,我们将对其进行分割:仅取出w2-w1以最大化我们的利润。保证这个贪心的解决方案是正确的。

    7. 动态规划(Dynamic Programming)

    动态规划 (DP) 是一种类似于分而治之的方法。它还将问题分解为类似的子问题,但它们实际上是重叠和相互依赖的——它们不是独立解决的。

    每个子问题的结果都可以在以后随时使用,它是使用记忆(预先计算)构建的。DP 主要用于(时间和空间)优化,它基于寻找循环。

    DP 应用包括斐波那契数列、河内塔、Roy-Floyd-Warshall、Dijkstra 等。 下面我们将讨论 0-1 背包问题的 DP 解决方案。

    0–1 背包问题

    给定n个物品的重量和价值,我们需要将这些物品放入容量为W的背包中,以获得背包中的最大总值(不允许像贪婪解决方案中的那样分割物品)。
    0-1 属性是由我们应该选择整个项目或根本不选择它的事实给出的。
    我们构建了一个 DP 结构作为矩阵dp[i][cw]存储我们通过选择总权重为 cw 的 i 个对象可以获得的最大利润。很容易注意到我们应该首先用v[i]初始化dp[1][w[i] ],其中w[i]是第 i 个对象的权重,v[i] 是它的值。
    复现如下:

    dp[i][cw] = max(dp[i-1][cw], dp[i-1][cw-w[i]]+v[i])
    

    我们稍微分析一下。

    dp[i-1][cw]描述了我们没有在背包中添加当前物品的情况。dp[i-1][cw-w[i]]+v[i]就是我们添加item的情况。话虽如此,dp[i-1][cw-w[i]]是采用 i-1 个元素的最大利润:所以它们的重量是当前重量,没有我们的物品重量。最后,我们将项目的值添加到它。

    答案存入dp[n][W]. 通过一个简单的观察进行优化:在循环中,当前行仅受前一行的影响。因此,将DP结构存储到矩阵中是不必要的,因此我们应该选择一个空间复杂度更好的数组:O(n)。时间复杂度:O(n*W)。

    8. 最长公共子序列(Longest Common Subsequence)

    给定两个序列,找出它们中存在的最长子序列的长度。子序列是以相同的相对顺序出现的序列,但不一定是连续的。例如,“bcd”、“abdg”、“c”都是“abcdefg”的子序列。

    这是动态规划的另一个应用。LCS 算法使用 DP 来解决上述问题。

    实际的子问题是要分别从序列 A 中的索引 i 开始,分别从序列 B 中的索引 j 中找到最长公共子序列。

    接下来,我们将构建 DP 结构lcs[ ][ ](矩阵),其中lcs[i][j]是从 A 中的索引 i 开始,分别是 B 中的索引 j 的公共子序列的最大长度。我们将以自顶向下的方式构建它。显然,解决方案存储在lcs[n][m] 中,其中 n 是 A 的长度,m 是 B 的长度。

    递推关系非常简单直观。为简单起见,我们将考虑两个序列都是 1 索引的。首先,我们将初始化lcs[i][0] , 1<=i<=nlcs[0][j] , 1<=j<=m , 0, 作为基本情况(没有从 0 开始的子序列)。然后,我们将考虑两种主要情况:如果A[i]等于B[j],则lcs[i][j] = lcs[i-1][j-1]+1(比之前的 LCS 多一个相同的字符)。否则,它将是lcs[i-1][j](如果不考虑A[i])和lcs[i][j-1](如果不考虑B[j])之间的最大值)。

    时间复杂度:O(n*m)
    附加空间:O(n*m)

    9. 最长递增子序列(Longest Increasing Subsequence)

    给定一个包含 n 个元素的序列 A,找到最长子序列的长度,使其所有元素按递增顺序排序。子序列是以相同的相对顺序出现的序列,但不一定是连续的。例如,“bcd”、“abdg”、“c”是“abcdefg”的子序列。

    LIS 是另一个可以使用动态规划解决的经典问题。

    使用数组l[ ]作为 DP 结构来寻找递增子序列的最大长度,其中l[i]是包含A[i]的递增子序列的最大长度,其元素来自[A[i] ], ..., A[n]] 子序列。l[i]为 1,如果A[i]之后的所有元素比它小。否则,在 A[i] 之后大于它的所有元素之间的最大值为 1+。显然,l[n]=1,其中 n 是 A 的长度。 实现是自底向上的(从末尾开始)。

    在搜索当前元素之后的所有元素之间的最大值时出现了一个优化问题。我们能做的最好的事情是二分搜索最大元素。

    为了找到现在已知的最大长度的子序列,我们只需要使用一个额外的数组ind[],它存储每个最大值的索引。

    时间复杂度:O(n*log n)
    附加空间:O(n)

    10.凸包算法(Convex Hull)

    给定同一平面中的一组 n 个点,找到包含所有给定点(位于多边形内部或其边上)的最小面积凸多边形。这种多边形称为凸包。凸包问题是一个经典的几何,在现实生活中有很多应用。例如,碰撞避免:如果汽车的凸包避免碰撞,那么汽车也能避免碰撞。路径的计算是使用汽车的凸表示完成的。形状分析也是在凸包的帮助下完成的。这样,图像处理很容易通过匹配模型的凸缺陷树来完成。

    有一些算法用于寻找凸包,如 Jarvis 算法、Graham 扫描等。今天我们将讨论 Graham 扫描和一些有用的优化。

    格雷厄姆扫描按极角对点进行排序——由某个点和其他选定点确定的线的斜率。然后用一个栈来存储当前时刻的凸包。当一个点 x 被压入堆栈时,其他点会被弹出堆栈,直到 x 与最后两个点所确定的线形成小于 180° 的角度。最后,引入堆栈的最后一个点关闭多边形。由于排序,这种方法的时间复杂度为 O(n*log n)。但是,这种方法在计算斜率时会产生精度误差。

    一种改进的解决方案具有相同的时间复杂度,但误差较小,按坐标(x,然后是 y)对点进行排序。然后我们考虑由最左边和最右边的点形成的线,并将问题分为两个子问题。最后,我们在这条线的每一边找到了凸包。所有给定点的凸包是两个包的重聚。

    11. 图遍历(Graph Traversals)

    遍历图的问题是指以特定顺序访问所有节点,通常沿途计算其他有用信息。

    广度优先搜索(Breadth-First Search)

    广度优先搜索 (BFS) 算法是确定图是否连通的最常用方法之一——或者换句话说,查找 BFS 源节点的连通分量。

    BFS 还用于计算源节点和所有其他节点之间的最短距离。BFS 的另一个版本是 Lee 算法,用于计算网格中两个单元格之间的最短路径。

    该算法首先访问源节点,然后访问将被推入队列的邻居。队列中的第一个元素被弹出。我们将访问它的所有邻居,并将之前未访问的邻居推入队列。重复该过程直到队列为空。当队列为空时,表示所有可达顶点都已访问完毕,算法结束。

    深度优先搜索(Depth-First Search)

    深度优先搜索 (DFS) 算法是另一种常见的遍历方法。在检查图形的连通性时,它实际上是最好的选择。

    首先,我们访问根节点并将其压入堆栈。虽然堆栈不为空,但我们检查顶部的节点。如果该节点有未访问的邻居,则选择其中一个并将其压入堆栈。否则,如果它的所有邻居都被访问过,我们就会弹出这个节点。当堆栈变空时,算法结束。

    经过这样的遍历,就形成了一个DFS树。DFS 树有很多应用;最常见的一种是存储每个节点的“开始”和“结束”时间——它进入堆栈的时刻,分别是它从堆栈中弹出的时刻。

    12. 弗洛依德算法(Floyd-Warshall)

    Floyd-Warshall / Roy-Floyd 算法解决了所有对最短路径问题:找到给定边加权有向图中每对顶点之间的最短距离。

    FW 是一个动态规划应用程序。DP 结构(矩阵)dist[ ][ ]用输入图矩阵初始化。然后我们将每个顶点视为其他两个节点之间的中间体。最短路径在每两对节点之间更新,任何节点 k 作为中间顶点。如果 k 是 i 和 j 之间排序路径中的中间值,则dist[i][j]成为dist[i][k]+dist[k][j]dist[i][j]之间的最大值。

    时间复杂度:O(n³)
    空间复杂度:O(n²)

    13. Dijkstra 算法和 Bellman-Ford 算法

    迪杰斯特拉(Dijkstra) 算法

    给定一个图和图中的一个源顶点,找出从源到给定图中所有顶点的最短路径。

    Dijkstra 算法用于在加权图中找到这样的路径,其中所有的权重都是正的。

    Dijkstra 是一种贪心算法,它使用以源节点为根的最短路径树(SPT)。SPT 是一种自平衡二叉树,但该算法可以使用堆(或优先级队列)来实现。我们将讨论堆解决方案,因为它的时间复杂度是 O(|E|*log |V|)。这个想法是使用图形的邻接列表表示。这样,节点将使用 BFS (广度优先搜索)在 O(|V|+|E|) 时间内遍历。

    所有顶点都用 BFS 遍历,那些最短距离尚未最终确定的顶点被存储到最小堆(优先队列)中。

    创建最小堆并将每个节点连同它们的距离值一起推入其中。然后,源成为距离为 0 的堆的根。其他节点将无限分配为距离。当堆不为空时,我们提取最小距离值节点 x。对于与 x 相邻的每个顶点 y,我们检查 y 是否在最小堆中。在这种情况下,如果距离值大于 (x, y) 的权重加上 x 的距离值,那么我们更新 y 的距离值。

    贝尔曼-福特(Bellman-Ford)算法

    正如我们之前所说,Dijkstra 仅适用于正加权图。贝尔曼解决了这个问题。给定一个加权图,我们可以检查它是否包含负循环。如果没有,那么我们还可以找到从我们的源到其他源的最小距离(可能为负权重)。

    Bellman-Ford 非常适合分布式系统,尽管它的时间复杂度是 O(|V| |E|)。

    我们初始化一个 dist[] 就像在 Dijkstra 中一样。对于 *|V|-1次,对于每个(x, y)边,如果dist[y] > dist[x] + (x, y) 的权重,那么我们用它更新dist[y]。

    我们重复最后一步以可能找到负循环。这个想法是,如果没有负循环,最后一步保证最小距离。如果有任何节点在当前步骤中的距离比上一步中的距离短,则检测到负循环。

    14.克鲁斯卡尔算法(Kruskal’s Algorithm)

    我们之前已经讨论过什么是最小生成树。

    有两种算法可以找到图的 MST:Prim(适用于密集图)和 Kruskal(适用于大多数图)。现在我们将讨论 Kruskal 算法。

    Kruskal 开发了一种贪心算法来寻找 MST。它在稀有图上很有效,因为它的时间复杂度是 O(|E|*log |V|)

    该算法的方法如下:我们按权重的递增顺序对所有边进行排序。然后,选取最小的边。如果它不与当前 MST 形成循环,我们将其包括在内。否则,丢弃它。重复最后一步,直到 MST 中有 |V|-1 条边。

    将边包含到 MST 中是使用 Disjoint-Set-Union 完成的,这也在前面讨论过。

    15. 拓扑排序(Topological Sorting)

    有向无环图 (DAG) 只是一个不包含循环的有向图。

    DAG 中的拓扑排序是顶点的线性排序,使得对于每个拱形(x, y),节点 x 出现在节点 y 之前。

    显然,拓扑排序中的第一个顶点是一个入度为 0 的顶点(没有拱形指向它)。

    另一个特殊属性是 DAG 没有唯一的拓扑排序。

    BFS (广度优先搜索)实现遵循此例程:找到一个入度为 0 的节点并将第一个推入排序。该顶点已从图中删除。由于新图也是一个 DAG,我们可以重复这个过程。

    在 DFS 期间的任何时候,节点都可以属于以下三个类别之一:

    • 我们完成访问的节点(从堆栈中弹出);
    • 当前在堆栈上的节点;
    • 尚未发现的节点。

    如果在 DAG 中的 DFS 期间,节点 x 具有到节点 y 的输出边,则 y 属于第一类或第三类。如果 y 在堆栈上,则(x, y)将结束一个循环,这与 DAG 定义相矛盾。

    这个属性实际上告诉我们一个顶点在它的所有传出邻居都被弹出后从堆栈中弹出。因此,要对图进行拓扑排序,我们需要跟踪弹出顶点的逆序列表。

    哇,你已经到读了文章的结尾。感谢您的阅览!文章篇幅较长,如果有些出错的地方还请大家批评指正,可在评论区留言或者私信我。

    关注作者公众号【海拥】回复【进群】,免费下载CSDN资源和百度文库资源
    在这里插入图片描述

    整理不易,最后,不要忘了❤或📑支持一下哦

    展开全文
  • 半边数据结构讲解

    万次阅读 多人点赞 2017-11-15 19:16:40
    在介绍半边数据结构之前,必须先要科普一下计算机图形学中,模型的几何表达。 对于一般的几何模型,在计算机图形学上早已有相关的数学模型来表达,而且这些表达已经标准化了。 例如对于机械行业的CAD来说,模型...

    前言

    在介绍半边数据结构之前,必须先要科普一下计算机图形学中,模型的几何表达。

    对于一般的几何模型,在计算机图形学上早已有相关的数学模型来表达,而且这些表达已经标准化了。

     

    例如对于机械行业的CAD来说,模型是比较规则的,但是要求的精度必须足够精准,所以会有相应的数据结构来表达几何体。例如拉伸体会有对应的特征来表示拉伸体,旋转体会有对应的特征来表示旋转体。而曲面必须要用到nurbs这些精确的数学模型来表达。

    而对于数字媒体,游戏,实时交互等的领域,模型通常是不规则的曲面几何体,要求美观(精度低)、计算时间足够短。因此模型通常是用的离散化的表面网格,所谓离散化就是网格通过一系列的面片拼接而成,好像比较粗糙,但是通过贴图和渲染技术可以使得看起来却是光滑的。

     

    对于用过OpenGL或者Unity加载和处理过模型的人来说,这些似乎都有些印象,可是这些知识却是在大部分计算机图形学的教材上都是没有或者很少详细介绍的,而这些知识却是非常重要,而且又是非常常用的,因此必须要在这里介绍一下。

     

    本文着重介绍离散化的表面网格。

     

    对于表面网格来说,其重要的特点在于拓扑,也就是曲面是如何表达的,而不是其顶点的位置。拓扑的不同造就了不同的数据结构和标准,不同的拓扑,其进行网格查询和编辑的性能也不同。

     

    在计算机图形学上,有一个术语叫做流形,这是一个比较装逼的术语,很多学术论文都会用到这样一个词。为了这一个词,我还特意学了很久的数学,来看它的数学含义。

    现在有经验了,对流形的理解总算有点清晰了。计算机图形学上,通常说的流形是一种几何模型表面(不是所有几何表面都是流形),即二维流形。这种流形在数学上对应的实际上是最简单的流形——拓扑流形

    二维拓扑流形是什么意思呢?二维拓扑流形就是说,流形上的每个点都有一个邻域,这个邻域能够与欧几里得平面(就是普通意义上的平面)的某个区域一一连续对应。

    这是我结合http://blog.csdn.net/lafengxiaoyu/article/details/51524361和点集拓扑的知识总结出的流形的概念。

     

    那么二维流形在计算机图形学上的离散化表达是怎样呢?事实上,计算机图形学的流形概念比数学上的流形概念简单多了。简单地说,如果网格的每个边最多被两个面片共用,那么这个网格就是流形网格,否则称为非流形网格

     

    在计算机图形学上,表达表面网格的数据结构有三种,分别是面列表、邻接矩阵、半边结构。

    面列表的典型代表是.obj格式文件和Unity。其优点是,简单而且能够表达非流形网格,但网格查询和处理能力差。

    当然还有一些不是利用索引,而是直接储存整个顶点的信息,典型代表是OpenGL可编程管线和.stl格式文件。

     

    邻接矩阵就不多说了,半边数据结构是接下来要重点讲述的。关于流形网格和这些数据结构的知识可查阅链接: https://pan.baidu.com/s/1jIlCwF8 密码: y9n7

    或者https://wenku.baidu.com/view/6424ca78ce2f0066f53322c3.html

     

    半边数据结构

    关于半边数据结构,其最大特点当然是半边,每个边分为两个半边,每个半边都是一个有向边,方向相反。如果一个边被两个面片共用(正则边),则每个面片都能各自拥有一个半边。如果一个边仅被一个面片占有(边界边),则这个面片仅拥有该边的其中一个半边,另一个半边为闲置状态。

    这就能解释为什么半边数据结构仅支持流形网格了。

    图1

     

    下面讲解半边数据结构的三个重要的数据结构——顶点、半边、面片

     

    顶点(Vertex):包含出半边(OutgoingHalfedge)的指针或索引

    半边(HalfEdge):包含起始点(StartVertex)、邻接面(AdjacentFace)、下一条半边(NextHalfedge)、上一条半边(PrevHalfedge)的指针或索引

    面片(Face):包含一条起始边(FirstHalfedge)的指针或索引

     

    注意:半边数据结构的面片不一定是三角面片,可以是多边形的面片。

     

    对于C/C++的话,所用的应该是指针,此时每个数据结构就变成了链表了。而对于C#或者Java的话,由于没有指针,所以可能要分别增加对应的列表类来容纳各自的点边面。

     

    对于C/C++,可参考CGAL或者是OpenMesh,因为它们用的都是半边数据结构。

    而C#的话,可参看 https://github.com/meshmash/Plankton的源代码(本文解释用的就是这个接口)。

     

    现在问题来了。顶点可能有两条或以上的出半边,而顶点的数据表达只有一条出半边,那这条出半边是哪一条?半边的下一条半边又是哪一条?面片的起始半边又是哪一条?通过某个网格的数据结构图(如图1)能看得出这些信息吗?

     

    答:事实上,半边数据结构的网格的构建通常是通过面列表来创建的,也就是说,正常的构建半边数据结构网格是通过一个一个面片的添加来构建的。

    所以面的添加顺序就决定了点边面结构的信息,添加面的方法通常是addFace(a,b,c,…),a,b,c…参数是该面片按其某条环路顺序排列的顶点的指针或索引。注意,环路可以是顺时针或者逆时针,决定了该面片的方向(法向量的方向)。

     

    面片的起始半边(FirstHalfedge):若添加面片的操作为addFace(0,1,2),那么该面片的起始边为0号指向1号的半边(下面简称0->1,其余以此类推)。

    由此可见,面片的起始半边是由顶点的添加顺序决定的,同一个面片(构成其半边的方向也必须相同)的起始半边可以是不同的,因此通过图1是无法知道面片的起始半边是哪条。

     

    半边的邻接面(AdjacentFace):若添加面片的操作为addFace(0,1,2),则0->1,1->2,2->0的邻接面都是该面片。而1->0,2->1,0->2的邻接面不是该面片。

    半边的邻接面是唯一的,若某条边是边界边,则它必定有某条边的邻接面指针为空指针或者索引为-1。所以由图1是能够看出其邻接面的。

     

    半边的下一条半边(NextHalfedge):若添加面片的操作为addFace(0,1,2),则0->1的下一条边为1->2,也就是说,若该半边是有邻接面的,则其下一条半边沿着邻接面的环路走。如果该半边没有邻接面(边界半边),则其下一条半边沿着边界走(这个后面会解释)。所以由图1是能够看出半边的下一条半边的。

     

    顶点的出半边(OutgoingHalfedge):若该顶点是边界边的顶点,则其出半边必为边界半边,通过图1是能看出的。若该顶点并不是边界边的顶点(被封闭),则其出半边为其被封闭前(添加最后一个面片即被封闭)的出半边,通过图1无法看出。为什么是这样呢?后面会解释。

     

    好了,下面通过C#的代码来解释半边网格的构建。

    PlanktonMesh pMesh = new PlanktonMesh();
                List<PlanktonXYZ> vertices = new List<PlanktonXYZ>();
                vertices.Add(new PlanktonXYZ(-1, 1, 0));
                vertices.Add(new PlanktonXYZ(1, 1, 0));
                vertices.Add(new PlanktonXYZ(1, -1, 0));
                vertices.Add(new PlanktonXYZ(-1, -1, 0));
    
                pMesh.Vertices.AddVertices(vertices);
    
                pMesh.Faces.AddFace(0, 1, 2);
                pMesh.Faces.AddFace(0, 2, 3);
    

    核心代码很短,前面都是添加顶点,最关键的就是pMesh.Faces.AddFace方法,下面讲解一下。

     

    首先,添加顶点0,1,2构成的面片,代码按顺序成对添加半边(addPair方法),注意,半边是成对地添加的,即有0->1必有1->0。并分配其邻接面,无邻接面半边其邻接面索引设为-1。

    图2

     

    此时,

    第0条边:0->1,邻接面为0

    第1条边:1->0,邻接面为-1

    第2条边:1->2,邻接面为0

    第3条边:2->1,邻接面为-1

    第4条边:2->0,邻接面为0

    第5条边:0->2,邻接面为-1

     

    然后分配外围半边(非该面的半边)的下一条边和上一条边和顶点的出半边(swich(id)语句之后):

    2->1的下一条边为1->0,1号顶点的出半边为1->0(边界半边)

    0->2的下一条边为2->1,2号顶点的出半边为2->1(边界半边)

    1->0的下一条边为0->2,0号顶点的出半边为0->2(边界半边)

    上一条半边信息从下一条半边的信息可知。

    0->2,2->1,1->0构成一个环,满足边界环路。

     

    然后分配该面的半边的下一条半边:

    0->1下一条半边为1->2

    1->2下一条半边为2->0

    2->0下一条半边为0->1

    0->1,1->2,2->0构成一个环,满足面环路。

     

    好了,下面添加另一个面0,2,3

    图3

     

    现在的情况跟添加第一个面的情况不同,因为0->2已存在,所以只需添加剩余的边即可:

    第6条边:2->3,邻接面为0

    第7条边:3->2,邻接面为-1

    第8条边:3->0,邻接面为0

    第9条边:0->3,邻接面为-1

     

    由于0->2已经不是边界半边了,2->1的上一条边不再是它,而是3->2。

    即3->2的下一条边为2->1

    0->3的下一条边为3->2(和第一个面片的情况一样),3号顶点的出半边为3->2(边界半边)

    1->0的下一条边改为0->3,0号顶点的出半边改为0->3(边界半边)

    从而使得边界环路满足。

     

    然后分配该面的半边的下一条半边:

    0->2下一条半边为2->3

    2->3下一条半边为3->0

    3->0下一条半边为0->2

    0->2,2->3,3->0构成一个环,满足面环路。

     

    好了,下面思考一下,假如第二个面片的顶点添加顺序为addFace(2,0,3),该面片能否添加成功?

    答案是否定的,因为2->0已经存在并且带有邻接面0,不满足面片共享各自半边的条件。

     

    好了,假如一个顶点的周围都是面片(不是某个边界边的顶点),如图4所示,0号顶点的出半边是哪条?

     

    图4

     

    核心代码如下:

                PlanktonMesh pMesh = new PlanktonMesh();
                List<PlanktonXYZ> vertices = new List<PlanktonXYZ>();
                vertices.Add(new PlanktonXYZ(0, 0, 0));
                vertices.Add(new PlanktonXYZ(0, 1, 0));
                vertices.Add(new PlanktonXYZ(1,-1, 0));
                vertices.Add(new PlanktonXYZ(-1,-1,0));
    
                pMesh.Vertices.AddVertices(vertices);
    
                pMesh.Faces.AddFace(0, 1, 2);
                pMesh.Faces.AddFace(0, 2, 3);
                pMesh.Faces.AddFace(0, 3, 1);
    

     

    注意,当还未执行语句pMesh.Faces.AddFace(0,3, 1);的时候,0号顶点的出半边为0->3。执行完之后,如果0号顶点不封闭,则它的出半边本应改为0->1,可是0->1早已存在。故0号顶点的出半边不会再改变,仍为0->3。

     

     

    好了,半边数据结构的讲解就到此为止了。当然了,如果要在OpenGL或Unity中显示半边数据结构,则必须要把半边数据结构的数据转换为相应的网格数据。这个不难,只要熟悉OpenGL和Unity即知道如何转换。可以提醒一下,由于OpenGL和Unity的顶点数据都是用数组来传递的,因此必须把半边数据结构的顶点列表转换成坐标的数组,这个是不难的。C/C++的话可以搜索一下OpenMesh+OpenGL的教程。C#的话可以搜索Unity读取.obj文件/.stl文件的教程,或者直接搜索半边数据结构+Unity的教程即可。

     

    最后分享一下本人添加注释的C#源代码,重点看PlanktonFaceList.cs的代码

    链接:http://pan.baidu.com/s/1qXZoY5Y 密码:vder

     

    展开全文
  • 数据结构课设 校园导游
  • 数据结构总结

    千次阅读 2012-09-10 21:28:06
    常见的数据结构运用总结 考虑到Obsidian三个成员的擅长领域,这段时间都在做杂题,算是学习各种算法吧,趁现在休息的时间,而且大家马上要备战今年的比赛了,写写自己专攻方面的一些心得吧 扯开线段树、平衡树...
    常见的数据结构运用总结
    

    考虑到Obsidian三个成员的擅长领域,这段时间都在做杂题,算是学习各种算法吧,趁现在休息的时间,而且大家马上要备战今年的比赛了,写写自己专攻方面的一些心得吧

    扯开线段树、平衡树这些中高级的东西,先说说基础的数据结构



    算是代码量最小的数据结构?出栈进栈都只有一句话而已

    常见用途:
    消去一个序列中的相同元素(做法大家应该都知道了吧,见过很多次了)
    维护一个单调的序列(所谓的单调栈,dp的决策单调?)
    表达式求值(经典的栈运用,如果使用的很熟悉的话,可以处理一元、二元运算,不过最近没见过类似的题目了)
    用于辅助其他算法(计算几何中的求凸包)

    队列

    队列应该还是很常见的数据结构了,如果专攻图论的话,spfa应该是写烂了的
    这里说到的队列,是狭义的普通的队列和循环队列,不包括后面讲的一些变形
    注意循环队列的写法,尽量不要使用取模运算,不然的话,遇到不厚道的出题者,可以把取模的循环队列卡到死

    常见用途:
    主要用于辅助其他算法,比如说spfa,bfs等(建议习惯用stl的孩子手写queue,毕竟就几行代码而已,偷懒会付出代价的。。。)

    双端队列

    如果写dp写的多的话,这个东西应该还是算是比较基础的东西了,双端队列多用于维护一个满足单调性的队列
    还是建议手写,stl的deque使用块状链表写的,那东西的复杂度是O(Nsqrt(N))的,不要被迷惑了。

    常见用途:
    dp的单调性优化,包括单调队列优化和斜率优化,都要用到这个结构
    计算几何中的算法优化,比如半平面交
    树的分治问题中利用单调队列减少转移复杂度

    链表 Dancing Links

    写图论的不要告诉我不会写这货,链表可以写单双向,循环非循环的,高级点儿的可以考虑十字链表,麻花链表
    不过链表可以说是树形结构的基础,如果这个掌握的不好,那么树形结构写起来就会很纠结
    链表的优势在于可以O(1)的插入删除,如果要求插入的位置只是在序列的两端的话,这个数据结构是最方便的了(无视双端队列)
    hash表就是用链表实现的,熟悉hash的同学可以试试看怎么使你的hash效率提高

    常见用途:
    图的邻接表,维护不确定规模的二维数组
    约瑟夫问题,复杂度O(NlogN)
    单纯考链表的题目,比如说类似文本编辑器的东西
    算法实现上辅助,比如说POJ3183
    搜索优化,最经典的就是Dancing Links
    维护路径,嗯,这类问题就比较恶心了,有两题都是类似的问题,题的名字都叫做植物大战僵尸……

    字典树 自动机

    字典树又称为前缀树,用于维护一系列串(不一定是字符串,可以把一个数字看成二进制串,k进制串等),我们可以通过字典树解决很多关于串的问题

    常见用途:
    字符串匹配(最基础的用途了吧)
    字符串hash(利用字典树可以在O(N)的时间内查出一个串是否在集合中,N是串的长度)
    构建dp转移矩阵(其实很多题目都是利用自动机构建转移矩阵,然后矩阵快乘的,这也算是比较基础的运用了)
    字符串在自动机上的dp(这个是很大的一块,算是自动机最大的运用点)

    堆 优先队列

    堆在这段时间运用的次数明显增加了很多,自从某学校出了那计算几何扫描线之后,大家对这个数据结构不像原来那么陌生了
    普通堆代码量在20到30行左右,如果需要支持更改权值,删除特定结点的操作的话,需要改点堆,代码会多那么10行左右
    大家对于堆的最早理解,可能就是堆优化dij了,这个也算是它的一个很重要的运用吧

    常见用途
    堆优化 dijkstra(很经典的运用)
    极角扫描线(详见Visible Segments)
    某些贪心的题(我记得ZOJ月赛出过好几次的?CF也有类似的题目,还有一题经典的倒水问题HDU1692)
    堆优化的prim(已经很久没见过非要这么写的题目了,最经典的问题是最优比例生成树)
    搜索中的优化(大家都懂得,A*算法基于优先队列)
    满足偏序关系的集合(其实极角扫描线算是这个的一个子类了,很多问题可以转化过来)

    并查集

    这个东西应该在关于树的问题中非常常见了,用在非常多关于集合的合并问题上

    常见用途:
    离线LCA(tarjan算法的精髓就是并查集)
    集合维护,比如说POJ的食物链和我们OJ的Food,这个算是扩展并查集的经典运用之一

    几类可以用基础数据结构解决的经典树上统计问题
    求一颗树中任意两点间的距离,我们可以离线LCA,利用并查集维护点到父亲结点的距离,每次找到LCA之后,在LCA结点拉一个处理链表,回溯到LCA的时候处理全部以这个点为LCA的所有查询。
    静态查询一棵树某条路径上的最大最小边权,利用并查集维护点到其父亲结点这条路径上的最大边权即可。
    给你一棵树,叫你求一条有向路径上前面一个点减去后面一个点的点权差值最大,依然是扩展并查集,怎么实现大家自己想吧。
    还有一题是HDU的3804,很经典的题目,这题可以用四种不同的方法过,大家有兴趣的可以YY一下。

    基础的数据结构告一段落,下面主要讲讲线段树和树状数组的运用吧,直接说常见用途了,毕竟这个大家用的太多了

    常见用途(不扩展):
    dp优化(非常多的dp问题可以用树状数组和数据结构来优化,比如说我们校赛初赛和决赛的某题,dp专题的某题,还有LIS的O(NlgoN)优化等等)
    括号序列、树的线性序列统计问题(之前发过了,就不扩展了)

    更新点查找区间,更新区间查找点
    这个经典问题都是可以利用树状数组来做的,可以说树状数组太强大了,代码短常数小,如果遇到此类的问题,那就是裸的不能再裸了,专攻数据结构的,需要对这类问题的经典模型尽量多的进行掌握。
    这类问题最常见的用处就是求逆序对(HDU1394)和求一个区间内一堆直线相交的个数(保证不会有三条直线交于一点,例子ZOJ3157)
    URAL1470,三维树状数组,其实和二维没啥区别,就是要抓住如何更新
    树状数组的经典运用有两题经典题,一个是POJ2828,一个是HDU3436,后者是前者的动态版,如果可以自己想出这两题的做法,基本上基础的树状数组题目是没有问题了。

    更新区间查找区间
    这类问题一般是不能使用树状数组来做的(那啥用差分求区间和的无视,那种只是特例而已),一般正式比赛考察的比较多的就是这类问题,非常重视对懒操作的实现,一般建议大家写一个上传和一个下放函数,即使是就一行,写到函数中,扩展起来可以更方便。
    如果想锻炼自己对数据结构的掌握程度,可以尝试利用树状数组和线段树来做Memory Control这题,如果能想出三种或者三种以上的状态定义方法,就基本上合格了。
    另外还有一题非常好的考察基本功的题目,是HDU1199,一般的离散化是会有问题的,就看大家怎么写了。
    对于懒操作考察的另外一题是POJ3225,算是比较经典的区间翻转的范例了。
    如果以上的题目都解决了,就去写zhymaoiing的Rain in the ACStar吧,我们OJ就有,这题写了 基本上对计算几何和数据结构的综合就有感觉了。
    最后建议大家去写写SPOJ的GSS系列和QTREE系列,这两个系列在后面会专门提到。

    扫描线
    这种问题主要遇到的模型有以下几种,括号中是对应的时间复杂度
    给你N个矩形,求矩形的并面积(O(NlogN))
    给你N个矩形,求矩形的并周长(O(NlogN))
    给你N个矩形,每一个矩形有一定的权值,权值最多有K种,求加权的面积并,其中重叠部分用最大权值计算(O(NKlogN))
    给你N个矩形,叫你求被覆盖恰好K次或者至少K次的面积(O(NKlogN))
    给你N个矩形,每一个矩形有一定的权值,权值最多有K种,求加权的面积并,其中重叠部分用特定的公式计算混合权值(O(2^K*NlogN))
    给你N个点,用一个矩形覆盖最多的点(O(NlogN))
    给你N个点,M个矩形,询问每一个点是否被包含在任意一个矩形中(O((N+M)log(N+M)))
    给你N个点,点分为可选点和不可选点,询问用一个矩形覆盖的最多可选点的数量,任何不可选点都不能被覆盖,询问覆盖最多点的方案数(O(NlogN))

    *树链剖分 QTREE
    这个是很大的一块,但是也是很恶心的一块内容,如果你觉得自己基础的问题都没有了的话,可以考虑两个选择,一个是学习这个,另外一个就是做做GSS
    熟练剖分详看漆子超的论文,具体实现就不讲了,常见的题目,最经典还是SPOJ的QTREE系列了,这个对代码能力的要求还是很苛刻的,在比赛中,如果遇到这类问题,如果又没有强大的代码能力,又没有足够的时间,那就不要去碰它吧。此外剖分推荐GSS7,经典题之一。
    我做过的剖分题的列表:SPOJ QTREE1-4 HDU3601 POJ3237 ZJOI2008树的统计 SPOJ GSS7 HDU3804(如果想写就写吧,这题不用剖分的) HDU3966(依然是一道可以不用剖分的题目)

    *GSS系列解释
    GSS系列是SPOJ的经典线段树题了,其中1、3、5是基础的题目,建议大家在学习了线段树后作为强化用,GSS2和GSS7,其中GSS2是一个非常经典的模型,建议大家花一周的时间慢慢啃,如果自己思维好的话,有可能一个下午想出做法,不过那个题不是想出来就能写出来的。。。GSS7是一个剖分,算是裸的题目了,就是维护的量太多,建议大家代码能力提高之后再来写写。GSS6不是基础的数据结构题,我将在后面提到这题。

    以上的数据结构可以覆盖区域赛的中低档题,其中GSS2如果在区域赛中,完全可以算是难题了(前提是没见过此类问题),对于区域赛中,这些数据结构可以说占了90%以上

    下面是一些偏们的数据结构和一些高级数据结构的介绍

    划分树

    划分树是一个可以在O(NlogN)时间内求出每一个子区间内第K小的数的数据结构,可以算是模板化的东西了,经常和树状数组结合来考察,不过考的不多,所以建议如果专攻数据结构的可以考虑学习一下,但是不要太过于钻难题。

    左偏树 斜堆

    两类经典的可合并堆,可以在O(NlogN)时间内对数集进行合并,维护最值,建议学习一个,不建议都学习,我觉得没必要。

    块状链表

    可以说在Splay没有出来的年代,这个是万能的武器,在O(Nsqrt(N))的时间内可以进行序列的翻转、查询操作,可以算是非常无敌了,但是在Splay出来了之后基本上就被遗弃了,不过块状链表的思想是非常好的,CF经常考察利用块状链表做的题目,要学习的话,就专门去看看其思想吧

    跳表

    这个利用链表进行优化的数据结构,基本上没啥用处,不过可以提提,时间复杂度是均摊的,没有发现一定要这个数据结构解决的问题

    平衡树

    平衡树可以做几乎所有关于数集的维护操作,常见的平衡树有SBT和Splay,一般的话,建议如果专攻数据结构的可以在巩固了基础数据结构的基础上,学学这两种平衡树。对这两种结构进行比较,Splay的功能和SBT比起来,强大了不止一个档次,但是相应地,其代码量也大了不止一个档次。按照 我的代码风格,SBT的代码一般维持在150行左右,但是非要Splay来写的题目,一般代码量会超过200行,甚至超过300行。
    如果是对数据集合进行维护,我们一般考虑使用SBT,因为其编码十分方便,常数相对也小了很多,所以首选是这个。相反的,如果涉及到维护序列的问题,那么就需要使用Splay来维护了。
    记住一点,那就是好的代码风格,对数据结构的专攻者来说,是非常重要的,相同的结构,有的人需要300行,而且查代码十分不方便,好一点的写法,可以在150行左右解决。对于最简单的SBT问题,一般代码量可以保证在100行左右,那么也就差不多了。毕竟代码写的乱的话,写挂了就不好查了,队友更没办法帮你差,这样就会悲剧。

    SBT相关的问题,最基础的是树的遍历和数集的统计问题,比如说举个例子:
    给你10^9个数,有两种操作,一个是查询第K小的数是多少,一个是删除第K小的数,很明显,这种动态的问题是不能使用离散化加树状数组来实现的,因为删除的元素也是不确定的。
    看到这题第一眼的反应,树状数组,但是发现删除的也是第K小,那么我们就只能使用平衡树了,注意我们肯定不能把10^9个数加入到集合中,这样会MLE的,具体的做法自己可以想想,其实和前面提到的Queue Jumper那题类似,需要一个转化。

    常见的SBT操作,需要掌握的有以下几个:
    数集相关的操作:
    插入删除元素,查询一个比K小的数的个数,查询树中第K小的数,查找元素的前趋后继,查询一个数在集合中出现的次数,删除第K小的数,查询最值。
    序列相关的非动态操作(不需要查询区间或者做区间翻转等高级操作)
    把一个元素插入到指定位置,删除第K个位置的元素。

    对于Splay,我想说的是,这个数据结构运用的地方实在太多了,基本上其他平衡树可以做的,它都可以,但是它可以做的,其他平衡树不一定可以做。去年天津赛区的现场赛还有福州赛区的网络赛都考到了Splay的运用,这种题目在区域赛中一般难度都比较大,平时的话,多写写就当作锻炼代码能力吧。
    这里列举一些Splay可以做的事儿,其中SBT可以完成的我就不列举了。
    给你一个双关键字的集合,求满足第一关键字在[l,r]区间内的结点的最小关键字(Parking Log),维护一个序列,求[l,r]的和、最大连续子字段和,对[l,r]区间进行翻转操作(维护数列),叫你维护一个可合并可拆分的并查集,其中拆分是一个元素从一个集合转移到另外一个集合(LRJ的数据结构专场,DS@HUST,当然这题可以不用Splay),给你一些结点,现在有合并两个集合,查询集合的最值、第K大操作(四川省OI2011棘手的操作,2011天津赛区Graph and Queries)。

    此外我们可以把Splay运用到树链剖分中去,利用Splay进行路径剖分,用splay forest来维护路径,这样可以在O(NlogN)时间内维护一棵树,甚至是一个森林所有树的特性,这就是经典的动态树问题,如果想了解的,可以问我,不过前提是把基础的啃透了:)

    平衡树的资料还是很多的,推荐陈启锋的《Size Balanced Tree》以及某论文《利用伸展树解决维护数列问题》,对于动态树的论文,个人认为中文版的都是不能看的,推荐Tarjan的lecture。

    对于数据结构的其他方面
    高级数据结构需要的是一个自己非常熟悉的模板(前期还是要靠模板活的,熟悉之后的话另当别论了,当然比赛带上模板可以心安),不过对于数据结构, 个人不推荐贴模板,这个如果养成了习惯的话,代码能力是绝对上不来的,如果学了高级数据结构的话,建议每次有题写的时候自己手敲一下,就当培养感情吧。
    展开全文
  • 校园导航数据结构

    2013-07-08 09:24:57
    设计你的学校的平面图,至少包括10个以上的景点(场所),每两个景点间可以有不同的路,且路长也可能不同,找出从任意景点到达另一景点的最佳路径(最短路径)。
  • 数据结构课程设计 -- 校园导航,c语言数据结构课程设计_校园导航系统__课程设计报告
  • python 数据结构五 之 图

    千次阅读 2017-08-25 19:16:18
    python数据结构教程第五课 在计算机的数据结构领域和课程里,图被看作一类复杂数据结构,可用于表示具有各种复杂联系的数据集合,在实际应用中非常广泛 一、简介 二、图的抽象数据类型(ADT) 三、图的表示方式 四...
  • 假设有一些代码用来从字符串的固定位置中取出具体的数据(比如从一个平面文件或类似的格式:平面文件flat file是一种包含没有相对关系结构的记录文件): ########...
  • (1) 设计校园平面图,所包含景点少于10个,以图中顶点表示学校各景点,存放景点名称、代号、简介等信息:以边表示路径,存放路径长度等相关信息。注意:设校园平面图是无向图。 (2) 为来访客人提供图中任意...
  • 数据结构课程设计~校园导航问题

    千次阅读 多人点赞 2019-01-12 16:15:31
    下边发一下数据结构的课程设计:校园导航问题。 设计内容 (1)设计学校的平面图(至少包括10个以上的场所)。每两个场所间可以有不同的路径,且路长也可能不同(图形结构要求通过键盘输入数据后采用创建图的算法...
  • 数据结构-校园导航问题

    热门讨论 2009-05-13 17:16:38
    数据结构:用图来描述校园内各个单位,顶点包括名称和简介,边包括两个端点和距离。 结果形式:输入要查询的单位,显示单位简介。输入两个单位,计算两个单位地点间最短距离。 测试数据:校园单位可包括:前门、...
  • 半边数据结构

    千次阅读 2011-09-01 16:15:48
    实体的B-rep表示模型是一非常复杂的模型,要求能够表达出多面体各几何元素之间完整的几何和拓扑关系,并且允许对这种几何和拓扑关系进行修改.在B-rep表示中,体、面、边和顶点是最基本的几何元素,在实体的拼合、...
  • 高级数据结构之K-D-TREE

    千次阅读 2016-10-26 21:42:49
    k-d-tree(即k-dimensional tree)是一棵形如二叉树的一种非常重要的空间划分数据结构,尤其在多维数据访问中有重要应用。特别是机器学习中的kNN(k近邻)最常用到的搜索算法就是以k-d-tree为依托来执行的。k-d-tree...
  • 数据平面、控制平面、管理平面

    万次阅读 2017-03-16 14:50:10
    交换机数据平面:交换机的基本任务是处理和转发交换机各不同端口上各种类型的数据, L2/L3/ACL/QOS/组播/安全防护等各种具体的数据处理转发过程,都属于交换机数据平面的任务范畴。  交换机控制平面:交换机的...
  • SDN数据平面

    千次阅读 2019-05-08 18:03:09
    1.传统网络数据平面 1.1 数据包的处理流程 1.2 数据的转发处理的特点 2. SDN数据平面架构 2.1 OF交换机的转发模型 3. PISA架构 1.传统网络数据平面 传统网络交换设备的功能架构主要由控制平面数据平面组成...
  • 系统设计你的学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。
  • 数据结构与算法小结(1)

    千次阅读 2016-02-17 23:17:28
    一、概述数据结构,即数据存放的方式。算法,解决问题的方法。讨论数据结构与算法时,常常不会仅仅满足于能解决一个特定的问题,而是在追求如何优雅而高效的解决一类问题。 本文针对学堂在线的数据结构课程的小结,...
  • 设计你的学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。
  • 源代码:设计我校的平面图导航,至少包括10个以上的场所,每两个场所间有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。
  • 数据结构课程设计,代码在vc下成功,还有所有的文档包括实验报告。
  • SDN数据平面简介

    千次阅读 2019-05-12 15:29:06
    传统网络数据平面 数据平面主要执行网络控制逻辑,数据包的处理主要通过查询由控制平面所生成的FIB表 来完成。处理流程: 传统网络数据平面的特点 – 数据转发处理都是协议相关的; – 只支持有限的用户配置,...
  • 半边数据结构及其使用

    千次阅读 2015-09-04 09:53:15
    实体的B-rep表示模型是一非常复杂的模型,要求能够表达出多面体各几何元素之间完整的几何和拓扑关系,并且允许对这种几何和拓扑关系进行修改.在B-rep表示中,体、面、边和顶点是最基本的几何元素,在实体的拼合、...
  • 文章目录第一节 地理空间及其表达第二节 空间数据采集第三节 属性数据采集第四节 空间数据格式转换第五节 空间数据质量 第一节 地理空间及其表达 1.1 地理空间 地理空间上至大气电离层,下至地幔莫霍面,是生命过程...
  • 数据结构”课程设计题目

    万次阅读 2016-09-09 18:38:24
    数据结构”课程设计题目 1、城市链表 [问题描述] 将若干城市的信息,存入一个带头结点的单链表。结点中的城市信息包括:城市名,城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新...
  • 06-VTK基本数据结构(4)

    千次阅读 2013-02-03 22:05:24
    至此,我们知道,数据集由组织结构和与之关联的属性数据构组成,组织结构包括拓扑结构和几何结构数据集的类型是由它的组织结构决定,同时数据集的类型决定了点和单元之间的相互关系,图6.11列出了常见的数据集类型...
  • (一)基本数据类型OpenCV中有多种基本数据类型,虽然这些数据类型在C语言中不是基本类型,但结构都非常简单,在”OpenCV/cxcore/include“目录下的cxtypes.h文件下可以查看其详细定义。(1)CvPoint其中最简单的...
  • 完整代码及文档已上传 一 . 设计目的 随着高校的发展,校园面积不断扩大,校园内跨区域活动频繁,为了给校内师生和校外人士办公、教学、生活...设计学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且
  • 【OpevCV数据结构归总】

    千次阅读 2011-10-19 20:09:02
    OpenCV里面用到了很多图像相关的数据结构,熟练掌握它们是学习图像的基础。 1、IplImage IplImage IplImage IPL 图像头 typedef struct _IplImage { int nSize; /* IplImage大小 */ ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 61,536
精华内容 24,614
关键字:

关系数据结构包不包含平面数据

数据结构 订阅