Used On Used For Better On Name Pseudocode or Steps
Graphs Topological sorting . Kahn's algorithm L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else
    return L (a topologically sorted order)
Flow Control . Edmonds-Karp algorithm EdmondsKarp
    input:
        C[1..n, 1..n] (Capacity matrix)
        E[1..n, 1..?] (Neighbour lists)
        s             (Source)
        t             (Sink)
    output:
        f             (Value of maximum flow)
        F             (A matrix giving a legal flow with the maximum value)
    f := 0 (Initial flow is zero)
    F := array(1..n, 1..n) (Residual capacity from u to v is C[u,v] - F[u,v])
    forever
        m, P := BreadthFirstSearch(C, E, s, t, F)
        if m = 0
            break
        f := f + m
        (Backtrack search, and write flow)
        v := t
        while v ≠ s
            u := P[v]
            F[u,v] := F[u,v] + m
            F[v,u] := F[v,u] - m
            v := u
    return (f, F)
Minimum
spanning tree
Lots of edges Prim's algorithm 1. Associate with each vertex v of the graph a number C[v] (the cheapest cost of a connection to v) and an edge E[v] (the edge providing that cheapest connection). To initialize these values, set all values of C[v] to +∞ (or to any number larger than the maximum edge weight) and set each E[v] to a special flag value indicating that there is no edge connecting v to earlier vertices.

2. Initialize an empty forest F and a set Q of vertices that have not yet been included in F (initially, all vertices).

3. Repeat the following steps until Q is empty:
  3.1 Find and remove a vertex v from Q having the minimum possible value of C[v]
  3.2 Add v to F and, if E[v] is not the special flag value, also add E[v] to F
  3.3 Loop over the edges vw connecting v to other vertices w. For each such edge, if w still belongs to Q and vw has smaller weight than C[w], perform the following steps:
    3.3.1 Set C[w] to the cost of edge vw
    3.3.2 Set E[w] to point to edge vw.

4. Return F
Few edges
best with:
Fibonacci Heap
Kruskal's algorithm KRUSKAL(G):
  A = ∅
  foreach v ∈ G.V:
     MAKE-SET(v)
  foreach (u, v) ordered by weight(u, v), increasing:
     if FIND-SET(u) ≠ FIND-SET(v):
        A = A ∪ {(u, v)}
        UNION(u, v)
  return A
Shorters pats(s) Shortest path
vertice - all
in
Non-negative
cyrcles
best with:
Binary Heap
Dijkstra's algorithm function Dijkstra(Graph, source):
 
  create vertex set Q

  for each vertex v in Graph:             // Initialization
      dist[v] ← INFINITY                  // Unknown distance from source to v
      prev[v] ← UNDEFINED                 // Previous node in optimal path from source
      add v to Q                          // All nodes initially in Q (unvisited nodes)

  dist[source] ← 0                        // Distance from source to source
    
  while Q is not empty:
      u ← vertex in Q with min dist[u]    // Source node will be selected first
      remove u from Q
        
      for each neighbor v of u:           // where v is still in Q.
          alt ← dist[u] + length(u, v)
          if alt < dist[v]:               // A shorter path to v has been found
              dist[v] ← alt
              prev[v] ← u

      return dist[], prev[]
Shortest path
vertice - all
Bellman-Ford function BellmanFord(list vertices, list edges, vertex source)
   ::distance[],predecessor[]

   // This implementation takes in a graph, represented as
   // lists of vertices and edges, and fills two arrays
   // (distance and predecessor) with shortest-path
   // (less cost/distance/metric) information

   // Step 1: initialize graph
   for each vertex v in vertices:
       distance[v] := inf     // At the beginning , all vertices have a weight of infinity
       predecessor[v] := null // And a null predecessor
  
   distance[source] := 0      // Except for the Source, where the Weight is zero
  
   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // Step 3: check for negative-weight cycles
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "Graph contains a negative-weight cycle"
   return distance[], predecessor[]
Shortest path
all - all
Floyd–Warshall
(with path reconstruction)
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
let next be a |V| × |V| array of vertex indices initialized to null

