Graph problems are very common in computer science, and their applications pervade many real-life applications. Everything that can be represented by entities and their relationships can ultimately be modeled by a graph. How we connect with friends on social media, how route-planning applications are able to find the shortest route, and how e-commerce websites are able to provide us with recommendations are all examples of problems modeled by graphs.
A graph is a structure composed of a set of objects in which some pairs of objects are related. The objects are modeled by the mathematical abstraction of vertices (sometimes also called nodes), and the pairwise relationships are modeled by the mathematical abstraction of edges (sometimes also called arcs).
Edges can be directed or undirected. A directed edge is an edge which has a direction associated with it. A graph that is composed of directed edges is called a directed graph. A graph...