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.