procedure FloydWarshallWithPathReconstruction ()
   for each edge (u,v)
      dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
      next[u][v] ← v
   for k from 1 to |V| // standard Floyd-Warshall implementation
      for i from 1 to |V|
         for j from 1 to |V|
            if dist[i][k] + dist[k][j] < dist[i][j] then
               dist[i][j] ← dist[i][k] + dist[k][j]
               next[i][j] ← next[i][k]

procedure Path(u, v)
   if next[u][v] = null then
       return []
   path = [u]
   while u ≠ v
       u ← next[u][v]
       path.append(u)
   return path
Shortest path
all - all
Few Edges
Johnson's algorithm 1. First, a new node q is added to the graph, connected by zero-weight edges to each of the other nodes.
2. Second, the Bellman–Ford algorithm is used, starting from the new vertex q, to find for each vertex v the minimum weight h(v) of a path from q to v. If this step detects a negative cycle, the algorithm is terminated.
3. Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm: an edge from u to v, having length w(u,v), is given the new length w(u,v) + h(u) − h(v).
4. Finally, q is removed, and Dijkstra's algorithm is used to find the shortest paths from each node s to every other vertex in the reweighted graph.
Travelling salesman
problem
. Christofides
 algorithm
1. Create a minimum spanning tree T of G.

2. Let O be the set of vertices with odd degree in T. By the handshaking lemma, O has an even number of vertices.

3. Find a minimum-weight perfect matching M in the induced subgraph given by the vertices from O.
function PerfectMatching()
  Input: odds (list of odd vertices), G (adjacency list)
  while !odds.empty do
    v <-- odds.popFront()
    length <-- ∞
    for u ∈ odds do
      if weight(u,v) < length then
        length <-- weight(u,v)
        closest <-- u
      end if
    end for
    G.addEdge(closest,u)
    odds.remove(closest)
  end while
end function

4. Combine the edges of M and T to form a connected multigraph H in which each vertex has even degree.

5. Form an Eulerian circuit in H.
We find a euler circuit starting at any arbitrary node in our multigraph. If our node has neighbors, we push our node on a stack, choose a neighbor, remove the edge between them from the graph, and make that neighbor the current vertex. If our vertex has no neighbors left, we add it to our circuit and pop the top vertex from the stack to use as our current vertex. We continue tracing a tour in this manner until the stack is empty and the last vertex has no more neighbors left.

6. Make the circuit found in previous step into a Hamiltonian circuit by skipping repeated vertices (walking along the Euler tour, checking at every stop whether that node has already been visited. If it has, we skip that node and move on to the next one. Since our graph satisfies the triangle inequality, shortcutting vertices in this manner will not increase the length of our path).
Graph search . DFS
(using stack)
  procedure DFS(G,v):
      label v as discovered
      for all edges from v to w in G.adjacentEdges(v) do
          if vertex w is not labeled as discovered then
              recursively call DFS(G,w)
. BFS
(using queue)
Breadth-First-Search(Graph, root):
 
     for each node n in Graph:           
         n.distance = INFINITY       
         n.parent = NIL
 
     create empty queue Q     
 
     root.distance = 0
     Q.enqueue(root)                     
 
     while Q is not empty:       
    
         current = Q.dequeue()
    
         for each node n that is adjacent to current:
             if n.distance == INFINITY:
                 n.distance = current.distance + 1
                 n.parent = current
                 Q.enqueue(n)
. A*
(heuristic BFS)
function A*(start, goal)
    // The set of nodes already evaluated.
    closedSet := {}
    // The set of currently discovered nodes still to be evaluated.
    // Initially, only the start node is known.
    openSet := {start}
    // For each node, which node it can most efficient be reach from.
    // If a node can be reached from many nodes, cameFrom will eventually contain the
    // most efficient previous step.
    cameFrom := the empty map

    // For each node, the cost of getting from the start node to that node.
    gScore := map with default value of Infinity
    // The cost of going from start to start is zero.
    gScore[start] := 0
    // For each node, the total cost of getting from the start node to the goal
    // by passing by that node. That value is partly known, partly heuristic.
    fScore := map with default value of Infinity
    // For the first node, that value is completely heuristic.
    fScore[start] := heuristic_cost_estimate(start, goal)

    while openSet is not empty
        current := the node in openSet having the lowest fScore[] value
        if current = goal
            return reconstruct_path(cameFrom, goal)

        openSet.Remove(current)
        closedSet.Add(current)
        for each neighbor of current
            if neighbor in closedSet
                continue  // Ignore the neighbor which is already evaluated.
            // The distance from start to goal passing through current and the neighbor.
            tentative_gScore := gScore[current] + dist_between(current, neighbor)
            if neighbor not in openSet // Discover a new node
                openSet.Add(neighbor)
            else if tentative_gScore >= gScore[neighbor]
                continue  // This is not a better path.

            // This path is the best until now. Record it!
            cameFrom[neighbor] := current
            gScore[neighbor] := tentative_gScore
            fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)

    return failure

