Contents

# Graph Fundamentals

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
G
=(
V
,
E
) where
V
is a set whose elements are called vertices and
E
is a set of pairs of vertices whose elements are called edges.
The vertices
i
and
j
of an edge (
i
,
j
) are called the endpoints of the edge. The edge (
i
,
j
) is said to join or connect vertices
i
and
j
. A vertex may not belong to any edge.
The edges can be directed or undirected. For an edge (
i
,
j
) of a directed graph the vertex
i
is called the tail of the edge and vertex
j
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.

#### Product and Performance Information

1

Intel's compilers may or may not optimize to the same degree for non-Intel microprocessors for optimizations that are not unique to Intel microprocessors. These optimizations include SSE2, SSE3, and SSSE3 instruction sets and other optimizations. Intel does not guarantee the availability, functionality, or effectiveness of any optimization on microprocessors not manufactured by Intel. Microprocessor-dependent optimizations in this product are intended for use with Intel microprocessors. Certain optimizations not specific to Intel microarchitecture are reserved for Intel microprocessors. Please refer to the applicable product User and Reference Guides for more information regarding the specific instruction sets covered by this notice.

Notice revision #20110804