Algorithms

Graph algorithms

Trees are a restricted form of a graph, so some graph algorithms can be applied to trees. Moreover, the algorithms can be changed for optimization. For example, in BFS/DFS algorithmes a start node will be a root node. Trees don't have cycles, so you don't need to check if a node is visited.

depth-first search

Depth-first search (DFS) is an algorithm for traversing or searching graph data structures. The algorithm starts from some arbitrary node and explores as far as possible along each branch before backtracking.

Main ideas are:

  1. mark all nodes as not visited to avoid cycles
  2. put a start node to the stack
  3. while stack is not empty:
    • pop current node from the stack
    • check if it is not visited
      • mark as visited
      • add all unvisited neighbors to the stack

You can replace the stack with a call stack i.e. recursion:

  1. mark input node as visited
  2. for all neighbors:
      if(neighbor is not visited) recursively call with neighbor node

Optionally, when you mark a node as visited, you can add additional code to solve your problem. For example, update node data, check node for search criteria, etc.

Some use cases for the algorithm:

  • finding connected components
  • finding biconnectivity in graphs
  • finding strongly connected components
  • finding the bridges of a graph
  • topological sorting
  • solving puzzles with only one solution, such as mazes
  • maze generation

breadth-first search

Breadth-first search (BFS) is an algorithm for traversing or searching graph data structures. The algorithm starts from some arbitrary node and explores all nodes at the present depth prior to moving on to the nodes at the next depth level.

This is similar to the DFS, but a queue is used instead a stack.

Main ideas are:

  1. mark all nodes as not visited to avoid cycles
  2. put a start node to the queue
  3. mark a start node as visited
  4. while queue is not empty:
    • take current node from queue
    • for all neighbours
      • check if it is not visited
        • mark as visited
        • add neighbor to the queue

Some use cases for the algorithm:

  • copying garbage collection, Cheney's algorithm
  • finding the shortest path between two nodes u and v, with path length measured by number of edges
  • Ford–Fulkerson method for computing the maximum flow in a flow network
  • serialization/deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner
  • implementing parallel algorithms for computing a graph's transitive closure

Dijkstra's algorithm

Dijkstra's algorithm allows you to find the shortest paths between nodes in a graph.

Original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a tree.

Dijkstra's algorithm only works with the graph that possesses positive weights.

There are several ways from S to C, for example:

  • S-A-C, total distance 25
  • S-B-C, total distance 15
  • S-B-D-C, total distance 14. This is minimum distance that we save in result.

The distance from the source to itself is always 0.