Scribd
Upload
8 views

Lecture 09 - Graphs Graph Algorithms

Uploaded by

luckysuthakaran
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
8 views

Lecture 09 - Graphs Graph Algorithms

Uploaded by

luckysuthakaran
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 47

ITEC 2620

Introduction to
Data Structures
:Graphs
Khairul Bashar
School of Information Technology
York University, Toronto.
Graph

• A graph G = (V,E) consists of a set of vertices V and a set of edges E


• Each edge in E connects a pair of vertices in V
Graph
Undirected Graph

a b c d e
Directed
Graph
• First vertex is source
Weighte
d Graph
• Directed graphs can also
be weighted.
Graph
• A vertex vi is adjacent to vertex vj if
they are connected by an edge in E.
• e.g. v2 and v3 – connected by e3 = ( v2,
v3)
• These vertices are neighbours
Graph
• A path is a sequence of vertices in which
each vertex is adjacent to its predecessor and
successor
• e.g. (undirected) path p = v1, v3, v2, v4
Graph
• The length of a path is the
number of edges in it
• The cost of a path is the sum of
edge weights in the path
Graph
• A cycle is a path of length greater than
one that begins and ends at the same
vertex
• e.g. (undirected) cycle c = v1, v3, v2, v1
Graph
• A simple cycle is a cycle of length
greater than three that does not visit
any vertex (except the start/finish)
more than once
Graph
• Two vertices are connected if there as a
path between them
Graph
• A subset of vertices S is a connected
component of G if there is a path from each
vertex vi to every other distinct vertex vj in
S – e.g. S = {v1, v2, v3, v4}
Graph
•The degree of a vertex is the number of edges
incident to it (the number of vertices that it is
connected to)
Graph
• A graph is acyclic if it has no cycles (e.g. a
tree)
• This graph is not acyclic
Graph
• A directed acyclic graph is called a DAG or
digraph
• This graph is not a directed acyclic graph
• Examples are inheritance and precedence
Representation
• The adjacency matrix of graph G = ( V, E ) for vertices numbered 0 to n-1 is an
n x n matrix M
• M[i][j] is 1 if there is an edge from vi to vi, and 0 otherwise
Representation

• The adjacency list of graph G = ( V, E ) for vertices numbered 0 to n-1


consists of an array of n linked lists.
• The ith linked list includes the node j if there is an edge from vi
to vj
Representation
Representation
Representation
Representation
Representation
• Comparisons and Analysis
• Which representation is better?
• |V| is number of vertices (n)
• |E| is number of edges
Representation
• Space
• Adjacency matrix uses O(|V|2) space
• Constant
• Adjacency list uses O(|V| + |E|) space
• Note: pointer overhead
• Better for sparse graphs (graphs with few edges)
Representation
• Access Time
• Is there an edge connecting vi to vj?
• Adjacency matrix – O(1)
• Adjacency list – O(d)
• Visit all edges incident to vi
• Adjacency matrix – O(n)
• Adjacency list – O(d)
Representation
• Primary operation of algorithm and density of graph determines
more efficient data structure
• Complete graphs (e.g. TSP) should use adjacency matrix
• Traversals of sparse graphs should use adjacency list
Minimum-Cost Spanning Tree
• Assume weighted (undirected) connected graph
• Use Prim’s algorithm
• A greedy algorithm
• From visited vertices, pick least-cost edge to an unvisited vertex
Minimum-Cost Spanning Tree
place edges incident on vi into a min-heap while (an un-
VISITED vertex exists)

{
remove shortest edge from heap
if new
visit that vertex – vj
add new edges incident to vj to heap
}
Minimum-Cost Spanning Tree
Minimum-Cost Spanning Tree
Minimum-Cost Spanning Tree
Minimum-Cost Spanning Tree
Minimum-Cost Spanning Tree
Minimum-Cost Spanning Tree
Minimum-Cost Spanning Tree
Minimum-Cost Spanning Tree
Shortest Path
• Assume weighted (undirected) connected graph
• Use Dijkstra’s algorithm
• A greedy algorithm
• Build paths from unvisited vertex with least current cost
Shortest Path
start at source vertex vi
for (all vertices)
{
select least cost un-VISITED vertex (vj)
visit vj
for all incident vertices to vj
update costs to un-VISITED vertices
}
Shortest Path
Shortest Path
Shortest Path
Shortest Path
Shortest Path
Shortest Path
Shortest Path
Shortest Path
Thank you

You might also like