Graph Fundamentals

Developer Reference for Intel® oneAPI Math Kernel Library for C

Download PDF

ID 766684

Date 3/31/2023

Version

Public

A newer version of this document is available. Customers should click here to go to the newest version.

Visible to Intel only — GUID: GUID-A59A03B9-5155-417A-929B-5A04CF75FB17

View Details

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.

Parent topic: Appendix E: Graph Basics

Select Your Language

Using Intel.com Search

Quick Links

Recent Searches

Advanced Search

Only search in

Developer Reference for Intel® oneAPI Math Kernel Library for C

Graph Fundamentals