4. Graphs (Chapter 10)

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

  1. every node has a unique predecessor (except the first node)
  2. every node has a unique successor (except the last node).
In a tree we have (1) but not (2). In a graph we have neither property: any node can have any number of successors and any number of predecessors. In fact, we don't always distinguish between successors and predecessors.

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.

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.