Transcript chapter_08_part1

Chapter 8, Part I
Graph Algorithms
Graph Terminology
 A graph is an ordered pair G=(V,E) with a set of vertices or nodes and the
edges that connect them the nodes . (u,v) are called the endpoints of e and u
and v are said to be adjacent nodes or neighbors.
 The degree of node u, written deg(u), is the number of edges containing
adjacent nodes or neighbor.
 A cycle is closed simple path with length 3 or more.
 A node is said to be isolated if does not belong to any edge.
 A sub graph of a graph has a subset of the vertices and edges.
 The edges indicate how we can move through the graph
2
Graph Terminology
 A path is a subset of E that is a series of edges between two nodes. Or
a path P of length n from node u to node v is defined as a sequence of
n+1 nodes.
 A path P is said to be closed if vo=vn
 A path P is said to be simple if all the nodes are distinct, with the
exception that v0 may equal to vn.
 A cycle is a closed simple path with length 3 or more. A cycle of
length k is called a K-cycle.
 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.
3
Graph Terminology
• A graph is said to be connected if there is a simple path between any two of
nodes in G.
• A complete graph is one that has an edge between every pair of nodes( such a
graph is connected). A completed graph with n nodes have n(n-1)/2 edges.
• A weighted graph is one where each edge has a cost for traveling between the
nodes
4
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
5
Graph Types
• A directed graph edges’ allow travel in one direction
• An undirected graph edges’ allow travel in either direction
6
Data Structures for Graphs
an Adjacency Matrix
• There are two standards ways of maintaining a graph in G in memory of
computer. One way is called sequential representation of G, is by means of
ardency matrix A. The other way is called the linked representation of G is by
means of linked lists of neighbors.
• 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 (such a matrix which contains 0 and 1 is called bit
matrix or Boolean matrix.
7
Data Structures for Graphs
An Adjacency Matrix
• Suppose G is an undirected graph, then the adjacency matrix A of G will be
symmetric matrix. i.e. one in which Aij = Aji for every I and j. this follows from
the fact that each undirected edge( u, v) corresponds to the two directed edges (u
, v) and (v, u).
• 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
8
Adjacency Matrix Example 1
9
Adjacency Matrix Example 2
10
Data Structures for Graphs
An Adjacency List
• The sequential representation of G in memory has a number of draw backs. First
of all, it may be difficult to insert and delete nodes in G. this is because the size
of node may need to be changed and the nodes may need to be reordered, so there
may be many, many changes in the matrix A. memory also wasted if the number
of edges is O(m). So due to these reasons linked representation is used for
adjacency structure. The example of linked list is represented in class. The two
lists are required node list and edge list.
• Node list each element in the list Node will correspond to a node in G, and it will
be a record of the form
NODE
NEXT
ADJ
11
Edge list each element in the list Edge will correspond to an edge of G, and will be a
record of the form
DEST
LINK
12
Adjacency List Example 1
13
Adjacency List Example 2
14
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.
• Many algorithm requires one to systematically examine the nodes and edges of
graph G. there are two standard ways that is done . One way is called Breadth-First
search and other is called Depth-First search. Breadth-First search will use queue as
an auxiliary structure to hold nodes for future processing, and other use stack.
• There are following states called status of N
Read state
Waiting state
Processed state
15
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
16
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
17
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
18
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
19