Is there a route between these two nodes in this directed graph?

Question 4.2 of Cracking the Coding Interview:

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

Given any node in the graph, we can generate a full list of nodes reachable from that node, by exploring the graph from that node outwards. We can then determine whether a route exists from node n1 to node n2 by generating the full list of nodes reachable from n1, and asking whether n2 is in that list.

To generate the “reachable set” from a node, we partition the graph into three sets: explored nodes, boundary nodes, and the rest. We repeatedly look for new nodes by looking at outgoing edges from nodes in the boundary set. When we’ve looked at all the outgoing edges of a node, we move that node to explored so we don’t look at its edges again. Eventually, our boundary set becomes empty, there are no new nodes to explore, and the explored set is all the reachable nodes.

Here’s an implementation in Haskell:

module DirectedGraphRoute where

import qualified Data.Set as Set
import Data.Set (Set)

type Node = Int
type Edge = (Node,Node)
type Graph = Set Edge

isRoute :: Graph -> Node -> Node -> Bool
isRoute g n1 n2 = Set.member n2 $ reachableSet g n1

reachableSet :: Graph -> Node -> Set Node
reachableSet g n = go Set.empty (Set.singleton n) where
  go explored boundary
    | Set.null boundary = explored
    | otherwise = go newExplored $ Set.fromList [ t | 
                    (f,t) <- Set.toList g, 
                    Set.member f boundary, 
                    not (Set.member t newExplored)
                  ]
                  where newExplored = Set.union explored boundary

One optimization could be to stop as soon as we find n2 while exploring. Another optimization could be to expand from n1 and n2 concurrently (exploring edges in the reverse direction from n2), and stopping as soon as the explored sets overlap.

I just released Vidrio, a free app for macOS and Windows to make your screen-sharing awesomely holographic. Vidrio shows your webcam video on your screen, just like a mirror. Then you just share or record your screen with Zoom, QuickTime, or any other app. Vidrio makes your presentations effortlessly engaging, showing your gestures, gazes, and expressions. #1 on Product Hunt. Available for macOS and Windows.

With Vidrio

With generic competitor

More by Jim

Tagged #ctci, #programming, #haskell. All content copyright James Fisher 2020. This post is not associated with my employer. Found an error? Edit this page.