In Part 1 we covered what graphs are and how to represent them. In Part 2 we explored BFS and DFS — the two ways to traverse a graph. Now it’s time for the advanced algorithms that solve real engineering problems: finding the shortest weighted path, connecting a network at minimum cost, and efficiently grouping nodes. This is Part 3 of a 3-part series. Start from Part 1 if you’re new to graphs. Dijkstra’s Algorithm — Shortest Path in a Weighted Graph The Problem BFS finds the shortest path in an unweighted graph (fewest edges). But what if edges have READ MORE
Tag: minimum spanning tree
Minimum Spanning Tree – Kruskal’s Algorithm
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