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. Ifdirectedisfalse, every edge works in both directions.addEdge(u, v)adds an edge fromutov(and fromvtouwhen undirected). Vertices are integers and come into existence the first time they appear.bfs(start)returns the vertices reachable fromstartin breadth-first visiting order.dfs(start)returns the vertices reachable fromstartin 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
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 2 visible tests, Submit all 8. ⌘Enter runs, ⌘⇧Enter submits.