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

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

## 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.

## 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)

## 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).

## 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.

## 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.

## 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.

## 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.

## 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.

## 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.

## 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. 😇