1 Star 0 Fork 0

endpoint_rust/Algorithms

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
克隆/下载
贡献代码
同步代码
取消
提示: 由于 Git 不支持空文件夾,创建文件夹后会生成空的 .keep 文件
doc
Loading...
README
MIT

Rusty Algorithms & Data Structures for Learners

Crates.io Crates.io Continuous Integration Coverage Status lines of code

This repository presents Rust implementations of common algorithms and data structures, many of which are based on William Fiset's Java implementation: https://github.com/williamfiset/Algorithms . I highly recommend his YouTube channel, where he explains many of these algorithms in detail using illustrations, animations and pseudocode. I recommend that you implement these algorithms by yourself before comparing them to my or William's implementations, since the best way to learn is by doing, and it's likely that you discover ways in which the code can be written in a more efficient, robust and/or readable way, in which case you're welcome to submit a PR!

I also write algorithms that's not yet available in William's repository. When I do so I attach references (most of which are freely accessible) that I used and hopefully they should be sufficient to guide you to write your own implementations.

Usage

The implementation details are explained in comments and docs and the example usage is implied in unit tests. To run tests:

cargo test

I use LaTeX to write some math expression in docs. To render them correctly in docs, run:

RUSTDOCFLAGS="--html-in-header katex-header.html" cargo doc --no-deps --open

or an alias for this command:

./doc

Recommended Environment

This simple setup provides most features a decent IDE would provide (importantly, jump to definition and type labelling)

Contents

Search Algorithms

  • Binary Search
  • Interpolation Search
  • Ternary Search

Sort Algorithms

  • Merge sort
  • Selection sort
  • Bubble sort
  • Insertion sort
  • Counting sort
  • Heap sort
  • Radix sort
  • Bucket sort
  • Quick sort
    • Hoare partition

Graph

Graph Representations

  • Adjacency Matrix (Weighted & Unweighted)
  • Adjacency List (Weighted & Unweighted)
  • Condensed Adjacency Matrix (Weighted)

Fundamental Graph Algorithms

  • Depth-first search (iterative and recursive)
  • Breadth-first search (iterative)

Tree Algorithms

  • Tree representation: with or without pointer to parent
  • Fundamentals (DFS, tree height, tree sum, etc.)
  • Tree Center
  • Tree rooting
  • Tree isomorphism
  • Lowest common ancestor (LCA)

Minimum Spanning Tree/Forest

  • Prim's Algorithm
  • Kruskal's Algorithm

Network Flow

  • Ford-Fulkerson + DFS
  • DFS with capacity scaling
  • Edmonds-Karp Algorithm (BFS)
  • Dinic's Algorithm (BFS + DFS)

Shortest Path

  • BFS (unweighted)
  • DAG shortest path with topological sorting
  • Dijkstra's algorithm (non-negative weights, SSSP)
  • Bellman-Ford algorithm (SSSP)
  • Floyd-Warshall algorithm (APSP)

Others

  • Bipartite check
  • Topological sorting of DAG graphs and DAG shortest path
  • Eulerian path/circuit
  • Strongly connected components (Tarjan's algorithm)

Data Structures

  • Bit manipulation
  • Priority queue (binary heap)
  • Balanced tree
    • AVL tree
  • Disjoin set (union-find)
  • Sparse table (range query) (generic)
  • Quadtree
  • k-dimensional tree (k-d tree)

Machine Learning

Clustering

  • Hierarchical clustering (WIP, almost done)

K Nearest Neighbour (KNN)

  • in quad tree (docs/annotations WIP)
  • in k-d tree (docs/annotations WIP)

Math

  • GCD
    • Euclidean algorithm
    • Coprime
    • Extended euclidean algorithm
  • LCM
  • log2
  • Prime numbers
    • Prime check
    • Sieve of Eratosthenes
    • Prime factorization (Pollard's rho algorithm)

Linear Algebra (docs/annotations WIP)

  • Basics (matrix representation, matrix/vector arithmetics)
  • Determinant of square matrix (Laplace expansion)
  • Gauss-Jordan Elimination
  • LU Decomposition
  • Cholesky Decomposition

Problems

Dynamic Programming

  • Edit distance
  • Knapsack 0/1

Back Tracking

  • Sudoku
  • N-Queens

Graph

  • Travelling salesman problem (brutal force & DP)

Network Flow

  • Mice and owls
MIT License Copyright (c) 2020 Tianyi Shi Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

简介

一个Github仓库,一些常用算法和数据结构的Rust实现,其中大多数基于William Fiset的 Java 实现 展开 收起
README
MIT
取消

发行版

暂无发行版

贡献者

全部

近期动态

不能加载更多了
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/endpoint_rust/Algorithms.git
git@gitee.com:endpoint_rust/Algorithms.git
endpoint_rust
Algorithms
Algorithms
main

搜索帮助