Graph

Algorithm Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we’ve visited it, process v, and  then visit i.e. mark the vertex as visited and process all of v’s neighbors.  Now that we’ve visited and processed all of v’s neighbors,  we need to visit and process all of v’s neighbors neighbors Example So consider the tree: [Read More]

This algorithm was first propsed by Jarnik, but typically attributed to Prim. It starts from an arbitrary vertex (root) and at each stage, add a new branch (edge) to the tree already constructed, much like a mould. The algorithm halts when all the vertices in the graph have been reached. To understand the problem statement refer here. This is similar to djikstra’s algorithm where we were clear where to begin with as we were given the source vertex, but here we have to choose arbitrarily. [Read More]

In kruskal’s algorithm the selection function chooses edges in increasing order of length without worrying too much about their connection to previously chosen edges, except that never to form a cycle. The result is a forest of trees that grows until all the trees in a forest (all the components) merge in a single tree. graph Example In Kruskal’s algorithm, we sort the edges according to their edge weights and start counting them and including them in MST, if they are not forming any cycle. [Read More]