Transcript Old Ch. 8: Graph Algorithms (Part 1)

Chapter 8, Part I
Graph Algorithms
Chapter Outline
•
•
•
•
•
•
•
Graph background and terminology
Data structures for graphs
Graph traversal algorithms
Minimum spanning tree algorithms
Shortest-path algorithm
Biconnected components
Partitioning sets
2
Prerequisites
• Before beginning this chapter, you should be
able to:
– Describe a set and set membership
– Use two-dimensional arrays
– Use stack and queue data structures
– Use linked lists
– Describe growth rates and order
3
Goals
• At the end of this chapter you should be
able to:
– Describe and define graph terms and concepts
– Create data structures for graphs
– Do breadth-first and depth-first traversals and
searches
– Find the minimum spanning tree for a connected
graph
– Find the shortest path between two nodes of a
connected graph
– Find the biconnected components of a connected
graph
4
Graph Types
• A directed graph edges’ allow travel in one
direction
• An undirected graph edges’ allow travel in
either direction
5
Graph Terminology
• A graph is an ordered pair G=(V,E) with a set
of vertices or nodes and the edges that
connect them
• A subgraph of a graph has a subset of the
vertices and edges
• The edges indicate how we can move through
the graph
6
Graph Terminology
• A path is a subset of E that is a series of edges
between two nodes
• A graph is connected if there is at least one path
between every pair of nodes
• The length of a path in a graph is the number of
edges in the path
7
Graph Terminology
• A complete graph is one that has an edge
between every pair of nodes
• A weighted graph is one where each edge
has a cost for traveling between the nodes
8
Graph Terminology
• A cycle is a path that begins and ends at the
same node
• An acyclic graph is one that has no cycles
• An acyclic, connected graph is also called an
unrooted tree
9
Data Structures for Graphs
an Adjacency Matrix
• A two-dimensional matrix or array that has
one row and one column for each node in
the graph
• For each edge of the graph (Vi, Vj), the
location of the matrix at row i and column j is
1
• All other locations are 0
10
Data Structures for Graphs
An Adjacency Matrix
• For an undirected graph, the matrix will be
symmetric along the diagonal
• For a weighted graph, the adjacency matrix
would have the weight for edges in the graph,
zeros along the diagonal, and infinity (∞)
every place else
11
Adjacency Matrix Example 1
12
Adjacency Matrix Example 2
13
Data Structures for Graphs
An Adjacency List
• A list of pointers, one for each node of the
graph
• These pointers are the start of a linked list of
nodes that can be reached by one edge of
the graph
• For a weighted graph, this list would also
include the weight for each edge
14
Adjacency List Example 1
15
Adjacency List Example 2
16
Graph Traversals
• We want to travel to every node in the graph
• Traversals guarantee that we will get to each
node exactly once
• This can be used if we want to search for
information held in the nodes or if we want to
distribute information to each node
17
Depth-First Traversal
• We follow a path through the graph until we
reach a dead end
• We then back up until we reach a node with
an edge to an unvisited node
• We take this edge and again follow it until
we reach a dead end
• This process continues until we back up to
the starting node and it has no edges to
unvisited nodes
18
Depth-First Traversal Example
• Consider the following graph:
• The order of the depth-first traversal of this
graph starting at node 1 would be:
1, 2, 3, 4, 7, 5, 6, 8, 9
19
Depth-First Traversal Algorithm
Visit( v )
Mark( v )
for every edge vw in G do
if w is not marked then
DepthFirstTraversal(G, w)
end if
end for
20
Breadth-First Traversal
• From the starting node, we follow all paths
of length one
• Then we follow paths of length two that go
to unvisited nodes
• We continue increasing the length of the
paths until there are no unvisited nodes
along any of the paths
21
Breadth-First Traversal Example
• Consider the following graph:
• The order of the breadth-first traversal of this
graph starting at node 1 would be: 1, 2, 8, 3, 7,
4, 5, 9, 6
22
Breadth-First Traversal Algorithm
Visit( v )
Mark( v )
Enqueue( v )
while the queue is not empty do
Dequeue( x )
for every edge xw in G do
if w is not marked then
Visit( w )
Mark( w )
Enqueue( w )
end if
end for
end while
23
Traversal Analysis
• If the graph is connected, these methods will
visit each node exactly once
• Because the most complex work is done
when the node is visited, we can consider
these to be O(N)
• If we count the number of edges considered,
we will find that is also linear with respect to
the number of graph edges
24