next up previous index CD Book Algorithms
Next: Lecture 15 - DFS Up: No Title Previous: Lecture 13 - dynamic

Lecture 14 - data structures for graphs

Listen To Part 14-1

Problem Solving Techniques

Most important: make sure you understand exactly what the question is asking - if not, you have no hope of answer it!!  

Never be afraid to ask for another explanation of a problem until it is clear.

Play around with the problem by constructing examples to get insight into it.

Ask yourself questions. Does the first idea which comes into my head work? If not, why not?

Am I using all information that I am given about the problem?

Read Polya's book How to Solve it.

Listen To Part 14-2

16-1: The Euclidean traveling-salesman problem is the problem of determining the shortest closed tour that connects a given set of n points in the plane.    

Bentley suggested simplifying the problem by restricting attention to bitonic tours, that is tours which start at the leftmost point, go strictly left to right to the rightmost point, and then go strictly right back to the starting point.

Describe an tex2html_wrap_inline15090 algorithm for finding the optimal bitonic tour. You may assume that no two points have the same x-coordinate. (Hint: scan left to right, maintaining optimal possibilities for the two parts of the tour.)
Make sure you understand what a bitonic tour is, or else it is hopeless.

First of all, play with the problem. Why isn't it trivial?

Listen To Part 14-3

Am I using all the information?

Why will they let us assume that no two x-coordinates are the same? What does the hint mean? What happens if I scan from left to right?

If we scan from left to right, we get an open tour which uses all points to the left of our scan line.  

In the optimal tour, the kth point is connected to exactly one point to the left of k. tex2html_wrap_inline15092 Once I decide which point that is, say x. I need the optimal partial tour where the two endpoints are x and k-1, because if it isn't optimal I could come up with a better one.

Listen To Part 14-4

Hey, I have got a recurrence! And look, the two parameters which describe my optimal tour are the two endpoints.

Let c[k,n] be the optimal cost partial tour where the two endpoints are k<n.

tex2html_wrap_inline15098 (when k < n-1)


c[0, 1]=d[0, 1]

c[n-1, n] takes O(n) to update, c[k, n] k<n-1 takes O(1) to update. Total time is tex2html_wrap_inline15116 .

But this doesn't quite give the tour, but just an open tour. We simply must figure where the last edge to n must go.


Listen To Part 15-1


A graph G consists of a set of vertices V together with a set E of vertex pairs or edges.    

Graphs are important because any binary relation is a graph, so graphs can be used to represent essentially any relationship.

Example: A network of roads, with cities as vertices and roads between cities as edges.

Example: An electronic circuit, with junctions as vertices as components as edges.

To understand many problems, we must think of them in terms of graphs!

Listen To Part 15-2

The Friendship Graph

Consider a graph where the vertices are people, and there is an edge between two people if and only if they are friends.  

This graph is well-defined on any set of people: SUNY SB, New York, or the world.

What questions might we ask about the friendship graph?

Listen To Part 15-5

Data Structures for Graphs

There are two main data structures used to represent graphs.

Adjacency Matrices

An adjacency matrix is an tex2html_wrap_inline15124 matrix, where M[i,j] = 0 iff there is no edge from vertex i to vertex j  

It takes tex2html_wrap_inline15128 time to test if (i,j) is in a graph represented by an adjacency matrix.

Can we save space if (1) the graph is undirected? (2) if the graph is sparse?

Listen To Part 15-6

Adjacency Lists

An adjacency list consists of a tex2html_wrap_inline15132 array of pointers, where the ith element points to a linked list of the edges incident on vertex i.  

tex2html_wrap15228 tex2html_wrap15230
To test if edge (i,j) is in the graph, we search the ith list for j, which takes tex2html_wrap_inline15136 , where tex2html_wrap_inline15138 is the degree of the ith vertex.

Note that tex2html_wrap_inline15140 can be much less than n when the graph is sparse. If necessary, the two copies of each edge can be linked by a pointer to facilitate deletions.

Listen To Part 15-7

Tradeoffs Between Adjacency Lists and Adjacency Matrices

Comparison Winner
Faster to test if (x, y) exists? matrices
Faster to find vertex degree? lists
Less memory on small graphs? lists (m+n) vs. tex2html_wrap_inline15146
Less memory on big graphs? matrices (small win)
Edge insertion or deletion? matrices O(1)
Faster to traverse the graph? lists m+n vs. tex2html_wrap_inline15150
Better for most problems? lists

Both representations are very useful and have different properties, although adjacency lists are probably better for most problems.

Listen To Part 16-2

Traversing a Graph

One of the most fundamental graph problems is to traverse every edge and vertex in a graph. Applications include:  

For efficiency, we must make sure we visit each edge at most twice.

For correctness, we must do the traversal in a systematic way so that we don't miss anything.

Since a maze is just a graph, such an algorithm must be powerful enough to enable us to get out of an arbitrary maze.  

Listen To Part 16-3

Marking Vertices

The idea in graph traversal is that we must mark each vertex when we first visit it, and keep track of what have not yet completely explored.

For each vertex, we can maintain two flags:

We must also maintain a structure containing all the vertices we have discovered but not yet completely explored.

Initially, only a single start vertex is considered to be discovered.

To completely explore a vertex, we look at each edge going out of it. For each edge which goes to an undiscovered vertex, we mark it discovered and add it to the list of work to do.

Note that regardless of what order we fetch the next vertex to explore, each edge is considered exactly twice, when each of its endpoints are explored.

Listen To Part 16-4

Correctness of Graph Traversal

Every edge and vertex in the connected component is eventually visited.

Suppose not, ie. there exists a vertex which was unvisited whose neighbor was visited. This neighbor will eventually be explored so we would visit it:

Listen To Part 16-5

Traversal Orders

The order we explore the vertices depends upon what kind of data structure is used:

The three possible colors of each node reflect if it is unvisited (white), visited but unexplored (grey) or completely explored (black).

Listen To Part 16-6

Breadth-First Search



for each vertex tex2html_wrap_inline15152 do

color[u] = white

tex2html_wrap_inline15154 , ie. the distance from

p[u] = NIL, ie. the parent in the BFS tree

color[u] = grey

d[] = 0

p[] = NIL


while tex2html_wrap_inline15164 do

u = head[Q]

for each tex2html_wrap_inline15168 do

if color[v] = white then

color[v] = gray

d[v] = d[u] + 1

p[v] = u



color[u] = black

Listen To Part 16-8

Depth-First Search

DFS has a neat recursive implementation which eliminates the need to explicitly use a stack.  

Discovery and final times are sometimes a convenience to maintain.


for each vertex tex2html_wrap_inline15180 do

color[u] = white

parent[u] = nil

time = 0

for each vertex tex2html_wrap_inline15188 do

if color[u] = white then DFS-VISIT[u]

Initialize each vertex in the main routine, then do a search from each connected component. BFS must also start from a vertex in each component to completely visit the graph.  


color[u] = grey (*u had been white/undiscovered*)

discover[u] = time

time = time+1

for each tex2html_wrap_inline15198 do

if color[v] = white then

parent[v] = u


color[u] = black (*now finished with u*)

finish[u] = time

time = time+1

next up previous index CD Book Algorithms
Next: Lecture 15 - DFS Up: No Title Previous: Lecture 13 - dynamic

Mon Jun 2 09:21:39 EDT 1997