Data structures and algorithms · Lesson 22 of 60 · Code lesson, JavaScript or Python · Optional
Graphs
A graph is a set of nodes joined by edges, such as people and friendships or cities and roads.
Traversal means visiting every node you can reach, and breadth-first search visits the nearest nodes first.
A visited set stops you from going round in circles.
Worked example
In JavaScript, a Set remembers visited nodes, and an array used as a queue gives the order with push and shift.
const graph = { A: ["B", "C"], B: ["D"], C: ["D"], D: [] };
console.log(graph["A"].join(" "));Output: B C
In Python, a set remembers visited nodes, and a list used as a queue gives the order with append and pop(0).
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(" ".join(graph["A"]))Output: B C
Your turn
The program starts a breadth-first walk from the node it reads, but never adds any neighbours to the queue. Add each neighbour that has not been visited yet, so every reachable node is printed.
Your program is checked with these 3 inputs:
Input:
A
Expected output:
A B C D
Input:
B
Expected output:
B D
Input:
D
Expected output:
D
Loading your practice…
Preparing your workspace…