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
Vis a set whose elements are called vertices and
Eis a set of pairs of vertices whose elements are called edges.
jof an edge (
j) are called the endpoints of the edge. The edge (
j) is said to join or connect vertices
j. A vertex may not belong to any edge.
The edges can be directed or undirected. For an edge (
j) of a directed graph the vertex
iis called the tail of the edge and vertex
jis 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.