Other useful graph methods

It is very often that we need to use graphs for finding a path between two nodes. Sometimes, it is necessary to find all the paths between nodes, and in some situations, we might need to find the shortest path between nodes. For example, in routing applications, we generally use various algorithms to determine the shortest path from the source node to the destination node. For an unweighted graph, we would simply determine the path with the lowest number of edges between them. If a weighted graph is given, we have to calculate the total weight of passing through a set of edges.

Thus, in a different situation, we may have to find the longest or shortest path using different algorithms, such as a Minimum Spanning Tree, which we look into in the next section.

Minimum Spanning Tree

A Minimum Spanning Tree (MST) is a subset of the edges of the connected graph with an edge-weighted graph that connects all the nodes of the graph, with the lowest possible...