This section provides basic definitions for graphs. Graphs are structures
describing sets of objects with some pairs of objects being connected. The objects are called
vertices and the connections between them are called edges.
A graph can be defined as a pair
is a set whose elements are called
is a set of pairs of
vertices whose elements are called edges.
of an edge (
) are called the endpoints of the edge. The
) is said to join or connect vertices
. A vertex may not belong to any edge.
The edges can be directed or undirected. For an edge (
) of a directed graph the vertex
is called the tail of the edge and vertex
is called the head of the edge.
Consider the example graph provided in the figure below where a graph with
seven vertices (depicted as circles) and 12 edges (depicted as arrows) is presented. Arrows
have a direction which means that this is a directed graph.
One of the fundamental operations on graphs is a graph traversal. A graph
traversal is the process of visiting each vertex in a graph. An example of a graph traversal
is a breadth-first search (BFS).
A BFS consists of repeated steps where at each step, the algorithm takes
the current starting set of vertices (called a frontier) and follows the outgoing edges from
this set to form the starting set for the next step. Using the tree traversal terminology, BFS
visits the sibling vertices first before visiting the child vertices. A typical traversal
avoids visiting the same vertex multiple times.
For the example graph pictured above, the BFS could start from vertex 4.
At the first step, the traverse reaches vertices 1 and 3. Then, at the second step, the
traverse reaches vertices 2, 4, 6, and vertex 4 is not considered again. So, the starting
vertex set for the next step consists of vertices 2 and 6, and so on the process repeats.