Transcript CS2007Ch13B

COSC 2007
Data Structures II
Chapter 14
Graphs II
Topics

Graph implementation



Traversal


2
Adjacency matrix
adjacency list
Depth-first search
Breadth-first search
ADT Graphs

Insertion & deletion operations are somewhat different for
graphs than for other ADTs in that they apply to either nodes
or edges

Elements:



Structure:


3
A graph consists of nodes and edges. Each node will contain one data
element
Each node is uniquely identified by the key value of the element it
contains
An edge is a one-to-one relationship between a pair of distinct nodes
A pair of nodes can be connected by at most one edge, but any node
can be connected to any collection of other nodes
ADT Graphs

Operations:









4
Create an empty graph
Determine whether a graph is empty
Determine the number of nodes in a graph
Determine the number of edges in a graph
Determine whether an edge exists between two nodes
Insert a node/ an edge
Delete a node/ an edge
Retrieve a node having a given search key
Traverse a graph
Implementation of Graphs

Two common implementations:



Adjacency matrix
Adjacency list
Adjacency Matrix (Incidence Matrix)

A graph containing n nodes can be represented by an n x n matrix
of Boolean values or 1/0

5
M[i,j] = 1 (T)
graph.
0 (F)
<==> If there is an edge between node i & node j of the
Otherwise
Implementation of Graphs


Example:
A
A
B
B
L
T
R
P
6
L
C
C
R
P
P
T
T
T
B
T
L
C
A
Adjacency Matrix
T
T
T
T
T
T
T
T
T
R
Implementation of Graphs

Adjacency Matrix




7
The ith row and ith column are identical (Symmetric
matrix)
Fewer than half the entries are needed, since each edge
is recorded twice and the diagonal contains all zeros
Using a lower triangular matrix is possible, but it is not
convenient
If the graph is directed, the full matrix, except the
diagonal, is needed
Implementation of Graphs

Adjacency Lists



8
Keep an array of linked lists, one points to one LL
For each node, in the linked list, there is an edge
list of the neighbors of that node
Any other possibility?
Implementation of Graphs


Maintain each adjacency list as a linked chain
Array h head nodes keeps track of the lists

G
h[i] points to the first node of adjacency list for
vertex i
1
2
3
4
9
Implementation of Graphs

10
Questions:
2
Graph Traversal
3
1
4
5

Process each node in a graph exactly once (if &
only if the graph is connected)

The order of visiting the nodes is not unique,
because it depends on the representation
11
B
A
C
Graph Traversal
F
D


12
E
An adjacency list representation of the graph
could lead to many different orderings of the
visit, depending on the sequence in which the
edges are entered
If a graph contains a cycle, a graph-traversal
algorithm can loop indefinitely, unless the
visited nodes are marked
Graph Search Methods

A vertex u is reachable from vertex v iff
there is a path from v to u.
2
3
8
1
4
5
9
10
6
13
7
11
Graph Search Methods

A search method starts at a given vertex v
and visits/labels/marks every vertex that is
reachable from v.
2
3
8
1
4
5
9
10
14
6
7
11
Graph Search Methods

Many graph problems solved using a search
method




Commonly used search methods:


15
Path from one vertex to another
Is the graph connected?
Etc.
Depth-first search
Breadth-first search
Graph Traversal

Depth First Search (DFS)



Idea of DFS algorithm




16
Follow a path from a previous node as far as possible
before moving to the next neighbor of the starting node
DFS uses a stack to put all nodes to be traversed (ready
stack).

“Mark" a node as soon as we visit it
Try to move to an unmarked adjacent node
If there are no unmarked nodes at the present position,
backtrack along the nodes already visited, until a node is
reached that is adjacent to an unvisited node
Visit this node
Continue the process
Graph Traversal

Depth First Search (DFS)

Recursive
dfs(in v:Vertex)
// Traverses a graph beginning at node v by using a
// depth-first search (Recursive version)
Mark v as visited
for (each unvisited node u adjacent to v)
dfs(u)
17
Depth-First Search Example
2
3
8
1
4
5
9
10
6
Start search at vertex 1.
18
7
11
Graph Traversal

19
Depth First Search (DFS)
 Iterative (Using a Stack)
dfs(v)
// Traverses a graph beginning at node v by using a DFS
s.CreateStack( )
s.push ( v)
// Push v onto stack & mark it
Mark v as visited
while (!s.isEmpty( ) )
{ if (no unvisited nodes are adjacent to v on stack top)
s.pop ()
// Backtrack
else
{ Select an unvisited node u adjacent to the node on top of stack
s.push (u)
Mark u as visited
} // end if
} // end while
Graph Traversal

Breadth First Search (BFS)


20
Look at all of the neighbors of a node first, then follow the
paths from each of these nodes to its neighbors, and so
on
Nodes that have been visited but not explored are kept in
a (ready) queue, so that when we are ready to move to a
node adjacent to the current node, we will be able to
return to another node adjacent to the old current node
after our move
Graph Traversal

Breadth First Search (BFS)

21
Iterative: Using Queue
bfs( v:Vertex)
// Traverses a graph beginning at node v by using a
// Breadth-first search
q.createQueue ( )
q.enqueue(v) // Add v to queue & mark it
Mark v as visited
while (!q.isEmpty ( ) )
{ q.dequeue(w)
for (each unvisited node u adjacent to w)
{
Mark u as visited
q.enqueue(u)
} // end for
} // end while
Breadth-First Search


22
Visit start vertex and put into a FIFO queue.
Repeatedly remove a vertex from the queue, visit its
unvisited adjacent vertices, put newly visited
vertices into the queue.
Review

A graph-traversal algorithm stops when
______.




23
it first encounters the designated destination
vertex
it has visited all the vertices that it can reach
it has visited all the vertices
it has visited all the vertices and has returned
to the vertex that it started from
Review

A ______ is the subset of vertices visited
during a traversal that begins at a given
vertex.




24
circuit
multigraph
digraph
connected component
Review

An iterative DFS traversal algorithm uses
a(n) ______.




25
list
array
Queue
stack
Review

An iterative BFS traversal algorithm uses
a(n) ______.




26
list
array
Queue
stack
Review

A ______ is an undirected connected
graph without cycles.




27
tree
multigraph
digraph
connected component
Review

A connected undirected graph that has n
vertices must have at least ______ edges.




28
n
n–1
n/2
n*2
Review

A connected undirected graph that has n
vertices and exactly n – 1 edges ______.




29
cannot contain a cycle
must contain at least one cycle
can contain at most two cycles
must contain at least two cycles
Review

A tree with n nodes must contain ______
edges.




30
n
n–1
n–2
n/2