function reconstruct_path(cameFrom, current)
    total_path := [current]
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.append(current)
    return total_path
Strongly connected
components 
. Tarjan's algorithm  algorithm tarjan is
  input: graph G = (V, E)
  output: set of strongly connected components (sets of vertices)

  index := 0
  S := empty
  for each v in V do
    if (v.index is undefined) then
      strongconnect(v)
    end if
  end for

  function strongconnect(v)
    // Set the depth index for v to the smallest unused index
    v.index := index
    v.lowlink := index
    index := index + 1
    S.push(v)
    v.onStack := true

    // Consider successors of v
    for each (v, w) in E do
      if (w.index is undefined) then
        // Successor w has not yet been visited; recurse on it
        strongconnect(w)
        v.lowlink  := min(v.lowlink, w.lowlink)
      else if (w.onStack) then
        // Successor w is in stack S and hence in the current SCC
        v.lowlink  := min(v.lowlink, w.index)
      end if
    end for

    // If v is a root node, pop the stack and generate an SCC
    if (v.lowlink = v.index) then
      start a new strongly connected component
      repeat
        w := S.pop()
        w.onStack := false
        add w to current strongly connected component
      while (w != v)
      output the current strongly connected component
    end if
  end function
Sequence
algorithms
Sequence search . Binary search
algorithm
int binary_search(int A[], int key, int imin, int imax)
{
  // continue searching while [imin,imax] is not empty
  while (imin <= imax)
    {
      // calculate the midpoint for roughly equal partition
      int imid = midpoint(imin, imax);
      if (A[imid] == key)
        // key found at index imid
        return imid;
      // determine which subarray to search
      else if (A[imid] < key)
        // change min index to search upper subarray
        imin = imid + 1;
      else       
        // change max index to search lower subarray
        imax = imid - 1;
    }
  // key was not found
  return KEY_NOT_FOUND;
}
Sequence sorting . Quick Sort
(3 Way Partition)
# choose pivot
swap a[n,rand(1,n)]

# 3-way partition
i = 1, k = 1, p = n
while i < p,
  if a[i] < a[n], swap a[i++,k++]
  else if a[i] == a[n], swap a[i,--p]
  else i++
end
→ invariant: a[p..n] all equal
→ invariant: a[1..k-1] < a[p..n] < a[k..p-1]

# move pivots to center
m = min(p-k,n-p+1)
swap a[k..k+m-1,n-m+1..n]

# recursive sorts
sort a[1..k-1]
sort a[n-p+k+1,n]
. Radix Sort  bucket sort(L)
    {
    list Y[k+1]
    for (i = 0; i <= k; i++) Y[i] = empty
    while L nonempty
    {
        let X = first record in L
        move X to Y[key(X)]
    }
    for (i = 0; i <= k; i++)
    concatenate Y[i] onto end of L
    }
Best on
worst case scenario
Merge sort function merge_sort(list m)
    // Base case. A list of zero or one elements is sorted, by definition.
    if length of m < 2 then
        return m

    // Recursive case. First, divide the list into equal-sized sublists
    // consisting of the even and odd-indexed elements.
    var left := empty list
    var right := empty list
    for each x with index i in m do
        if i is odd then
            add x to left
        else
            add x to right

    // Recursively sort both sublists.
    left := merge_sort(left)
    right := merge_sort(right)

    // Then merge the now-sorted sublists.
    return merge(left, right)
