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: union find
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