CHAPTER 8 Graph Theory
8.1Introduction, Data Structures
Graphs, directed graphs, trees and binary trees appear in many areas of mathematics and computer science.
This and the next two chapters will cover these topics. However, in order to understand how these objects may be
stored in memory and to understand algorithms on them, we need to know a little about certain data structures.
We assume the reader does understand linear and two-dimensional arrays; hence we will only discuss linked lists
and pointers, and stacks and queues below.
Linked Lists and Pointers
Linked lists and pointers will be introduced by means of an example. Suppose a brokerage firm maintains a
file in which each record contains a customer’s name and salesman; say the file contains the following data:
Customer Adams Brown Clark Drew Evans Farmer Geller Hiller Infeld
Salesman Smith Ray Ray Jones Smith Jones Ray Smith RayThere are two basic operations that one would want to perform on the data:
Operation A: Given the name of a customer, find his salesman.Operation B: Given the name of a salesman, find the list of his customers.We discuss a number of ways the data may be stored in the computer, and the ease with which one can perform
the operationsAandBon the data.
Clearly, the file could be stored in the computer by an array with two rows (or columns) of nine names.
Since the customers are listed alphabetically, one could easily perform operationA. However, in order to perform
operationBone must search through the entire array.
One can easily store the data in memory using a two-dimensional array where, say, the rows correspond to
an alphabetical listing of the customers and the columns correspond to an alphabetical listing of the salesmen,
and where there isa1inthematrix indicating the salesman of a customer and there are 0’s elsewhere. The main
drawback of such a representation is that there may be a waste of a lot of memory because many 0’s may be in the
matrix. For example, if a firm has 1000 customers and 20 salesmen, one would need 20 000 memory locations
for the data, but only 1000 of them would be useful.
We discuss below a way of storing the data in memory which uses linked lists and pointers. By alinked list,
we mean a linear collection of data elements, callednodes, where the linear order is given by means of a field
154Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use.