(Subsequences)
Maximum sub-array
. Kadane's algorithm def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far
Longest common subsequence problem function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]
Longest increasing subsequence  P = array of length N
 M = array of length N + 1
 L = 0
 for i in range 0 to N-1:
   // Binary search for the largest positive j ≤ L ; such that X[M[j]] < X[i]
   lo = 1; hi = L
   while lo ≤ hi:
     mid = ceil((lo+hi)/2)
     if X[M[mid]] < X[i]:
       lo = mid+1
     else:
       hi = mid-1
   // After searching, lo is 1 greater than the length of the longest prefix of X[i]
   newL = lo
   // The predecessor of X[i] is the last index of the subsequence of length newL-1
   P[i] = M[newL-1]
   M[newL] = i
   if newL > L:
     // If we found a subsequence longer than any we've found yet, update L
     L = newL
 // Reconstruct the longest increasing subsequence
 S = array of length L
 k = M[L]
 for i in range L-1 to 0:
   S[i] = X[k]
   k = P[k]
 return S
Sequence
(string)
searching
. Knuth–Morris–Pratt
 Algorithm
algorithm kmp_search:
    input:
        an array of characters, S (the text to be searched)
        an array of characters, W (the word sought)
    output:
        an integer (the zero-based position in S at which W is found)

    define variables:
        an integer, m ← 0 (the beginning of the current match in S)
        an integer, i ← 0 (the position of the current character in W)
        an array of integers, T (the table, computed elsewhere - precompute)
       
    while m + i < length(S) do
        if W[i] = S[m + i] then
            if i = length(W) - 1 then
                return m
            let i ← i + 1
        else
            if T[i] > -1 then
                let m ← m + i - T[i], i ← T[i]
            else
                let i ← 0, m ← m + 1
           
    (if we reach here, we have searched all of S unsuccessfully)
    return the length of S
Optimization
algorithms
Gain - Cost
decision
(games)
. Minimax
Algorithm
 function minimax(node, depth, maximizingPlayer)
     if depth = 0 or node is a terminal node
         return the heuristic value of node

     if maximizingPlayer
         bestValue := −∞
         for each child of node
             v := minimax(child, depth − 1, FALSE)
             bestValue := max(bestValue, v)
         return bestValue

     else    (* minimizing player *)
         bestValue := +∞
         for each child of node
             v := minimax(child, depth − 1, TRUE)
             bestValue := min(bestValue, v)
         return bestValue
Minimax
 Algorithm
Optimization
. Alpha-beta pruning function alphabeta(node, depth, α, β, maximizingPlayer)
      if depth = 0 or node is a terminal node
          return the heuristic value of node
      if maximizingPlayer
          v := -∞
          for each child of node
              v := max(v, alphabeta(child, depth - 1, α, β, FALSE))
              α := max(α, v)
              if β ≤ α
                  break (* β cut-off *)
          return v
      else
          v := ∞
          for each child of node
              v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
              β := min(β, v)
              if β ≤ α
                  break (* α cut-off *)
          return v
Computer
 Graphics
Line clipping . Cohen-Sutherland
 Algorithm
procedure CohenSutherlandLineClipAndDraw(
       x0,y0,x1,y1,xmin,xmax,ymin,ymax : real ; value: integer);
{ Cohen-Sutherland clipping algorithm for line P0=(x1,y0) to P1=(x1,y1)
and clip rectangle with diagonal from (xmin,ymin) to (xmax,ymax).}
type
    edge = (LEFT,RIGHT,BOTTOM,TOP);
    outcode = set of edge;
var
    accept,done : boolean;
    outcode0,outcode1,outcodeOut : outcode;
    {Outcodes for P0,P1, and whichever point lies outside the clip rectangle}
    x,y : real;
    procedure CompOutCode(x,y: real; var code:outcode);
    {Compute outcode for the point (x,y) }
    begin
      code := [];
      if y > ymax then code := [TOP]
      else if y < ymin then code := [BOTTOM];
      if x > xmax then code := code +[RIGHT]
      else if x < xmin then code := code +[LEFT]
    end;

