0.4 Graph Algorithms
A graph is a finite set of vertices and edges. Each edge
in a graph must begin and end at a different vertex (and, thus, no
edges can "loop" joining one vertex to itself). Moreover between any
pair of vertices there can be only one edge. Vertices are sometimes
also called nodes. Nodes joined by an edge are said to be adjacent.
We call moving between vertices along edges traversing a graph.
In directed graphs, or di-graphs, every edge has
orientation.
It is only possible to traverse a given edge in one direction.
All edges are like one-way streets; traffic can only flow in
a single direction.
In weighted graphs, each edge has a cost
associated with
it. To move from a pair of vertices with an edge joining them
you have to pay a toll - the price of that edge. It is often
possible, however, to circumvent expensive edges by finding a
less expensive, more indirect route, between an edge's endpoints.
In the following section we will explore several algorithms designed
to find the shortest path between two vertices.
| 
Search