What is a graph? The answer depends on what kind of graph we are talking about. There are two major types: directed graphs and undirected graphs, as well as many special variations and subtypes.
A graph 
is denoted by a pair, 
where 
is a set of so-called
``vertices'' and 
is a set of ``edges'' that connect vertices to
one another. In a directed graph,
, ie, an edge
is an ordered pair of vertices; we think of an edge 
as an arrow
beginning at vertex 
and stopping at vertex 
; we say is
``adjacent'' to ; and and
are allowed to be the same vertex. In the example below,
and
. We will refer to
each end of an edge as ``attached'' to its vertex; so every edge is attached
twice-even the ``self-loop'' edge on vertex e below. Note that, for
instance, 
is adjacent to 
but not vice versa; adjacency need
not be symmetric in a directed graph.
____
| |
v |
--->a----->b<----------e----
| | |
| | |
| v v
----c----------------->d
Fig. I. A directed graph.
In an undirected graph, edges are unordered pairs
of vertices where 
. However, we will use the
notation for an edge of either kind of graph, where we must
keep in mind whether the edges are ordered or not.
The undirected graph in the example below
has the same vertices as in the directed graph above, but the edges no
longer have beginnings and ends; the edge 
is missing since
``self-loops'' are not allowed in undirected graphs; and the two
directed edges 
and 
are now just one undirected edge
connecting a and c to one another. So for undirected graphs,
adjacency is a symmetric notion.
a------b-----------e
| |
| |
| |
c------------------d
Fig. II. An undirected graph.
A graph is ``connected'' if for every two distinct vertices
and there is a path (sequence of consecutive edges) beginning
at and ending at . The undirected graph in Fig. II is connected;
but the directed one in Fig. I is not since one cannot get from b to e
(nor from b to anything, nor from d to anything). However, the following
directed graph is connected:
a----->b---------->e
^ |
| |
| v
c<-----------------d
Fig. III. A connected directed graph.
A multigraph is
essentially an undirected graph where there may be more than one edge
between two vertices, and where a vertex may be connected to itself;
in this kind of graph, special names (rather than ) must be
used to distinguish edges from one another. In the following example
of a multigraph, there are two edges connecting e and d.
a------b-----------e
| / \
| / \
| \ /
| \ /
c------------------d
Fig. IV. A multigraph
Here is an example of an unconnected undirected graph:
a------b------e
c--------d
Fig. V. An unconnected undirected graph.
The ``degree'' of a vertex is the number of edge-attachments to it. So vertices
in the multigraph in Fig. IV each have degree 2, and vertices 
have degree
3. And in the connected directed graph in Fig. III, each vertex has
degree 2. In Fig. V, b has degree 2 and the other vertices each have
degree 1. We say the graph in Fig. V has two ``components''; that is,
it consists of two subgraphs each of which is connected, but where
there is no path from one to the other. In general, a graph can have
any positive number of components; obviously it is connected if and
only if it has exactly one component.
Here is an example of a simple application of graphs: At a party of 
people,
each person
shakes hands with a certain number 
of people. The
sum of the values of 
,
, is an even number. We
can prove this by noting that an undirected graph can be used to represent who shook
hands with whom (the vertices are the people, and an edge represents a
handshake between the two vertices it connects, and the degree of any
vertex 
is the number of people shook hands with:
.
We use an undirected graph since we do not want self-loops; that would
correspond to shakings hands with oneself, which is not what we
want (and it would make the result false). So all we need to prove is that
is even, in any undirected graph. But each
edge attaches to two distinct vertices (in an undirected graph),
and so each edge contributes a 1 to the degree of each of two
vertices; so the sum is just the number of edges times 2, which is
even.
How is a graph represented in a computer? There are two standard methods: as a set of adjacency lists, or as an adjacency matrix. Essentially what we need is a way to record all the edges. Here is an example of each method, for the graph of Fig I which we repeat here, along with the two representations:
____
| |
v |
--->a----->b<----------e----
| | |
| | |
| v v
----c----------------->d
a b c d e
a -> b -> c/ a 0 1 1 0 0
b/ b 0 0 0 0 0
c -> a -> d/ c 1 0 0 1 0
d/ d 0 0 0 0 0
e -> b -> d -> e/ e 0 1 0 1 1
adjacency lists adjacency matrix
Fig. VI. A directed graph and two representations
In the adjacency-lists representation, each vertex is followed by a
list of all vertices adjacent to it; the end of the list is
indicated by a slash / . Be careful to read the lists properly: the
list headed by 
, for example, indicates that it has adjacent
vertices 
and ; it does NOT indicate that has adjacent vertex
! In fact, has nothing adjacent to it, not even to itself. The
order in which the vertices are listed after a head item is arbitrary;
thus a -
b - c / and a - c - b / would have the same meaning: is
has both and adjacent to it.
In the adjacency-matrix representation, a 1 in position 
indicates that there is an edge from vertex 
to vertex 
. Notice
that the two edges and are represented separately,
each by its own 1. In an undirected graph these would not be distinct
edges; but still we would put both 1's in those two matrix positions;
and so the matrix representation for an undirected graph is always
symmetric about the main diagonal, and we must be careful not to count
edges twice. In fact, the matrix representation is especially suited
for the handshake result we proved above using an undirected graph:
each 1 represents the shaking of hands by (say) and ; this is
one shaking (and one edge) but is doubly represented (by two 1's); and
the number of 1's in the graph is the sum of the degrees of all the
vertices, an even number due to the double representation! This
matrix in Fig. VI above has an odd number of 1's due to the fact that
it has a self-loop: e is adjacent to itself; it has degree two, but
there is room for only one 1 in position .
Adjacency lists are more compact than an adjacency matrix, since we only
record the actual edges that occur, not the ones that are not
there. The matrix version records (with a 0) edges that are not in the
graph, thereby taking up more space. On the other hand, the matrix
form allows a faster determination as to whether a vertex is
adjacent to a vertex : one simply looks for a 1 at location
in the matrix instead of searching through the (possibly long) list
headed by .
A ``weighted graph'' is a graph that has, for each edge, an associated number (weight). One can often conveniently think of a weighted graph as a map where the cities (or railway stations) are vertices, the edges are roads (or tracks), and the weights are distances (or ticket costs).
One kind of computational problem that involves graphs is that of
graph-search. Typically a path of some sort is needed, and a special
algorithm is employed to find such a path. The most famous example of
such a problem is TSP: the traveling salesperson problem. Given a weighted
graph , find a path 
that starts at vertex 
, passes exactly once
through every vertex in , and ends up back at , such that the
total cost of (the sum of all weights of edges traversed) is as
small as possible. It is not hard to solve this problem; that is, it
is not hard to come up with an algorithm that finds such a path, if
there is one at all. But all known solutions run very slow, in
time
for all integers , and it is widely believed
that no polynomial-time algorithm for TSP can exist. We will return
to this issue later.
Another famous problem is that of finding a least-cost path between
two distinct points in a weighted directed graph. A common version of this
specifies a starting vertex and asks, for all other vertices ,
to find a least-cost path from to . If the weights are
non-negative, the following is the standard solution (and apparently
the first graph-search algorithm ever written):
Dijkstra's Algorithm
Let us think of the graph as consisting of railroad stations (as
vertices) and one-way tracks (as edges). We have given as the
starting station, and for all other stations we seek a path from
to with the least total cost. We imagine that there is a
small town at , and that it expands as people move out of town and
decide a nearby station (on the border of the town) is now to be
considered in town
too, thereby altering the border. But the town does not expand to
include a new station until it is known for sure that the shortest
possible path to it from has been found (eg, so that the mayor,
who lives beside , can travel there at the lowest cost!). Key to this
is the notion of the border and the least cost to get out of town:
that will turn out to tell us which station is the next one that the
town should include.
We now present the algorithm, then an example, and finally a proof of its correctness.
Dijkstra(G=<V,E,weight-function W>,s)
declarations:
u,v,v_i,v_j: vertex variables
d=distance: array[1...n] of non-negative reals
p=predecessor: array[1...n] of vertices
border: minheap or other queue of vertices, prioritized by lowest d-value
in: boolean array[1...n]
initializations:
for all v in V do
d(v) <- infinity **no known path from s to v yet**
p(v) <- nil **no previous node on path to v yet**
in(v) <- false **no nodes in town yet**
d(s) = 0 **already at s**
border = {s} **s is at the border of town for now**
while border not empty do **main loop**
u <- extract-min(border) **this includes fixing up border with new min**
in(u) **u is now in town**
for each edge (u,v_i) leaving u do
if [not in(v_i) and d(v_i) > d(u) + w(u,v_i)] then
d(v_i) <- d(u) + w(u,v_i)n **there is a shorter way from s to v_i**
p(v_i) = u **it gets to v_i by way of u**
position v_i in border **v_i now at border of town; this includes
fixing up border priorities**
return array p of predecessor vertices
Example. Here is a directed weighted graph, with indicated weights
and a designated starting vertex :
1 4
---->a----------->c---------->e
/ / ^ . ^ . ^
2/ / \ . | . |
/ / \ . | . |
s {3 5} .1 |3 .2 |1
\ \ / . | . |
6\ \ / . | . |
\ v / v | v |
---->b----------->d---------->f
2 2
If we run Dijkstra's Algorithm on the graph, we
get the following results, shown below in a table, where the columns
indicate the distance to each vertex from , after the indicated
pass through the main loop. Also shown is the previous vertex
(initially nil or 0). Thus d/p means the distance (so far) is d and
the previous vertex is p (or 0); and ``in'' means that vertex is now
in town and its distance and previous vertex are fixed.
pass 0 1 2 3 4 5 6 7 s 0/0 in a oo/0 0+2/s in b oo/0 0+6/s 2+3/a 3+1/c in c oo/0 oo/0 2+1/a in d oo/0 oo/0 oo/0 oo/0 4+2/b 6/b in e oo/0 oo/0 oo/0 3+4/c 7/c 5+1/f 6/f in f oo/0 oo/0 oo/0 3+2/c 5/c in
Sketch of proof of correctness. The algorithm works as follows:
at any stage it checks all ways to ``get out of town'' and chooses
the shortest way (closest station) and extends the town out to it.
When it does that, the new station has been given its correct final
(least possible) distance from . We prove this by induction on the
vertices in the order
that they are pulled in. The
full argument is a bit complicated, but the outlines below are
straightforward.
The base case is 
; but clearly 
is correct. Let the
(strong) inductive hypothesis, IH, say that
already have the correct (least possible) distance when they are
pulled into town (ie, when the town expands out to them), and when
each of them was pulled in, they had the shortest path from to a
vertex out of town.
Now consider 
just before it is pulled in, ie, when
it was the min vertex at the top of the queue (eg, minheap) and
then is just being extracted; and let 
be its previous vertex.
We must show that has the shortest path out of town at that
time.
Clearly, to get to the closest new station, one must get out of town.
But the closest way out of town is to the station at the top of the
minheap. This is because the border consists of all vertices that are
not yet in town, but that are one edge away from a vertex in town.
The border vertex that has the closest distance to so far,
can never have that distance made shorter, since that would mean that
some shorter path from to would go through some other
previous vertex (not ). But such a would either be in
town (in which case, by the IH, , and not , would be its
previous vertex), or not in town (in which case there is a shorter way
out of town); so there is no such . [End of proof.]
Notice that the information contained in the relation ``previous'' at termination of the algorithm provides a way to get from the start vertex to any other (with the least cost); and that if we highlight the edges so specified by ``previous'' we get a subgraph of G that is a tree, if we regard the start vertex as the root. This is called a spanning tree for G; it contains every vertex of G (but not necessarily every edge). But its total weight (sum of all its edge weights) need not be as small as possible (ie, there might be another subtree containing all vertices of G, having a smaller total weight); a tree of this sort is called a minimum spanning tree.
Example: in the graph G below, with start vertex s, Dijkstra will find the spanning tree T1 with root s having children b and c, and b having child d for a total weight of 2+3+1.5 = 6.5, whereas the tree T2 also rooted at s but having only the child b, which in turn has child d, and d with child c, has total weight 2+1.5+2 = 5.5.
2 2 2
s -------- b s -------- b s -------- b
| | | | |
3 | G | 1.5 3 | T1 | 1.5 T2 | 1.5
| | | | |
c -------- d c d c -------- d
2 2 2
Minimum spanning trees are important enough that several algorithms have been devised to find them; one such is Kruskal's algorithm, which we present now.
Kruskal(G) [G is weighted connected graph with n vertices]
1. Sort G's edge set E into list L, from least weight to greatest weight.
2. [Initializations] Foreach v in V do T(v) <- {v} [T(v) will be a
growing subset of
vertices and edges, initially with
no edges and just one vertex v]
3. k = 1
4. While k < n do
5. pop least-weight edge <v,w> from list L
6. if T(v) =/= T(w) then do
7. T(v) <- T(v) union T(w) union <v,w>
8. T(w) <- T(v)
9. k <- k+1
10. return T [all the T(v)'s are now the same]
Applying Kruskal to the example above, we get in fact T = T2.
However, the algorithm requires repetitively finding a subset T(v)
containing a given element and then taking of the union of it and
another such subset T(w), disjoint from T(v). Fortunately there are
good algorithms for this: so-called union-find algorithms. It may
sound trivial to form the union of two (disjoint) subsets of a set
S. However, this depends on how the subsets are represented as data
structures. Most methods represent each subset by a
``representative'' element of that subset. Getting the elements back
from the representative can be done in various ways, depending on how
the elements of each subset are stored. One is to create, for each
subset, a tree whose nodes contain that subset's elements, with the
representative being at the root. Then the union of two subsets (ie,
of two trees) can be performed simply by attaching the root of one
tree as a new child of the root of the other; this takes constant
time, 
, no matter how large the subset. But the find
operation is slower with this implementation, although it can be done
in 
time.
In addition to problems of finding paths of a certain sort, there are graph-search problems of finding vertices of a certain sort. For instance, data maybe stored inside vertices (like data in heap nodes), and one might need to find the vertex with a particular kind of data (often referred to as a goal vertex). There are many standard techniques, depending on details concerning what is known about the data. For instance, the data might be sorted, in which case the search can be very fast. So-called binary search is of this sort; here one examines the value in the middle and if it is less than the goal value then the search continues to the right, else to the left. It is useful to think of such a search in terms of a so-called binary search tree, where for each non-leaf node x, all values less than the value at x lie in the left subtree below x, and the rest in the right subtree.
An important example is the so-called AVL tree; it is one of a class of search trees known as balanced trees, since there are constraints that tend to keep all the leaves at approximately the same depth. An AVL tree is a binary tree such that (i) there are data values at all non-leaf nodes, (ii) every non-leaf node has exactly 2 children, (iii) the heights of the two children of each non- leaf node differ by at most 1 (reminder: height of a node is the longest distance from it to a leaf), and (iv) for each non-leaf node (with some data value v) all the values in its left subtree are less than or equal to v, which is less than or equal to all the values in its right subtree.
If the data is not sorted, standard techniques include breadth-first search (BFS), depth-first search (DFS), iterative broadening, and heuristic search (or best-first search). In addition, there are game-tree searches, in which one has control only over every other ``move'' through the graph. Here we give only the barest rudiments of two of these (BFS and DFS) and only for trees (although there are versions of them for graphs in general).
Breadth-first search (in a tree) involves starting at the root and
examining, one by one, all the children; and only then examining the
grandchildren; and so on to still lower levels but only after the levels
above have been examined in the search for a goal vertex. The code
generally involves setting up all the children at the next level on
a to-do list, and when the first of them, , is popped off and examined,
its children (at the next level) are placed at the back of
that list so that they (actually grandchildren) come after all
the siblings of have been examined. This amounts to
saying that the list is maintained as a queue (first-in, first-out).
BFS is ``complete'': it will eventually find any (and every) goal vertex, if allowed to run long enough, even if the tree is infinitely deep; and it is ``optimal'': it will find the goals closest to the root first. But it tends to require a great deal of memory, namely all the vertices it tends to get on its to-do list (all the children at the next level). Below is a tree with the vertices numbered in the order that BFS would examine them, assuming a left-right order among siblings.
1
2 3
4 5 6 7
8 9 10 11 12 13
Depth-first search involves examining the root and then one child,
then one of its children (ie a grandchild), then one of its children
(a great grandchild) etc. The code places all the children at the
current level on the to-do list, as in BFS, but when it examines (and
pops off the list) the child at the front, its children
(actually granchildren) then go on at the front, ahead of siblings of
. Only when there are no lower levels (descendants) to examine are
the siblings examined. This amounts to saying the list is a stack
(last-in, first-out).
DFS is fast if there is a goal on a path that is searched early; but otherwise it tends to be slow and might not even find a goal at all (if the tree is infinite). Its main advantage is that it uses relatively little memory, since only a few children at the next level need to be stored at any time. In the tree below, the vertices are numbered in the order that DFS would examine them, assuming a left-right order among siblings.
1
2 9
3 6 10 13
4 5 7 8 11 12
Iterative deepening is a mixture of BFS and DFS that combines their virtues. Heuristic (or informed) search is a technique in artificial intelligence that uses special information about the tree (or graph) to allow for useful estimates (heuristics) at to what is the best vertex to examine next.
We referred above to possible infinite trees. Some comments are in
order. First, a tree is a special kind of graph in which there is one
distinguished vertex (the root), and such that, for every vertex ,
there is exactly one simple path from the root to . (A simple path
is one that does not visit any vertex more than once.) In some
applications, a tree is determined by operations that bring one from
given vertices to new ones; that is, the operations in effect create
new vertices, and thus open up the possibility of infinitely many
vertices. Example are certain kinds of game (even single-person
games) where a move creates a new state of the game, eg if state is defined
in a way the includes the past (history) of the game so far, then
every move adds to the history and so creates a new state. The
so-called state-space graph (or tree) then is potentially
infinite.
Another example comes from automated theorem-proving where, typically, one has axioms and a statement S that one wants to prove from the axioms. Often the negation of S, -S, is used as another axiom and one hopes to prove a contradiction, thereby establishing that -S cannot hold, so S is proven. In so-called resolution theorem provers, contradictions take the simple form of ``nil''; hence all one has to do is search for nil in the state space of all possible proofs (or results of proofs); but usually there are infinitely many possible proofs (and results) that can be constructed.