Recall that a list was a collection of nodes with two properties
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.
