Skip to content
Search
Generic filters
Exact matches only

10 Graph Algorithms Visually Explained | by Vijini Mallawaarachchi | Aug, 2020

A quick introduction to 10 basic graph algorithms with examples and visualisations

Vijini Mallawaarachchi
Image by Author

A graph consists of a finite set of vertices or nodes and a set of edges connecting these vertices. Two vertices are said to be adjacent if they are connected to each other by the same edge.

  • Size: The number of edges in the graph
  • Vertex degree: The number of edges that are incident to a vertex
  • Isolated vertex: A vertex that is not connected to any other vertices in the graph
  • Self-loop: An edge from a vertex to itself
  • Directed graph: A graph where all the edges have a direction indicating what is the start vertex and what is the end vertex
  • Undirected graph: A graph with edges that have no direction
  • Weighted graph: Edges of the graph has weights
  • Unweighted graph: Edges of the graph has no weights
Fig 1. Visualization of Terminology of Graphs (Image by Author)
Fig 2. Animation of BFS traversal of a graph (Image by Author)

Applications

  • Used to determine the shortest paths and minimum spanning trees.
  • Used by search engine crawlers to build indexes of web pages.
  • Used to search on social networks.
  • Used to find available neighbour nodes in peer-to-peer networks such as BitTorrent.
Fig 3. Animation of DFS traversal of a graph (Image by Author)

Applications

  • Used to find a path between two vertices.
  • Used to detect cycles in a graph.
  • Used in topological sorting.
  • Used to solve puzzles having only one solution (e.g., mazes)
Fig 4. Animation showing the shortest path from vertex 1 to vertex 6 (Image by Author)

Algorithms

  1. Dijkstra’s shortest path algorithm
  2. Bellman–Ford algorithm

Applications

  • Used to find directions to travel from one location to another in mapping software like Google maps or Apple maps.
  • Used in networking to solve the min-delay path problem.
  • Used in abstract machines to determine the choices to reach a certain goal state via transitioning among different states (e.g., can be used to determine the minimum possible number of moves to win a game).
Fig 5. A cycle (Image by Author)

Algorithms

  1. Floyd cycle detection algorithm
  2. Brent’s algorithm

Applications

  • Used in distributed message-based algorithms.
  • Used to process large-scale graphs using a distributed processing system on a cluster.
  • Used to detect deadlocks in concurrent systems.
  • Used in cryptographic applications to determine keys of a message that can map that message to the same encrypted value.
Fig 6. Animation showing a minimum spanning tree (Image by Author)

Algorithms

  1. Prim’s algorithm
  2. Kruskal’s algorithm

Applications

  • Used to construct trees for broadcasting in computer networks.
  • Used in graph-based cluster analysis.
  • Used in image segmentation.
  • Used in regionalisation of socio-geographic areas, where regions are grouped into contiguous regions.
Fig 7. Strongly connected components (Image by Author)

Algorithms

  1. Kosaraju’s algorithm
  2. Tarjan’s strongly connected components algorithm

Applications

  • Used to compute the Dulmage–Mendelsohn decomposition, which is a classification of the edges of a bipartite graph.
  • Used in social networks to find a group of people who are strongly connected and make recommendations based on common interests.
Fig 8. A topological ordering of vertices in a graph (Image by Author)

Algorithms

  1. Kahn’s algorithm
  2. The algorithm based on depth-first search

Applications

  • Used in instruction scheduling.
  • Used in data serialisation.
  • Used to determine the order of compilation tasks to perform in makefiles.
  • Used to resolve symbol dependencies in linkers.
Fig 9. Vertex colouring (Image by Author)

Algorithms

  1. Algorithms using breadth-first search or depth-first search
  2. Greedy colouring

Applications

  • Used to schedule timetable.
  • Used to assign mobile radio frequencies.
  • Used to model and solve games such as Sudoku.
  • Used to colour geographical maps of countries or states where adjacent countries or states have different colours.
  • Used to check if a graph is bipartite.
Fig 10. Determining the maximum flow (Image by Author)

Algorithms

  1. Ford-Fulkerson algorithm
  2. Edmonds–Karp algorithm
  3. Dinic’s algorithm

Applications

  • Used in airline scheduling to schedule flight crews.
  • Used in image segmentation to find the background and the foreground in an image.
  • Used to eliminate baseball teams that cannot win enough games to catch up to the current leader in their division.
Fig 11. Matching of a bipartite graph (Image by Author)

Algorithms

  1. Hopcroft-Karp algorithm
  2. Hungarian algorithm
  3. Blossom algorithm

Applications

  • Used in matchmaking to match brides and grooms (the stable marriage problem).
  • Used to determine the vertex cover.
  • Used in transportation theory to solve problems in resource allocation and optimization in travel.

I hope you found this article useful as a simple and summarised introduction to graph algorithms. I would love to hear your thoughts. 😇