class Graphlb::Algorithms::Prims

Overview

Prim's algorithm is an algorithm for finding the Minimum spanning tree in a graph, i.e the tree with the lowest weight

Given a graph and source vertex dijkstra function finds the shortest distance from the source vertex to all other vertices in the graph

Defined in:

graphlb/spanning_trees/prims.cr

Instance Method Summary

Instance Method Detail

def path_constructor(prev, source, target) #

constructs a path from source vertex to target vertex

@param : prev , prev hash contains the previous node of all the vertices

@param : Source, the source vertex for the path

@param : target, The vertex till which the path should be constructed

@return : An array which contains all the vertices(path) to be travelled to reach from source to target vertex


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

returns a hashes, which contains the information about the previous vertex of all the vertives present inside the graph


[View source]