begin
    accept := false;  done := false;
    CompOutCode (x0,y0,outcode0); CompOutCode (x1,y1,outcode1);
    repeat
      if(outcode0=[]) and (outcode1=[]) then {Trivial accept and exit}
        begin accept := true; done:=true end
      else if (outcode0*outcode1) <> [] then
        done := true    {Logical intersection is true, so trivial reject and exit.}
      else
        {Failed both tests, so calculate the line segment to clip;
        from an outside point to an intersection with clip edge.}
        begin
          {At least one endpoint is outside the clip rectangle; pick it.}
          if outcode0 <> [] then
            outcodeOut := outcode0 else outcodeOut := outcode1;
          {Now find intersection point;
          use formulas y=y0+slope*(x-x0),x=x0+(1/slope)*(y-y0).}
          if TOP in outcodeOut then
            begin     {Divide line at top of clip rectangle}
              x := x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);
              y := ymax
            end
          if BOTTOM in outcodeOut then
            begin     {Divide line at bottom of clip rectangle}
              x := x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);
              y := ymax
            end
          else if RIGHT in outcodeOut then
            begin     {Divide line at right edge of clip rectangle}
              y := y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);
              x := xmax
            end
          else if LEFT in outcodeOut then
            begin     {Divide line at left edge of clip rectangle}
              y := y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);
              x := xmin
            end;
          {Now we move outside point to intersection point to clip,
          and get ready for next pass.}
          if (outcodeOut = outcode0) then
            begin
              x0 := x; y0 := y; CompOutCode(x0,y0,outcode0)
            end
          else
            begin
              x1 := x; y1 := y; CompOutCode(x1,y1,outcode1);
            end
        end   {subdivide}
    until done;
    if accept then MidpointLineReal(x0,y0,x1,y1,value) {Version for real coordin
ates}
end; {CohenSutherlandLineClipAndDraw}
Polygon
clipping
. Sutherland
Hodgman
Algorithm
 List outputList = subjectPolygon;
  for (Edge clipEdge in clipPolygon) do
     List inputList = outputList;
     outputList.clear();
     Point S = inputList.last;
     for (Point E in inputList) do
        if (E inside clipEdge) then
           if (S not inside clipEdge) then
              outputList.add(ComputeIntersection(S,E,clipEdge));
           end if
           outputList.add(E);
        else if (S inside clipEdge) then
           outputList.add(ComputeIntersection(S,E,clipEdge));
        end if
        S = E;
     done
  done
Determine
area connection
. Flood fill Flood-fill (node, target-color, replacement-color):
 1. If target-color is equal to replacement-color, return.
 2. If the color of node is not equal to target-color, return.
 3. Set the color of node to replacement-color.
 4. Perform Flood-fill (one step to the south of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
 5. Return.
Global illumination . Ray tracing for(each pixel (sample) on the viewing area)
{
   for(each primitive in the world model)
   {
      if(ray-pixel intersection)
      {
          select the frontmost intersection;
          recursively trace the relection and refraction rays;
          calculate color;
      }
   }
}
Determine
circle points
. Midpoint circle
Algorithm
void DrawCircle(int x0, int y0, int radius){
  int x = radius;
  int y = 0;
  int decisionOver2 = 1 - x;   // Decision criterion divided by 2 evaluated at x=r, y=0

  while( y <= x ){
    DrawPixel( x + x0,  y + y0); // Octant 1
    DrawPixel( y + x0,  x + y0); // Octant 2
    DrawPixel(-x + x0,  y + y0); // Octant 4
    DrawPixel(-y + x0,  x + y0); // Octant 3
    DrawPixel(-x + x0, -y + y0); // Octant 5
    DrawPixel(-y + x0, -x + y0); // Octant 6
    DrawPixel( x + x0, -y + y0); // Octant 7
    DrawPixel( y + x0, -x + y0); // Octant 8
    y++;
    if (decisionOver2<=0){
      decisionOver2 += 2 * y + 1;   // Change in decision criterion for y -> y+1
    }
    else{
      x--;
      decisionOver2 += 2 * (y - x) + 1;   // Change for y -> y+1, x -> x-1
    }
  }
}
Line pixel
aproximation
. Bresenham's
line algorithm
function line(x0, y0, x1, y1)
     real deltax := x1 - x0
     real deltay := y1 - y0
     real error := 0
     real deltaerr := abs(deltay / deltax)    // Assume deltax != 0 (line is not vertical),
           // note that this division needs to be done in a way that preserves the fractional part
     int y := y0
     for x from x0 to x1
         plot(x,y)
         error := error + deltaerr
         while error ≥ 0.5 then
             plot(x, y)
             y := y + sign(y1 - y0)
             error := error - 1.0