Graph Data Structures

In problems arising in computer science, mathematics, engineering, and many other disciplines we often need to represent arbitrary relationships among data objects. Directed and undirected graphs are natural models of such relationships.

An undirected graph G = (V, E) consists of a finite set of vertices V and a set of edges E. It differs from a directed graph in that each edge in E is an unordered pair of vertices. If (v, w) is an undirected edge, then (v, w) = (w, v). Hereafter we refer to an undirected graph as simply a graph.

Graphs are used in many different disciplines to model a symmetric relationship between objects. The objects are represented by the vertices of the graph and two objects are connected by an edge if the objects are related. 

A directed graph (digraph for short) G consists of a set of vertices V and a set of arcs E. The vertices are also called nodes or points; the arcs could be called directed edges or directed lines. An arc is an ordered pair of vertices (v, w); v is called the tail, and w is the head of the arc. The arc (v, w) is often expressed by v → w and drawn as

Notice that the "arrowhead" is at the vertex called the "head" and the tail of the arrow is at the vertex called the "tail." We say that arc v → w is from v to w, and that w is adjacent to v.

The vertices of a digraph can be used to represent objects and the arcs relationships between the objects. For example, the vertices might represent cities and the arcs of airplane flights from one city to another.

Happy Exploring!