Skip to content

Instantly share code, notes, and snippets.

@yefim
Created February 27, 2013 05:57
Show Gist options
  • Save yefim/5045547 to your computer and use it in GitHub Desktop.
Save yefim/5045547 to your computer and use it in GitHub Desktop.
BFS implemented in CoffeeScript
# G = [vertices]
# vertex = {
# adjacency_list: [vertex_ids]
# color: one of ["WHITE", "GRAY", "BLACK"]
# parent: vertex
# d: depth
# }
module.exports =
test: ->
u0 = {adjacency_list: [1,2]}
u1 = {adjacency_list: [0]}
u2 = {adjacency_list: [0,3,4]}
u3 = {adjacency_list: [2]}
u4 = {adjacency_list: [2]}
g = [u0, u1, u2, u3, u4]
return module.exports.BFS g, u0
###
u0
/ \
u1 u2
/ \
u3 u4
###
BFS: (G, s) ->
for u in G
u.color = "WHITE"
u.d = Infinity
u.parent = undefined
s.color = "GRAY"
s.d = 0
q = []
q.push s
while q.length
u = q.shift()
# for each neighbor v of u
for v_id in u.adjacency_list
v = G[v_id]
if v.color == "WHITE"
v.color = "GRAY"
v.d = u.d + 1
v.parent = u
q.push v
u.color = "BLACK"
return G
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment