What is a graph?
A graph is a collection of vertices and edges that connect the vertices. Figure 1 gives a visual representation of an example of a graph. There are a few features to note here, which we will discuss next:
Figure 1: Example of an undirected graph
Undirected graph: An undirected graph is a graph in which the edges have no direction, as shown in Figure 1.
Directed graph: This is a graph in which the edges have a direction.
Path: A path is a sequence of edges that connects a set of vertices that are distinct from one another, except the first and the last vertices as they may be the same. For example, in Figure 1, the edges AB, BD, and DE represent a path. It can also be described as the ABDE path, which does not repeat its vertices. In the case of a directed graph, the edges must traverse only in the specified direction to form the sequence of edges required to make a path.
Cycle: A cycle is a path with at least two vertices involved; it starts and ends on the same vertex. For...