Graph algorithms are used in many real-world scenarios.
Here are 5 standard graph algorithms and their significant use cases:
{1/11} โ
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}
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}
โ 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}
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}
โ 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}
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}
โ 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}
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}
โ 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}
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}
โ 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!
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!
Loading suggestions...