Skip to content

wangyoucao577/algorithms_practice

BranchesTags

Repository files navigation

algorithms_practice

Learn and practice algorithms and data structures. 来源包括但不限于《算法导论》, hankerrank, leecode, 北京大学 PKU JudgeOnline, etc.

实验环境

编译与运行主要在Linux上进行, 但代码都应属于平台无关的, 理论上不限于操作系统/编译器等.

  • Ubuntu 18.04 LTS: WSL(Windows Subsystem for Linux) on Win10 1803-17134.228
  • cmake version 3.10.2
  • gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0
  • go version go1.10.1 linux/amd64

实验代码

虽说都是实验代码, 但大部分提供了封装好的golang pkg, 可直接导入作为基础库使用. 内部进行实验时, 也尽可能地拆分成pkg以解耦.

[Golang] 排序

学习各种排序的实验代码，主要参考《算法导论 第3版》，

  • 包括:
    • 比较排序算法: 插入排序(Insertion Sort)、归并排序(Merge Sort)、堆排序(Heap Sort)、快速排序(Quick Sort)
    • 非比较排序算法: 计数排序(Counting Sort)、基数排序(Radix Sort)、桶排序(Bucket Sort)
    • 其他算法: 选择第n-th元素(Select n-th Element)、基于Binary Search Tree的排序(Tree Sort)
  • 详见:
    pkg - mysorts

[Golang] 最大子数组问题

  • maxsubarray
    解决最大子数组问题(Maximum Subarray Problem)的实验代码.
    • divide_and_conquer_algorithm.go: O(n*log(n)) 实现《算法导论 第3版》 ch4.1 最大子数组问题 中介绍的基于分治法(Divide and Conquer Alogrithm)的实现. 其基本原理为将原数组分解为两个子数组, 分别求解两个子数组的最大子数组及同时跨两个子数组的最大子数组, 取最大值为最大子数组. 递归地执行这个过程直至求到最终解.
    • violent_solution.go: O(n^2) 实现暴力方法求解, 即遍历所有子数组的可能, 从而取出最大子数组.
    • kadane_algorithm.go: O(n) 实现《算法导论 第3版》 习题4.1-5 中所描述的线性算法. 基本原理为同时记录到目前为止的max subarray以及以当前为止为ending的max subarray, 遍历下一个元素时, 要得到最大子数组, 要么为max subarray so far, 要么为 max(max subarray ending here + new element, new element). 伪代码可参考Maximum Subarray Problem - Kadane's algorithm.

[C++] 堆与优先队列

  • cc_heaps
    《算法导论 第3版》 ch6.5 介绍的基于最大堆/最小堆的优先队列的设计.
    • 最大优先队列Max Priority Queue一般支持Insert/Maximum/ExtractMax/IncreaseKey/Delete等操作(最小优先队列对应的为Insert/Minimum/ExtractMin/DecreaseKey/Delete).
    • 其基本原理仍然是基于最大堆/最小堆(与堆排序的原理非常类似), 即Insert时将新元素放在数组末尾然后进行up操作, 而ExtractMax/Delete时将对应元素与末尾元素交换后, 对当前元素进行down(i.e. MaxHeapity)操作, 从而维护堆的性质. 特殊处在于IncreaseKey/DecreaseKey操作, 需要记录针对每一个HeapNode的handle才能发起此操作. 实验中的handle直接用的是HeapNode的指针来表示.(std::priority_queue干脆就没有暴露这个接口, 所以看起来接口简单很多.)
    • NOTE:
      • 此处的实现代码, 基于BinaryHeap进行实现的, 且仅实现了MaxPriorityQueue. 而实际上同样可以基于d-ary heap来实现, 区别只是2-dry或d-ary.
      • Golang中目前不支持泛型, 也没有class/object等概念, 不太好实现一个封装起来的PriorityQueue. Golang源码库中的实现是给出了一些heap的操作函数Fix/Init/Push/Pop等, 而把内部的数据结构实现交给了使用者. 实现和使用思路都与一般的面向对象思路不同, 个人感觉是不太直观的, 所以这里用c++来实现了此处的实验代码, 看起来或许更直观些.
        • 另外, 下面的包minspanningtree中实现Prim算法时用到了MinHeap, 除借助golang的"container/heap"中提供的方法外, 也自己实现了一份在my_min_binary_heap.go中, 可供参考.
      • 当前代码中暂未考虑效率问题(如object的多处拷贝等), 实际使用的话应考虑优化, 如多采用std::move等. 另可参考boost::heap::d_ary_heap, Fibonacci heap等.
    • g++ -std=c++11 main.cc && ./a.out

