Path between Nodes
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.
2018-07-09 The Book of Problems currently supports Ruby, Python, Elixir, Java, C, OCaml, and now C++!
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 love to explain and answer questions on programming problems. I publish a new programming problem and its solution every month. Did I mention that I love to 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.