Data Structures and Algorithms -- Class Notes, Section 2

Data Structures: § 3: Graphs and Trees

Instructor: M.S. Schmalz

After having discussed linear structures such as lists and stacks, we investigated the tree-structured heap. This should lead you to ask whether or not other tree-structured ADTs exist, and what are their uses. In this section, we examine tree-structured ADTs and summarize their various advantages and disadvantages, together with ADT operations specific to these structures. This section is organized as follows:

We begin with a discussion of theory of graphs and trees, as follows.

3.1. Mathematics of Graphs and Trees

It is often desirable to characterize relationships among data in a hierarchical fashion. This type of representation is facilitated by the tree data structure. A tree can be thought of like the geneaological trees that people use to trace their ancestors. Each internal node has one or more children, and there is often a top-level node that is the ancestor of all other nodes, which is called the root of the tree. At the bottom of the tree are the leaves. These correspond in genealogical terms to people who have not yet had children of their own.

Concept. A tree is a special type of graph. Recall from mathematics that a graph is a collections of points or vertices (which we can model as objects in algorithmic practice), as well as edges (an edge can be thought of as an association between two vertices).
Definition. A graph G = (V,E) is comprised of a set of vertices V and a set of edges E, which is an improper subset of V x V (the Cartesian product of V with itself).
Definition. A directed graph has edges that are unidirectional. That is, an edge e is represented as the tuple (v,w), where v,w v_n V. However, e cannot be simultaneously represented as the tuple (w,v). A directed graph is also called a digraph.
Definition. An undirected graph has edges that have no direction. That is, an edge e can be represented as the tuple (v,w), where v,w v_n V, and as the tuple (w,v). An undirected graph is also called a undigraph.
Definition. A path in a graph G = (V,E) is a sequence of vertices v₁, v₂,..., v_n V.
Definition. A cycle is a path in a graph that starts and ends with the same vertex.
Definition. An acyclic graph G is a graph whose paths have no cycles. If G is directed, then G is called a DAG, which is short for directed acyclic graph.