Graph Traversals - Breadth First and Depth First
Why Stack Overflow recommends it
Stack Overflow users link it as a short, clear visual demonstration of BFS and DFS when answering graph traversal and data structure questions.
Recommended by 2 people across 2 different months, 2015 to 2019.
What it is
A roughly ten-minute walkthrough of breadth-first and depth-first graph traversal, using a worked example to show the order in which nodes are visited. It is a modified re-upload of an earlier video and is presented by the channel owner, abhinav tripathi.
What people said
Recommends Turk · 2016-02 · Stack Overflow · on “Why does using a queue data structure in implementing Depth First Search makes it a Breadth First Search?”
I would suggest you first understand what a stack (FIFO) and queue (LIFO) data structure is. I'm sure you'll be able to reason the rest from there. [this video] A short video to get you started.
Recommends Patrick · 2019-07 · Stack Overflow · on “Iterative create graph with no cycles from another graph by removing edges”
Short answer Indeed, testing if a cycle is created each time you add a vertex to the G2 graph is costly. A more efficient method could consist in using a Breadth-First Search (BFS) on your graph G1 and to report the edges you use to travel from a node to another when you travel G1 in your G2 as you go along . I recommend the second part of this video [this video] for a demonstration of BFS. Regular BFS traversal of G1 to build G2 I will first describe how a standard BFS traversal can help you to eliminate loops in your original graph. For your preference in removing some type of edges over others, see below. I am going to assume that every vertex knows what its neighbors are (i.e. every vertex ha
Recommends Patrick · 2019-07 · Stack Overflow · on “graph data structure in node js”
As for the BFS algorithm, I think you may be confused because you got an example with a binary tree. I suggest you take a look at this short video [this video] . It corresponds very well to your situation with a graph of cities and roads. It explains both DFS and BFS but make sure to watch both algorithms, you will get more insight into which does what.
Cites w.brian · 2015-03 · Stack Overflow · on “Understanding ordering within a graph when doing traversals”
Thanks for your answer. I was watching this video [this video] wherein the author chooses which adjacent node to visit next based on the label of the node, which is what led to my confusion.