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: graph traversal
Intro to Depth First Search (DFS)
Depth first search is one of the popular graph traversal algorithms that work well for certain purposes.As you can infer from the name DFS is quite different from BFS – breadth first search.Therefore the applications of DFS are different from BFS.In this post, I am going to discuss how DFS works with examples.Please refer to my other post of BFS if you are interested in. How does DFS work? I am going to start by explaining DFS by comparing it with BFS.Please note that BFS searches all the neighbors at the same level or degree before you move to the READ MORE
Intro to Breadth First Search (BFS)
When dealing with a graph it might be necessary to traverse the graph.Graph traversal is a systemic method to traverse the graph.Breadth first search is one of the most popular graph traversal algorithms that work very well for certain purposes.Today, I am going to introduce breadth first search in this post. How does breadth first search traverse? BFS is a graph traversal algorithm to visit vertices from one starting point in a certain way.How does it visit other nodes? It first visits its nearest neighbors and processes them before reaching any further nodes.And it marks nodes as it visits so READ MORE