Thread by @Franc0Fernand0

Graph algorithms are used in many real-world scenarios.

Here are 5 standard graph algorithms and their significant use cases:

{1/11} ↓

1. Breadth-first search

It's a traversal algorithm implemented using a queue data structure.

It starts from a node and first explores all its adjacent nodes.

Then it explores all nodes two steps away from the starting one, and so on.

{2/11}

Applications of BFS are:

● build web pages indexes in web crawlers

● discove neighbour nodes in p2p networks

● find neighboring places in GPS navigation systems

{3/11}

2. Deepth First Search

It's a traversal algorithm implemented using a stack data structure.

It starts from a node and explores as far as possible along each path.

When no more nodes exist to explore in the current path, it retraces.

{4/11}

Applications of DFS are:

● find a path between 2 nodes

● detect cycles in a graph

● topological sorting

● solve maze or sudoku puzzles

{5/11}

3. Shortest path

It's a traversal algorithm that calculates the shortest path between two nodes.

The shortest path minimizes the sum of the weights on the traveled edges.

There are two main algorithms: Dijkstra and Bellman–Ford.

{6/11}

Applications of the Shortest path are:

● find travelling paths in navigation systems

● solve the min-delay path problem in networking

● finding the best route from one point to another in video games

{7/11}

4. Topological Sorting

It's a graph theory algorithm finding an order in which visiting the nodes.

It linearly orders the nodes of a directed graph so that for each edge x -> y, vertex x precedes y.

{8/11}

Applications of the Topological sorting are:

● scheduling interdependent job

● data serialisation and sentence ordering

● compilation tasks ordering and symbols dependencies resolution

{9/11}

5. Minimum spanning tree

It's a graph theory algorithm finding a subset of the edges connecting all the nodes.

Such edges have no cycles and minimum sum of weights.

Every connected and undirected graph has at least one spanning tree.

{10/11}

Applications of the Minimum spanning tree are:

● network design

● image registration and object tracking

● analysis of graph-based data clusters

{11/11}

Thanks for reading!

If you liked it, I'd be grateful if you'd:

• like or retweet the 1st tweet

• follow @Franc0Fernand0 for more similar content

• subscribe my newsletter polymathicengineer.com

Your support encourages me to keep writing!