University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page
Computer Science 477/677
Implementations of Graphs
Revised November 10, 2005
There are several methods of implementing graphs and directed graphs
that we need to understand.
Matrix Representation.
A graph of
n
nodes is represented by an
n by n
matrix. Assume that the names of the nodes are the
integers from 1 to n.
(If not, we attach those numbers to the nodes for now.)
The entry in
row i column j
of the matrix refers to an
edge from i to j.
There are severals possible forms of matrix representation.
Most of these apply to both graphs and directed graphs.
The simplest is that each entry is a Boolean value, true
if there is an edge from i to j,
false otherwise.
For weighted graphs or directed graphs, we place a number in
row i column j, representing the
weight of that edge. If the edge does not exist, we place a default
value in that entry. What default value we use depends on the application;
for example, if we are are using the matrix for finding minimum
costs, we would use ∞ for the default value.
Neighborset Representation.
This is usually referred to as "Neighborlist" representation, but there
is no requirement that the set of neighbors be represented as a list.
We represent a graph by an array of sets, where the array is indexed by
the nodes (represented by integers 1 to n,
for example) and the ith set is the
list of neighbors of i. In the case of a directed
graph, we can either list the out-neighbors of each node, or the
in-neighbors of each node.
If our graph, or directed graph, is weighted, each item in the neighborlist
for node i will have two values, the name of the other node,
and the weight of the edge from i to that node.
Edge Set Representation.
We represent the graph as a search structure, where the items
in the search structure are the edges. This is an ideal method
of representing very sparse graphs.
All of the above representations are explicit,
meaning there are memory locations corresponding to nodes or edges
of the graph. Alternatively, we can use implicit
representation, where nodes or edges are not actually stored.
Nodes Represented Explicitly, Edges Implicitly.
We may choose to represented nodes explicitly, but represent edges implicitly.
Our reason might be that the number of nodes does not exceed the size of the
space available, but the number of edges does. Another reason would
be that the edges can be easily computed as needed, such as in
words.dat
, Knuth's graph of five-letter words of English.
The nodes of words.dat
are all five-letter English words. There is an edge from one node
to another, if the words differ by only one letter. For example, there
is an edge from "alike" to "alive." We would certainly need to store
the nodes in a dictionary, but there is no reason to store the edges.
If we need to know whether there is an edge between any two nodes,
or if we need to know all the neighbors of a node, we can easily compute
them on the fly.
Nodes and Edges both Implicitly Represented.
In this representation, nodes must be represented as items in some
data structure, and these representations must be able to be generated
as needed. In addition, there must be some way of generating edges. For
example, let G be the directed graph where the nodes are all
possible chess configurations, and the edges are all possible moves.
Not even
Deep Thought
could hold G, whose size dwarfs the number of atoms
in the known universe. Instead, we can represent each node of
G by an appropriate object of some data type, and
we then need an algorithm which generates, from each such representation,
the representations of the out-neighbors of that node.
![](../../bluhorsa.gif)