Skip to content

Instantly share code, notes, and snippets.

@gosuri
Last active December 14, 2015 17:59
Show Gist options
  • Save gosuri/5126638 to your computer and use it in GitHub Desktop.
Save gosuri/5126638 to your computer and use it in GitHub Desktop.
Recursive depth-first search (DFS) for traversing a graph in ruby.
# Depth-first search (DFS) is an algorithm for traversing or
# searching a tree, tree structure, or graph. One starts at
# the root (selecting some node as the root in the graph case)
# and explores as far as possible along each branch before backtracking.
#
# A graph can be represented by its adjacency matrix G,
# where G[i][j] == 1 if there is an edge between
# vertices i and j and 0 otherwise.
#
# Below Graph in diagram http://i.imgur.com/sV1UzUn.png
G = [0,1,1,0,0,1,1], # A
[1,0,0,0,0,0,0],
[1,0,0,0,0,0,0],
[0,0,0,0,1,1,0],
[0,0,0,1,0,1,1],
[1,0,0,1,1,0,0],
[1,0,0,0,1,0,0] # G
LABLES = %w(A B C D E F G)
def dfs(vertex)
# mark v as explored
print "#{LABLES[v]} " # visited
# nullify the row to mark the
# vertex as visited
edge = 0
while edge < G.size
G[vertex][edge] = 0
edge += 1
end
# Find unexplored edges
edge = 0
while edge < G.size
# not explored and not same vertex
if ( G[edge][vertex] != 0 && edge != vertex)
dfs(edge)
end
edge += 1
end
end
dfs(0) # Replace 0 with 1..6 to see different paths
@lievencardoen
Copy link

Great! Thx! Could it be that on line 23 v should be vertex or is there some option in Ruby that I don't know about which would try to solve and match v to visited?

@lievencardoen
Copy link

Is there a similar approach for breadth-first search?

@francisbautista
Copy link

I think you left v and forgot to replace it with vertex in line 23?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment