The following is a list of well-known

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

s along with one-line descriptions for each.

Automated planning

Combinatorial algorithms

General combinatorial algorithms

* Brent's algorithm: finds a cycle in function value iterations using only two iterators * Floyd's cycle-finding algorithm: finds a cycle in function value iterations *

Gale–Shapley algorithm In mathematics, economics, and computer science, the Gale–Shapley algorithm (also known as the deferred acceptance algorithm or propose-and-reject algorithm) is an algorithm for finding a solution to the stable matching problem, named for David ...

: solves the stable marriage problem *

Pseudorandom number generator A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...

s (uniformly distributed—see also List of pseudorandom number generators for other PRNGs with varying degrees of convergence and varying statistical quality): ** ACORN generator ** Blum Blum Shub ** Lagged Fibonacci generator **

Linear congruential generator A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generat ...

Mersenne Twister The Mersenne Twister is a general-purpose pseudorandom number generator (PRNG) developed in 1997 by and . Its name derives from the fact that its period length is chosen to be a Mersenne prime. The Mersenne Twister was designed specifically to re ...

Graph algorithms

* Coloring algorithm: Graph coloring algorithm. *

Hopcroft–Karp algorithm In computer science, the Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum cardinality matching as output – a set of ...

: convert a bipartite graph to a

maximum cardinality matching Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is ...

Hungarian algorithm The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hu ...

: algorithm for finding a

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

* Prüfer coding: conversion between a labeled tree and its

Prüfer sequence In combinatorial mathematics, the Prüfer sequence (also Prüfer code or Prüfer numbers) of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on ''n'' vertices has length ''n'' − 2, and can be ...

Tarjan's off-line lowest common ancestors algorithm In computer science, Tarjan's off-line lowest common ancestors algorithm is an algorithm for computing lowest common ancestors for pairs of nodes in a tree, based on the union-find data structure. The lowest common ancestor of two nodes ''d'' and ...

: computes

lowest common ancestor In graph theory and computer science, the lowest common ancestor (LCA) (also called least common ancestor) of two nodes and in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both and as descendants, where ...

s for pairs of nodes in a tree * Topological sort: finds linear order of nodes (e.g. jobs) based on their dependencies.

Graph drawing

* Force-based algorithms (also known as force-directed algorithms or spring-based algorithm) *

Spectral layout Spectral layout is a class of algorithm for drawing graphs. The layout uses the eigenvectors In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar facto ...

Network theory

* Network analysis ** Link analysis ***

Girvan–Newman algorithm The Girvan–Newman algorithm (named after Michelle Girvan and Mark Newman) is a hierarchical method used to detect communities in complex systems.Girvan M. and Newman M. E. J.Community structure in social and biological networks Proc. Natl. Acad. ...

: detect communities in complex systems *** Web link analysis ****

Hyperlink-Induced Topic Search Hyperlink-Induced Topic Search (HITS; also known as hubs and authorities) is a link analysis algorithm that rates Web pages, developed by Jon Kleinberg. The idea behind Hubs and Authorities stemmed from a particular insight into the creation of we ...

(HITS) (also known as

Hubs and authorities Hyperlink-Induced Topic Search (HITS; also known as hubs and authorities) is a link analysis algorithm that rates Web pages, developed by Jon Kleinberg. The idea behind Hubs and Authorities stemmed from a particular insight into the creation of web ...

) ****

PageRank PageRank (PR) is an algorithm used by Google Search to rank web pages in their search engine results. It is named after both the term "web page" and co-founder Larry Page. PageRank is a way of measuring the importance of website pages. Accordi ...

****

TrustRank TrustRank is an algorithm that conducts link analysis to separate useful webpages from spam and helps search engine rank pages in SERPs (Search Engine Results Pages). It is semi-automated process which means that it needs some human assistance ...

Flow network In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations re ...

s **

Dinic's algorithm Dinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim (Chaim) A. Dinitz. The algorithm runs in O(V^2 E) ...

: is a

strongly polynomial In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...

algorithm for computing the

maximum flow In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such ...

in a

flow network In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations re ...

. **

Edmonds–Karp algorithm In computer science, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in O(, V, , E, ^2) time. The algorithm was first published by Yefim Dinitz (whose name is als ...

: implementation of Ford–Fulkerson ** Ford–Fulkerson algorithm: computes the

in a graph ** Karger's algorithm: a Monte Carlo method to compute the minimum cut of a connected graph ** Push–relabel algorithm: computes a

in a graph

Routing for graphs

Edmonds' algorithm In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an ''optimum branching''). It is the directed analog of the minimum spanning tree probl ...

(also known as Chu–Liu/Edmonds' algorithm): find maximum or minimum branchings * Euclidean minimum spanning tree: algorithms for computing the minimum spanning tree of a set of points in the plane *

Longest path problem In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path (graph theory), path of maximum length in a given Graph (discrete mathematics), graph. A path is called ''simple'' if it does not ha ...

: find a simple path of maximum length in a given graph *

Minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...

** Borůvka's algorithm **

Kruskal's algorithm Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. (A minimum spanning tree of a connected graph is a subset of the edges that forms a tree that ...

Prim's algorithm In computer science, Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every ...

Reverse-delete algorithm The reverse-delete algorithm is an algorithm in graph theory used to obtain a minimum spanning tree from a given connected, edge-weighted graph. It first appeared in , but it should not be confused with Kruskal's algorithm which appears in the sam ...

* Nonblocking minimal spanning switch say, for a

telephone exchange telephone exchange, telephone switch, or central office is a telecommunications system used in the public switched telephone network (PSTN) or in large enterprises. It interconnects telephone subscriber lines or virtual circuits of digital syste ...

Shortest path problem In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between t ...

Bellman–Ford algorithm The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it i ...

: computes shortest paths in a weighted graph (where some of the edge weights may be negative) **

Dijkstra's algorithm Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years ...

: computes shortest paths in a graph with non-negative edge weights **

Floyd–Warshall algorithm In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with p ...

: solves the all pairs shortest path problem in a weighted, directed graph ** Johnson's algorithm: all pairs shortest path algorithm in sparse weighted directed graph *

Transitive closure In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinit ...

problem: find the

transitive closure In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinit ...

of a given binary relation *

Traveling salesman problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...

Christofides algorithm The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle ine ...

** Nearest neighbour algorithm * Warnsdorff's rule: a heuristic method for solving the

Knight's tour A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again im ...

problem

Graph search

* A*: special case of best-first search that uses heuristics to improve speed * B*: a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node (out of one or more possible goals) *

Backtracking Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...

: abandons partial solutions when they are found not to satisfy a complete solution *

Beam search In computer science, beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Beam search is an optimization of best-first search that reduces its memory requirements. Best-first sea ...

: is a heuristic search algorithm that is an optimization of

best-first search Best-first search is a class of search algorithms, which explore a graph by expanding the most promising node chosen according to a specified rule. Judea Pearl described the best-first search as estimating the promise of node ''n'' by a "heuristic ...

that reduces its memory requirement * Beam stack search: integrates backtracking with

beam search In computer science, beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Beam search is an optimization of best-first search that reduces its memory requirements. Best-first sea ...

Best-first search Best-first search is a class of search algorithms, which explore a graph by expanding the most promising node chosen according to a specified rule. Judea Pearl described the best-first search as estimating the promise of node ''n'' by a "heuristic ...

: traverses a graph in the order of likely importance using a

priority queue In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a ''priority'' associated with it. In a priority queue, an element with high priority is se ...

* Bidirectional search: find the shortest path from an initial vertex to a goal vertex in a directed graph *

Breadth-first search Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next d ...

: traverses a graph level by level *

Brute-force search In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the soluti ...

: an exhaustive and reliable search method, but computationally inefficient in many applications * D*: an incremental heuristic search algorithm *

Depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alo ...

: traverses a graph branch by branch *

: a special case of A* for which no heuristic function is used * General Problem Solver: a seminal theorem-proving algorithm intended to work as a universal problem solver machine. * Iterative deepening depth-first search (IDDFS): a state space search strategy * Jump point search: an optimization to A* which may reduce computation time by an order of magnitude using further heuristics * Lexicographic breadth-first search (also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph *

Uniform-cost search Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years ...

: a

tree search In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. S ...

that finds the lowest-cost route where costs vary *

SSS* SSS* is a search algorithm, introduced by George Stockman in 1979, that conducts a state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm. SSS* is based on the notion of solution trees. Info ...

: state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm * F*: special algorithm to merge the two arrays

Subgraphs

* Cliques ** Bron–Kerbosch algorithm: a technique for finding maximal cliques in an undirected graph **

MaxCliqueDyn maximum clique algorithm The MaxCliqueDyn algorithm is an algorithm for finding a maximum clique in an undirected graph. It is based on a basic algorithm (MaxClique algorithm) which finds a maximum clique of bounded size. The bound is found using improved coloring algor ...

: find a maximum clique in an undirected graph * Strongly connected components **

Path-based strong component algorithm In graph theory, the strongly connected components of a directed graph may be found using an algorithm that uses depth-first search in combination with two stacks, one to keep track of the vertices in the current component and the second to keep ...

** Kosaraju's algorithm **

Tarjan's strongly connected components algorithm Tarjan's strongly connected components algorithm is an algorithm in graph theory for finding the strongly connected components (SCCs) of a directed graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's ...

* Subgraph isomorphism problem

Sequence algorithms

Approximate sequence matching

Bitap algorithm The bitap algorithm (also known as the shift-or, shift-and or Baeza-Yates–Gonnet algorithm) is an approximate string matching algorithm. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given patter ...

: fuzzy algorithm that determines if strings are approximately equal. * Phonetic algorithms ** Daitch–Mokotoff Soundex: a Soundex refinement which allows matching of Slavic and Germanic surnames ** Double Metaphone: an improvement on Metaphone ** Match rating approach: a phonetic algorithm developed by Western Airlines ** Metaphone: an algorithm for indexing words by their sound, when pronounced in English **

NYSIIS The New York State Identification and Intelligence System Phonetic Code, commonly known as NYSIIS, is a phonetic algorithm devised in 1970 as part of the New York State Identification and Intelligence System (now a part of the New York State Divisio ...

: phonetic algorithm, improves on Soundex ** Soundex: a phonetic algorithm for indexing names by sound, as pronounced in English *

String metric In mathematics and computer science, a string metric (also known as a string similarity metric or string distance function) is a metric that measures distance ("inverse similarity") between two text strings for approximate string matching or co ...

s: computes a similarity or dissimilarity (distance) score between two pairs of text strings **

Damerau–Levenshtein distance In information theory and computer science, the Damerau–Levenshtein distance (named after Frederick J. Damerau and Vladimir I. Levenshtein.) is a string metric for measuring the edit distance between two sequences. Informally, the Damerau–Leve ...

: computes a distance measure between two strings, improves on Levenshtein distance ** Dice's coefficient (also known as the Dice coefficient): a similarity measure related to the

Jaccard index The Jaccard index, also known as the Jaccard similarity coefficient, is a statistic used for gauging the similarity and diversity of sample sets. It was developed by Grove Karl Gilbert in 1884 as his ratio of verification (v) and now is fre ...

Hamming distance In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chang ...

: sum number of positions which are different **

Jaro–Winkler distance In computer science and statistics, the Jaro–Winkler distance is a string metric measuring an edit distance between two sequences. It is a variant proposed in 1990 by William E. Winkler of the Jaro distance metric (1989, Matthew A. Jaro). T ...

: is a measure of similarity between two strings ** Levenshtein edit distance: computes a metric for the amount of difference between two sequences *

Trigram search Trigram search is a method of searching for text when the exact syntax or spelling of the target object is not precisely known or when queries may be regular expressions. It finds objects which match the maximum number of three consecutive charac ...

: search for text when the exact syntax or spelling of the target object is not precisely known

Selection algorithms

* Quickselect *

Introselect In computer science, introselect (short for "introspective selection") is a selection algorithm that is a hybrid of quickselect and median of medians which has fast average performance and optimal worst-case performance. Introselect is relat ...

Sequence search

Linear search In computer science, a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. A linear search runs in at ...

: locates an item in an unsorted sequence *

Selection algorithm In computer science, a selection algorithm is an algorithm for finding the ''k''th smallest number in a list or array; such a number is called the ''k''th ''order statistic''. This includes the cases of finding the minimum, maximum, and median e ...

: finds the ''k''th largest item in a sequence * Ternary search: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa * Sorted lists **

Binary search algorithm In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the ...

: locates an item in a sorted sequence ** Fibonacci search technique: search a sorted sequence using a divide and conquer algorithm that narrows down possible locations with the aid of

Fibonacci numbers In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...

** Jump search (or block search): linear search on a smaller subset of the sequence **