class Graphlb::Algorithms::DFS

Overview

Depth first Search is an algorithm for finding all the vertices that are reachable from a source, vertex in a graph.

Given a graph and source vertex Depth First Search finds the vertices that are reachable from the source vertex in a graph

Defined in:

graphlb/algorithms/depth_first_search.cr

Instance Method Summary

Instance Method Detail

def reachable(graph, source) #

Given a graph and a Source vertex the DFS algorithm starts running from the sources vertex to find all the vertices that are reachable from the source vertex and the information about the previous node of all nodes

@param : graph, A graph on which the vertices are connected

@param : Source, A source vertex where the algorithm starts

@return : a tuple ([String]visited_nodes,[Hash]prev), visited nodes store the names of all the nodes that are reachable form the source vertex and prev stores the information about the previous nodes


[View source]
def run(graph, source) #

Given a graph and a Source vertex the DFS algorithm starts running from the sources vertex to find all the vertices that are visited from the source vertex.

The DFS algorithm uses stack data-structure to find the next node to visit

@param : graph, A graph on which the vertices are connected

@param : Source, A source vertex where the algorithm starts

@return : [string], An array of type string which contains all the node that are reachable form the source vertex


[View source]