[Golang] 二叉搜索树

  • binarysearchtree
    实现《算法导论 第3版》ch12 介绍的二叉搜索树的实验代码.
    • 二叉搜索树性质: 设x为二叉搜索树中的一个节点, 若y是x的左子树中的一个节点, 则y.key <= x.key; 若y是x的右子树中的一个节点, 则y.key >= x.key.
    • 二叉搜索树实现时, 一般每个node中都会记录parent/leftChild/rightChild三个指针以维护树的结构, 同时node中需记录key以维护二叉搜索树的性质. 可选的node中可能会记录额外的payload.
    • 二叉搜索树一般至少会提供接口: (实现在binary_search_tree.go中)
      • Minimum()/Maximum(): O(h) 返回最小/最大key的节点(同MinHeap/MaxHeap中的Minimum()/Maximum())
      • Successor()/Predecessor(): O(h) 返回当前node的Succesor/Predecessor节点
        • Successor节点: >= node.key 的最小key节点
        • Predecessor节点: <= node.key 的最大key节点
      • Insert(): O(h) 插入一个新的节点(总是会插入为tree的leaf)
      • Delete(): O(h) 删除一个新的节点. 实现上最复杂的一个接口, 主要是要删除的节点同时存在leftChild和rightChild时的情况比较复杂.
      • Search(): O(h) 搜索一个指定key的node.
      • InorderTreeWalk(): O(n) 中序遍历, 即总是按照 node.leftChild => node => node.rightChild 的顺序递归遍历.
        • 注: 由于二叉搜索树的性质, 中序遍历的结果总是按照key升序排序的. 也即可以通过二叉搜索树来实现排序. 我的实验代码见 mysorts - tree sort.
      • PreorderTreeWalk(): O(n) 先序遍历, 即总是按照 node => node.leftChild => node.rightChild 的顺序递归遍历.
      • postorderTreeWalk(): O(n) 后续遍历, 即总是按照 node.leftChild => node.rightChild => node 的顺序递归遍历.
    • 注: 以上分析的O(n)中的n为树中的总的节点数, O(h)中的h为树的高度, 最坏情况下h == n, 但平均情况接近最好情况即lg(n). 也即平均情况下Binary Search Tree的接口的运行时间为O(lg(n)).

[Golang] 红黑树

  • rbtree
    实现《算法导论 第3版》ch13 介绍的红黑树的实验代码.
    • 红黑树的性质(满足红黑性质的二叉搜索树即为红黑树):
      • 每个node都有一个color的属性, 要么是红色, 要么是黑色;
      • root node总是黑色的;
      • 每个leat node总是黑色的(为了实现的简便, 一般总是用一个sentinal nil node作为实现时的nil, 也即每个leaf node都是这个sentinal nil node, 只要它置为黑色即可满足此性质);
      • 如果一个node是红色的, 那么它的两个子node总是黑色的;
      • 对于每个node, 从该node到其所有后代leaf node的简单路径上, 均包含相同数目的黑色node.
    • 黑高(Black-Height)的定义: 从某个node出发(不包含该node)到达一个leaf node的任意一条简单路径上的黑色node数目, 即为黑高(Black-Height), 一般记作bh(node).
      • 定义root节点的黑高为红黑树的黑高.
    • 红黑树的Insert/Delete除了类似二叉搜索树的操作外, 都需要去维护红黑性质; 而维护了红黑性质后, 红黑树非常接近平衡树, 从而可以带来较好的平均性能.
    • 红黑树提供的接口与二叉搜索树完全一致, 复杂度分析也同样一致. 只是由于红黑树几乎为平衡二叉树, 树的高度总是为log(n)的, 所以接口的运行时间总是可以做到O(log(n)).
    • 非常好的学习资料(红黑树的Insert和Delete过程比较复杂, 以下资料个人认为讲的远好于书上. 而可能本质上就是需要枚举出所有的可能情况, 相对来讲书上枚举的不够详细. 跟着教程自己推导一遍, 收货颇丰):

[Golang] 图算法

golang_pkg_import_graph

  • graph
    通常使用符号 G(V, E) 来表示一张图, 其中 V 为点数, E 为边数. 此pkg定义了一堆表示graph的类型与通用接口, 支持包括邻接链表(Adjacency List)和邻接矩阵(Adjacency Matrix)两种图的表示方法. 其中点通过从0开始的uint来表示, 所以邻接链表和邻接矩阵都基于了基础的slice来实现. 基础概念可参考《算法导论 第3版》 ch22.1 图的表示.
    注: 图论中的各种涉及到路径的算法, 通常都基于point-to-point来讨论, 而不是edge-to-edge, 从graph的表现形式就可以反映出这一点.

  • graphsamples
    构建好的graph的例子, 方便进行各种测试. 详见 graphsamples.

  • bfs

    • O(V+E)
    • 实现《算法导论 第3版》ch22.2 广度优先搜索 中的算法描述, Breadth First Search. 基本思路为搜索过程中从queue(借助其先入先出的特性)头上取下一次迭代的初始节点, 并将迭代到的节点存储到queue尾, 从而实现广度优先. 搜索过程中的tree的信息及depth等通过节点属性的形式保存在一个节点数组中.
    • 提供了基于bfs的生成level graph的实现, 以供dinic算法使用.

  • cmd/test_bfs
    执行package bfs代码的main.

  • dfs

    • O(V+E)
    • 实现《算法导论 第3版》ch22.3 深度优先搜索 中的算法描述. 本书章节中的伪码是基于递归的描述, 比较清晰易懂也容易实现. 实际coding时同时参考Depth-first search - Wikipedia实现了基于栈的实现. 注: 基于栈的实现一般来讲结果会和递归的实现不太一样, 主要是遍历的次序关系.
    • 《算法导论 第3版》ch22.4 拓扑排序(Topological Sorting) 也是依赖 Depth-first search - Wikipedia 的方法来实现的, 故其实现也放在了dfs包中. 由于graph中若存在环是无法拓扑排序的, 所以拓扑排序只能基于Directed Acyclic Graph, 依据此也可以通过dfs判断一个graph是否为Directed Acyclic Graph.
      • 拓扑排序的一个典型应用: 比如要做一个Continuous Delivery比较复杂的Pipeline(Pipeline上许多步骤间有依赖关系), 那么便可以先把步骤的依赖关系图先画出来, 算出拓扑排序, 再按照拓扑排序的顺序来梳理Pipeline的流程.
    • 《算法导论 第3版》ch22.5 强连通分量(Strongly Connected Component) 同样依赖2次 Depth-first search - Wikipedia 实现, 于是实验代码也放在dfs包中. 第一次基于默认graph进行DFS, 然后以timestampF倒序作为第二次遍历的node顺序; 第二次基于graph的转置(反转所有edge)来进行dfs, 然后以timestampF正序来进行遍历并输出Strongly Connected Component, 以每个dfs tree的root作为切分.
      • 注: 第一次dfs后的timestampF倒序, 看起来为上述拓扑排序的结果的倒序即可. 但实际上主要区别在于拓扑排序的graph必须无环, 而切分强连通分量几乎必然有环(否则就只好每个node为一个强连通分量). 所以并不能直接调用拓扑排序的函数实现.

  • levelgraph
    Dinic算法所要用到的分层图, 即以Depth-first search - Wikipedia在graph上进行搜索, 以每个node的depth作为level.

  • flownetwork
    描述maximum flow problem的流网络, 主要包含基于directed graph的图以及图上每两个node间(i.e. edge)的容量. 需要注意的是两个node间只能有单向的edge, 不能有反向. 同时为了描述maximum flow problem问题, 也记录了入点和出点.
    NOTE: flownetwork 与 weightedgraph 非常相似, 所以其实完全可以基于weightedgraph来实现. 此处仅仅是因为flownetwork有点类似于描述maximum flow problem的一个专用数据结构, 所以减少了依赖. 有必要的时候可以进行 refactor 以去除重复代码.

  • maxflow
    maximum flow problem的算法实现, 包括FordFulkerson, EmondsKarp, Dinic, etc. 在其内部的_test.go中以Drainage Ditches问题作为典型的测试用例.

    • FordFulkerson: O(E|f|) 基础的最大流问题解决方法. 定义了flow, residual network, augmenting path等重要的基础概念, 以及解决问题的一般思路.
    • EmondKarp: O(V(E^2)) 基于FordFulkerson, 在如何寻找augmenting path的方法上进行了扩展优化, 即以Breadth First Search来寻找点到点的最短路径, 效率更高.
    • Dinic: O((V^2)E) 依然是基于FordFulkerson的方法, 最主要的区别在于在生成residual network后, 先采用Breadth First Search来生成分层图(level graph, 以每个node的depth作为其层次), 再在level graph上寻找blocking flow(即直到不能再找到新的flow), 以此blocking flow作为residual network上的augmenting flow.

  • cmd/test_maxflow
    调用maxflow以解决maximum flow problem, 支持从stdin来构造flownetwork, 以更容易测试新的问题.

  • weightedgraph
    即在package graph定义的directed/undirected graph的基础操作上, 为每个edge增加一个weight值.

  • minspanningtree
    《算法导论 第3版》ch23 中所描述的最小生成树问题, 即在一张每条edge都有其weight的连通图上(一般是基于undirected graph讨论), 找到经过的所有node的sum(weight)最小的生成树.

    • 此处实验中实现了书上提到的两种算法:
      • Kruskal: O(E*log(V)) 按weight排序所有的edge, 从最小weight的edge开始一条一条取出来生成树. 每条取出的edge的两个node不属于同一个集合, 才是有效的edge.
      • Prim: O(E*log(V)) 借助了最小堆的概念, 从任意node开始构造最小堆, 每次从ExtractMin的node遍历邻接的node, 并将经过的edge的weight作为遍历到的node的key以更新维护最小堆的性质, 于是每次ExtractMin的node与它的parent间的edge一定为最小生成树的一部分.
        • 注: 据说借助Fibonacci heap来实现可以进一步优化运行效率.
    • 注: 关于最小生成树的问题, 个人认为几个视频讲的比书上要好, FYI:

  • shortestpaths
    《算法导论 第3版》ch24 中所讨论的 Single-Source Shorest Paths 问题, 即在一张每条edge都有其weight的连通图上(一般是基于directed graph, 但其实只要weight非负, 也完全可以在undirected graph上讨论), 找到从某个source-node开始到其他任意node的最短weight路径.

    • bellman-ford.go: O(VE) 迭代V-1次, 每次所有的edge以更新每个node上的cost(从source-node到当前node). 最后再迭代一次所有的edge以判断是非存在negative-cycle. bellman-ford算法实现比较简单, 但迭代次数较多, 主要优势是可以支持negative weight(不能有negative-cycle).
    • dijkstra.go: O((V+E)log(V)) 基于PriorityQueue每次总是以最小weight的node开始relax, 从而可以大大减少迭代的次数. 此处的复杂度是基于二叉堆实现的PriorityQueue来分析的. Dijkstra算法必须要求weight为非负的.
      • 注意:
        • 参照书上伪代码实现的此Dijkstra, 流程是首先将所有的node-priority pair加入到PriroityQueue中, 过程中有priority发生变化时再DecreaseKey, 所以会有非常大量的DecreaseKey动作.
        • 但实际工程上实现时多半都是先只将source-node加入到PriorityQueue中, 过程中再将新relax到的node加入PriorityQueue, 所以会有大量的Push动作, DecreaseKey则大大减少, 同时PriorityQueue的规模也是动态增加的而不是一开始加满.
        • 这也是为什么学术上经常会讨论如何优化DecreaseKey效率从而提升Dijkstra的性能, 但却并不适用于工程实现.
    • directed_acyclic_graph_shortest_paths.go: O(V+E) 先将所有的node使用dfs拓扑排序, 再按照拓扑排序的顺序从source-node开始遍历一次edge即可. 适用于有向无环图的特殊情况, 复杂度主要是由于拓扑排序.

References

About

Practice algorithms and data structures.

Topics

go golang cplusplus algorithms leetcode cpp data-structures maxflow maxflow-mincut intorduction-to-algorithms handrank

Resources

Readme

License

Apache-2.0 license
Activity

Stars

3 stars

Watchers

2 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages