Skip to content

Instantly share code, notes, and snippets.

@gosuri
gosuri / dfs.rb
Last active December 14, 2015 17:59
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
@AgileMantis
AgileMantis / bfs_maze_solver.rb
Created July 19, 2012 13:19
Ruby Breadth-first Search algorithm (implemented to solve a maze)
# (The MIT License)
#
# Copyright (c) 2012 Ledsworth Consulting LLC
#
# Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
# documentation files (the "Software"), to deal in the Software without restriction, including without limitation the
# rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit
# persons to whom the Software is furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in all copies or substantial portions of the