This post explains what minimum spnning tree is and how to construct minimum spanning tree using Kruskal’s algorithm What is minimum spanning tree Given you have a list of nodes in a graph and weighted edges connecting the nodes. What is the minimum cost to connect the nodes that all the nodes are connected? For example, looking at the graph below, all the nodes are connected. However, some edges can be removed so that total weight of the graph can be minimized and still connecting all the nodes. Minimum spanning tree is a graph that all the nodes are connected READ MORE
Tag: graph
Union Find
There are two methods in order to traverse a graph – BFS, DFS. Let’s say there is a graph problem to count the number of connected components. Here are the steps you can take.1. Build the graph2. Perform BFS or DFS3. Outer loop to check each unvisited node4. Number of calls to BFS or DFS is equivalent to the number of connected components because BFS or DFS will mark the connected component as visited Time complexity would be O(V+E) where V is the node and E is the edge. It is linear complexity. This is a simple problem with a READ MORE
Dijkstra’s Algorithm Shortest Path
Dijkstra’s algorithm is the most popular algorithm to find the shortest paths from a certain vertex in a weighted graph.In fact, the algorithm will find the shortest paths to every vertex from the start vertex.The algorithm takes both greedy and dynamic programming approach that it will try to find local optimum paths first and use them to find the shortest paths.Let’s take a look at how it works! How does Dijkstra’s algorithm work? Let’s say we need to find the shortest path from node A to node E. There are five nodes and each edge is weighted with the cost READ MORE
Intro to Topological Sort
Topological sort is an important algorithm in DAG – directed acyclic graphs. It orders each vertex in line from left to right such that left most vertex could be considered as the highest level or root or entrance of the graph and rightmost as the lowest of the graph. In the end, topological sort tells you the order of vertices you need to go through from one node to the other without missing any middle vertices. There could be multiple topological sorts in the same graph. Let’s take a look at an example for a better understanding Course Prerequisite Example READ MORE
Intro to Graphs
A graph is an abstract representation of a complex system such as networks, human relationships, and any organization.A graph is very important because it can represent and simplify any complex relationships in a visual format.It is pretty amazing that messy applied problems often could be described with simple and classical graph properties. In this post, I am going to discuss some popular graphs and brief examples. Graph Examples A graph G can be represented as a set of vertices and edges which can be said as G = (V, E)Now, let’s take a look at various graphs and their properties. READ MORE