Skip to content
Onsite

Implement Graph with BFS and DFS

MediumP1Coding

Implement a graph stored as an adjacency list, with breadth-first and depth-first search.

Implement the Graph class:

  • Graph(directed) creates an empty graph. If directed is false, every edge works in both directions.
  • addEdge(u, v) adds an edge from u to v (and from v to u when undirected). Vertices are integers and come into existence the first time they appear.
  • bfs(start) returns the vertices reachable from start in breadth-first visiting order.
  • dfs(start) returns the vertices reachable from start in depth-first preorder.

To make the order unique, always visit a vertex's neighbours in the order its edges were added. start is always included, even when it has no edges or has never appeared in an edge. Each vertex appears at most once.

Example 1

Input
["Graph","addEdge","addEdge","addEdge","addEdge","bfs","dfs"] [[false],[0,1],[0,2],[1,3],[2,3],[0],[0]]
Output
[null,null,null,null,null,[0,1,2,3],[0,1,3,2]]
Why
From 0, BFS visits 1 and 2 before 3. DFS goes 0, 1, 3, then reaches 2 as a neighbour of 3.

Constraints

  • 0 <= u, v <= 1000
  • At most 2000 calls in total.
  • Self-loops and repeated edges may appear.

Hints

Run checks the 2 visible tests, Submit all 8.