Adjacency lists

Each vertex stores the vertices one edge away. One pass over the edge list builds it, and a search asks it for neighbours.

An adjacency list stores, for each vertex, the vertices you can reach in one step. An object whose keys are vertex ids and whose values are the neighbouring ids is enough. Building it is one pass over the edges. For an undirected edge, add each end to the other's list, or you will only be able to walk one direction.

The list answers "who are my neighbours?" in time proportional to how many there are, which is what a search actually asks on each pop. A matrix of every pair would answer "is this one edge present?" in constant time, and it would spend space on every possible edge, including the ones that do not exist. For the sparse graphs in these exercises, the list is the honest layout.

Once the list exists, breadth-first and depth-first search do not care how you built it. They only need, given a vertex, the neighbours to consider next.