Skip to content

douchuan/algorithm

Repository files navigation

Overview

This repository contains the Rust source code for the algorithms in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

The official Java source code is here.

Goals

Make a Rust implementation of the library so that a Rust programmer can follow this book easily or prefer to demonstrate the algorithms using Rust.

Try to keep the interface and variable name consistent with the original book while writing idiomatic rust code.

I hope that this project helped you understand why Rust is so wonderful and loved right now. Rust is proving to be a productive tool for reliable and efficient software. In Rust, the compiler plays a gatekeeper role by refusing to compile code with these elusive bugs, including concurrency bugs. By working alongside the compiler, you can spend your time focusing on the program’s logic rather than chasing down bugs. After you finish a day's work, go home and rest, can be at ease a good night's sleep, never worry about system crash.

Index

The table index follow.

1 FUNDAMENTALS
1.2 Stack LIFO stack
1.3 Queue FIFO queue
1.4 LinkedList multiset (linked list)
1.5 QuickFindUF quick find
- QuickUnionUF quick union
- WeightedQuickUnionUF weighted quick union
- UF union-by-rank with path halving
2 SORTING
2.1 insert.rs insertion sort
2.2 selection.rs selection sort
2.3 shell.rs shellsort
2.4 merge.rs Merge Sort
2.5 quick.rs quicksort
- Quick3Way quicksort with 3-way partitioning
2.6 PQ::new_max_pq max heap priority queue
- PQ::new_min_pq min heap priority queue
- IndexPQ::new_min_pq index min heap priority queue
- IndexPQ::new_max_pq index max heap priority queue
- TopM Find the largest M elements
2.7 floyd.rs heapsort
3 SEARCHING
3.4 rb2.rs red-black tree
3.6 SparseVector sparse vector
4 GRAPHS
- Graph undirected graph
- DepthFirstSearch depth-first search in a graph
- NonRecursiveDFS DFS in a graph (nonrecursive)
4.1 DepthFirstPaths paths in a graph (DFS)
4.2 BreadthFirstPaths paths in a graph (BFS)
4.3 CC connected components of a graph
- Bipartite bipartite or odd cycle (DFS)
- Cycle cycle in a graph
- SymbolGraph symbol graph
- Digraph directed graph
4.4 DepthFirstPaths paths in a digraph (DFS)
- BreadthFirstPaths paths in a digraph (BFS)
- DirectedCycle cycle in a digraph
4.5 Topological topological order in a DAG
- TransitiveClosure transitive closure
4.6 KosarajuSCC strong components (Kosaraju–Sharir)
- EWGraph edge-weighted graph
- LazyPrimMST MST (lazy Prim)
4.7 PrimMST MST (Prim)
4.8 KruskalMST MST (Kruskal)
- EdgeWeightedDigraphCycle edge-weighted digraph
4.9 DijkstraSP shortest paths (Dijkstra)
- DijkstraAllPairsSP all-pairs shortest paths
4.10 AcyclicSP shortest paths in a DAG
- AcyclicLP longest paths in a DAG
- CPM critical path method
4.11 BellmanFordSP shortest paths (Bellman–Ford)
- Arbitrage arbitrage detection
5 STRINGS
- Alphabet alphabet
- count.rs alphabet client
5.1 LSD LSD radix sort
5.2 MSD MSD radix sort
5.3 Quick3String 3-way string quicksort
5.4 TrieST multiway trie symbol table
5.5 TST ternary search trie
5.6 KMP substring search (Knuth–Morris–Pratt)

Running

# setup Rust Toolchain
make test

Roadmap

  • Implement algorithms in the textbook Algorithms, 4th Edition
  • Algorithms visualization (Easy to study and short learning curve)