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:40 | |
| Water Flow | 200 |
|
75:57 | |
| Stepping Numbers | 300 |
|
61:32 | |
| Capture Regions on Board | 500 |
|
66:55 | |
| Word Search Board | 500 |
|
60:50 |
Depth first search
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Path with good nodes! | 150 |
|
63:12 | |
| Largest Distance between nodes of a Tree | 200 |
|
79:28 | |
| Good Graph | 200 |
|
62:19 | |
| Cycle in Directed Graph | 200 |
|
58:04 | |
| Delete Edge! | 200 |
|
71:51 | |
| Two teams? | 300 |
|
58:34 |
Bfs
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Valid Path | 200 |
|
85:44 | |
| Region in BinaryMatrix | 200 |
|
47:02 | |
| Path in Matrix | 200 |
|
36:51 | |
| Level Order | 300 |
|
29:55 | |
| Smallest Multiple With 0 and 1 | 300 |
|
78:16 | |
| Snake Ladder Problem! | 300 |
|
69:07 | |
| Min Cost Path | 300 |
|
73:10 | |
| Permutation Swaps! | 300 |
|
63:03 |
Graph connectivity
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Commutable Islands | 200 |
|
79:03 | |
| Possibility of finishing all courses given pre-requisites | 200 |
|
65:35 | |
| Cycle in Undirected Graph | 200 |
|
54:48 | |
| Mother Vertex | 200 |
|
51:19 | |
| File Search | 200 |
|
30:03 | |
| Black Shapes | 300 |
|
49:07 |
Graph adhoc
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Convert Sorted List to Binary Search Tree | 300 |
|
45:05 |
Shortest path
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Sum Of Fibonacci Numbers | 300 |
|
53:53 | |
| Knight On Chess Board | 300 |
|
68:26 | |
| Useful Extra Edges | 400 |
|
65:47 | |
| Word Ladder I | 600 |
|
70:34 | |
| Word Ladder II | 800 |
|
71:39 |
Graph hashing
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Clone Graph | 500 |
|
57:29 |
