Recall that a list was a collection of nodes with two properties

- every node has a unique predecessor (except the first node)
- every node has a unique successor (except the last node).

Our general aim in this lecture is a rather brief overview to make you familiar with the terminology and one or two basic algorithms, such as traversal.

A Graph is a collection of *nodes* - which hold values - and
*edges* (or *arcs*) which connect two nodes. Usually
there is no distinguished `first' or `last' nodes.

**Directed Graph:**
A graph is a *directed* graph if the edges have a direction,
i.e.if they are arrows with a head and a tail.

**Undirected Graph:**
A graph is *undirected* if the edges are ``two way'' (have no
direction).

**Weighted Graph:**
In a *weighted* graph each arc has a number associated with it,
called its weight. For example, an edge's weight might represent the
distance between to nodes.

Here is an example of a weighted undirected graph:

**Subgraph:**
a subset of nodes and a subset of the arcs involving those nodes.

**Path:**
a sequence of nodes in which each successive pair is joined by an
edge. *Path length* in an unweighted graph = number of arcs in
the path. *Path length* in a weighted graph = sum of the
weights of the edges. e.g. in the graph above, the path ABD has length
7 + 3 = 10.

generalization of path length: the *weight* of a subgraph of
a weighted graph is the sum of the weights of the edges in the
subgraph.

**Simple Path:**
a path in which no node occurs twice.

- the path ABD in the graph above is a simple path
- the path BDCBA is not a simple path

**Cycle:**
a path (with more than one node) that starts and ends at the same
node. e.g. the path BDCB is a cycle

**Connected Graph:**
an undirected graph is *connected* if there exists a path
between every pair of nodes. We will normally restrict ourselves to
connected graphs.

**Adjacent Node:**
we say that node N2 is adjacent to node N1 if there is an edge from N1
to N2.

**Neighbours of a node:**
NEIGHBOURS (N) = set of nodes adjacent to N.