Graph Algorithms
Today, we will talk about algorithms in graphs. There are various problems that can be solved by using a Graph search.
- Initially, we have to know about Graph
- Graph traversal — look through the nodes in the Graph
- In the first word, we will talk about MST (Minimum Spanning Tree)
- The next algorithm will be the shortest path algorithms.
Graph Knowledges
As we know in our secondary schools, we all have learnt about graphs. There are many types of graph, but today we will talk about path. The famous problems about Königsberg brides, with 7 paths. Such as the Euler rule of the Königsberg bride. Have you remembered?
How could you travel to these islands without crossing the same bride twice?
When will look at graph types :
There are Nodes and Edges,
- Nodes (vertices in the graph)
- Edges
There are several ways in representing data in graph
- Matrix Representation
2. Adjacency list
Furthermore, there are various types of the graph such as the weighted and unweighted graph. Imagine about travelling between two towns, in each road there must be the different distance. Therefore, it shown that every route is not the same (have different weight) and we should “considered” when choosing the path.
Directed and undirected graph
When we are travelling, there might be some more factors, not every road is expressway. The expressway are called the undirected graph, which means that we could travel back and front in that path. On the contraty,
Graph Traversal
Let’s Traverse in the Graph!
Depth First Search
We will traverse in the graph, by going in depth first. Therefore, this types of traverse is Depth First Search or DFS. There are 2 ways to code the Depth First Search; by using stack and recursive function.
DFS Implementation using recursive function (code in c++) :
DFS Implementation using stack (code in c++) :
Breadth First Search
We will search the graph by the Breadth, this will traverse through the nearer nodes first.
BFS Implementation using queue (code in c++) :
Mahattan Distance
Minimum Spanning Tree
Minimum Spanning Tree’s aim is to :
connect all the nodes in the graph with the shortest distance.
In the minimum spanning tree, there must be only n-1 edges when there is only n nodes.
The Prim algorithm
- 2 subsets ( in MST or not)
- find the least weight to join the MST
- Find the starting node
- look through all the edges that connected to the nodes in MST
- Select the least weight in all the edges.
- Join the node in MST
- Loop to all nodes until every nodes are in the MST
These are the vectors that we have to create :
1. Parent [NULL]
2. Visited [false]
3. Key [infinity] (Distance from the first nodes)
We will updates new weight (key) when it’s less than the previous key’s value.
Prim MST Implementation using priority queue (code in c++) :
The Kruskal Algorithm
- sort all the paths
- select the least weight
- join the graph if the nodes aren’t in the same subset
UNION and FIND methods :
Boruvka’s algorithm
1) Input is a connected, weighted and un-directed graph.
2) Initialize all vertices as individual components (or sets).
3) Initialize MST as empty.
4) While there are more than one components, do following
for each component.
a) Find the closest weight edge that connects this
component to any other component.
b) Add this closest edge to MST if not already added.
5) Return MST.
Shortest Path
Finding the shortest path between two distances.
Dijkstra Algorithm
Like Prim algorithm, will the note of keeping in mind the distance that have traverse through the whole graph.
Bellman Ford Algorithm
Using Dynamic Programming Approach
Graph Neural Network
“In this tutorial, we will discuss the application of neural networks on graphs. Graph Neural Networks (GNNs) have recently gained increasing popularity in both applications and research, including domains such as social networks, knowledge graphs, recommender systems, and bioinformatics.
While the theory and math behind GNNs might first seem complicated, the implementation of those models is quite simple and helps in understanding the methodology. Therefore, we will discuss the implementation of basic network layers of a GNN, namely graph convolutions, and attention layers. Finally, we will apply a GNN on a node-level, edge-level, and graph-level tasks.”
Couclusion and use cases
Graph can be extremely useful in many real-world problems, of minimizing loss in every paths, that we have walk or even a journey or route that is planned for your trip. Gets everyday easier, more convinient with graph traversal in your trip to get a happier trip.
The algorithm are as follows:
Prim Algorithm
Kruskal Algorithm
Dijkstra Algorithm
Have fun exploring Graph! See you!
Book suggestion
Competitive Programmer’s Handbook
