Skip to content

Latest commit

 

History

History
221 lines (151 loc) · 6.56 KB

graph-search.asc

File metadata and controls

221 lines (151 loc) · 6.56 KB
Raw

Graph Search

Graph search allows you to visit search elements.

Warning
 Graph search is very similar to [Tree Search & Traversal]. So, if you read that section, some of the concepts here will be familiar to you.

There are two ways to navigate the graph, one is using Depth-First Search (DFS), and the other one is Breadth-First Search (BFS). Let’s see the difference using the following graph.

directed graph

Depth-First Search for Graphs

With Depth-First Search (DFS), we go deep before going wide.

We use DFS on the graph shown above, starting with node 0. A DFS will probably visit 5, then visit 1 and continue going down 3 and 2. As you can see, we need to keep track of visited nodes, since, in graphs, we can have cycles like 1-3-2. Finally, we back up to the remaining node 0 children: node 4.

So, DFS would visit the graph: [0, 5, 1, 3, 2, 4].

Breadth-First Search for Graphs

With Breadth-First Search (BFS), we go wide before going deep.

We use BFS on the graph shown above, starting with the same node 0. A BFS will visit 5 as well, then visit 1 and not go down to its children. It will first finish all the children of node 0, so it will visit node 4. After all the children of node 0 are visited, it will continue with all the children of node 5, 1, and 4.

In summary, BFS would visit the graph: [0, 5, 1, 4, 3, 2]

Depth-First Search vs. Breadth-First Search in a Graph

DFS and BFS can implementation can be almost identical; the difference is the underlying data structured. In our implementation, we have a generic graphSearch where we pass the first element to start the search the data structure that we can to use:

DFS and BFS implementation
link:../../../src/data-structures/graphs/graph.js[role=include]

Using an part02-linear-data-structures.asc (LIFO) for DFS will make use keep visiting the last node children while having a part02-linear-data-structures.asc (FIFO) will allow to visit adjacent nodes first and "queue" their children for later visiting.

Tip
 you can also implement the DFS as a recursive function, similar to what we did in the DFS for trees.

You might wonder what the difference between search algorithms in a tree and a graph is? Check out the next section.

DFS/BFS on Tree vs Graph

The difference between searching a tree and a graph is that the tree always has a starting point (root node). However, in a graph, you can start searching anywhere. There’s no root.

Note
 Every tree is a graph, but not every graph is a tree. Only acyclic directed graphs (DAG) are trees.

Practice Questions

Course Schedule

gr-1) Check if it’s possible to take all courses while satisfying their prerequisites.

Common in interviews at: Amazon, Facebook, Bytedance (TikTok).

Starter code:

link:../../interview-questions/course-schedule.js[role=include]

Examples:

canFinish(2, [[1, 0]]); // true
// 2 courses: 0 and 1. One prerequisite: 0 -> 1
// To take course 1 you need to take course 0.
// Course 0 has no prerequisite, so you can take 0 and then 1.

canFinish(2, [[1, 0], [0, 1]]); // false
// 2 courses: 0 and 1. Two prerequisites: 0 -> 1 and 1 -> 0.
// To take course 1, you need to take course 0.
// To Course 0, you need course 1, so you can't any take them!

canFinish(3, [[2, 0], [1, 0], [2, 1]]); // true
// 3 courses: 0, 1, 2. Three prerequisites: 0 -> 2 and 0 -> 1 -> 2
// To take course 2 you need course 0, course 0 has no prerequisite.
// So you can take course 0 first, then course 1, and finally course 2.

canFinish(4, [[1, 0], [2, 1], [3, 2], [1, 3]]); // false
// 4 courses: 0, 1, 2, 3. Prerequisites: 0 -> 1 -> 2 -> 3 and 3 -> 1.
// You can take course 0 first since it has no prerequisite.
// For taking course 1, you need course 3. However, for taking course 3
// you need 2 and 1. You can't finish then!
Critical Network Paths

gr-2) Given n servers and the connections between them, return the critical paths.

Common in interviews at: FAANG.

Examples:

graph G {
  subgraph cluster_1 {
    a0 -- a1 -- a2 [color=firebrick1]
    label = "Example A";
  }

  subgraph cluster_0 {
    b0 -- b1 [color=blue]
    b1 -- b2 [color=blue]
    b2 -- b0 [color=blue]
    b1 -- b3 [color=blue]
    b3 -- b2 [color=blue]
    label = "Example B";
    b0, b1, b2, b3 [color=midnightblue]
  }

  subgraph cluster_3 {
    c0 -- c1 [color=blue]
    c1 -- c2 [color=blue]
    c2 -- c0 [color=blue]
    c1 -- c3 [color=firebrick1]
    c3 -- c2 [color=transparent] // removed
    label = "Example C";
    c0, c1, c2 [color=midnightblue]
    // c3 [color=red]
  }

  a0, b0, c0 [label = 0]
  a1, b1, c1 [label = 1]
  a2, b2, c2 [label = 2]
  b3, c3 [label = 3]
}
// Example A
criticalConnections(3, [[0, 1], [1, 2]]);// [[0, 1], [1, 2]]
// if you remove any link, there will be stranded servers.

// Example B
criticalConnections(4, [[0, 1], [1, 2], [2, 0], [1, 3], [3, 2]]);// []
// you can remove any connection and all servers will be reachable.

// Example C
criticalConnections(4, [[0, 1], [1, 2], [2, 0], [1, 3]]); // [[1, 3]]
// if you remove [1, 3], then server 3 won't be reachable.
// If you remove any other link. It will be fine.

Starter code:

link:../../interview-questions/critical-connections-in-a-network.js[role=include]