Graph Data Structure & Algorithms
Go to ProblemsGraph Traversals ( DFS and BFS )
Now that we have looked at graph and some of its properties, we will try to explore how to traverse the graph and search for a particular node.
There are 2 popular approaches of doing graph traversals :
* Depth first search ( DFS )
* Breadth first search ( BFS )
We will take a look at them in this video :
Graph Data Structure & Algorithms Problems
Graph traversal
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Path in Directed Graph | 150 |
|
42:29 | |
| Water Flow | 200 |
|
75:01 | |
| Stepping Numbers | 300 |
|
61:17 | |
| Capture Regions on Board | 500 |
|
66:48 | |
| Word Search Board | 500 |
|
60:30 |
Depth first search
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Path with good nodes! | 150 |
|
62:35 | |
| Largest Distance between nodes of a Tree | 200 |
|
79:16 | |
| Good Graph | 200 |
|
61:43 | |
| Cycle in Directed Graph | 200 |
|
57:51 | |
| Delete Edge! | 200 |
|
70:50 | |
| Two teams? | 300 |
|
57:38 |
Bfs
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Valid Path | 200 |
|
85:28 | |
| Region in BinaryMatrix | 200 |
|
46:40 | |
| Path in Matrix | 200 |
|
35:46 | |
| Level Order | 300 |
|
29:55 | |
| Smallest Multiple With 0 and 1 | 300 |
|
77:21 | |
| Snake Ladder Problem! | 300 |
|
68:31 | |
| Min Cost Path | 300 |
|
72:17 | |
| Permutation Swaps! | 300 |
|
61:34 |
Graph connectivity
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Commutable Islands | 200 |
|
78:45 | |
| Possibility of finishing all courses given pre-requisites | 200 |
|
65:25 | |
| Cycle in Undirected Graph | 200 |
|
54:34 | |
| Mother Vertex | 200 |
|
49:34 | |
| File Search | 200 |
|
28:51 | |
| Black Shapes | 300 |
|
49:04 |
Graph adhoc
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Convert Sorted List to Binary Search Tree | 300 |
|
45:02 |
Shortest path
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Sum Of Fibonacci Numbers | 300 |
|
53:45 | |
| Knight On Chess Board | 300 |
|
68:21 | |
| Useful Extra Edges | 400 |
|
63:50 | |
| Word Ladder I | 600 |
|
70:18 | |
| Word Ladder II | 800 |
|
71:04 |
Graph hashing
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Clone Graph | 500 |
|
57:26 |
