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