Every graph algorithm starts with the same fundamental question: how do we visit every node? Answering that question efficiently is the job of the two core traversal algorithms — Breadth-First Search (BFS) and Depth-First Search (DFS). By the end of this post you’ll understand how both work, when to use each, and how DFS extends naturally into topological sort — one of the most useful tools in any developer’s toolkit. This is Part 2 of a 3-part series. Start with Part 1 if you haven’t yet. The Node Status Model Before writing any traversal code, it helps to think of READ MORE
Tag: topological sort
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