Given an undirected graph, determine if there is a path from one node to another.

Input. The input consists of one or more graph specifications. Each specification consists of three parts. The first part is a line with the source and target nodes, separated by one space. The second part is a line consisting of integer n, the number of edges in the graph. The third part consists of n edges. Each edge is given on a line and consists of a pair of nodes separated by spaces. All nodes are integers.

1
0 4
4
0 1
0 2
1 3
3 4
0 9

Output. For each graph, output true when there is a path between the source and target nodes, output false otherwise.

true

Check your solution online

Before you read our solution, try to solve the problem on your own. Remember that practice makes perfect.

Click here to check your solution online at The Book of Problems.

2017-10-08 The Book of Problems currently supports Ruby, Python and now Elixir. More languages will come soon. If there is a language you’d like to use, drop me a line in the comments section.

O.K. solution

Apply Breadth-first Search.

Implementation of O.K. solution

Here is a Ruby implementation.

#!/usr/bin/env ruby

def bfs s, t, g
  return true if s == t
  v = {s => true}
  frontier_queue = [s]
  while not frontier_queue.empty?
    p = frontier_queue.delete_at 0
    g[p].each do |child|
      next if v[child]
      return true if child == t
      v[child] = true
      frontier_queue << child
    end
  end
  return false
end

def read_graph
  n = readline.to_i
  g = {}
  while (n -= 1) >= 0
    a, b = readline.strip.split(' ').map(&:to_i)
    g[a] ||= []
    g[a] << b
    g[b] ||= []
    g[b] << a
  end
  return g
end

n = readline.to_i

while (n -= 1) >= 0
  s, t = readline.strip.split(' ').map(&:to_i)
  g = read_graph
  puts bfs s, t, g
end

Solution

Apply Bidirectional Search.

Implementation of solution

Here is a Ruby implementation.

#!/usr/bin/env ruby

def bfs_step fq, vs, vt, g
  p = fq.delete_at 0
  g[p].each do |child|
    next if vs[child]
    return true if vt[child]
    vs[child] = true
    fq << child
  end
  return false
end

def bidirectional_search s, t, g
  return true if s == t
  vs = {s => true}
  vt = {t => true}
  fs = [s]
  ft = [t]
  while !(fs.empty? || ft.empty?)
    return true if bfs_step fs, vs, vt, g
    return true if bfs_step ft, vt, vs, g
  end
  return false
end

def read_graph
  n = readline.to_i
  g = {}
  while (n -= 1) >= 0
    a, b = readline.strip.split(' ').map(&:to_i)
    g[a] ||= []
    g[a] << b
    g[b] ||= []
    g[b] << a
  end
  return g
end

n = readline.to_i

while (n -= 1) >= 0
  s, t = readline.strip.split(' ').map(&:to_i)
  g = read_graph
  puts bidirectional_search s, t, g
end

Want to read more?

I regularly write solutions to programming problems that you may or may not find in technical job interviews. I also love to explain those solutions and answer questions. If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.

Comments