Algorithms Analysis and Design
Graphs
Mohammad Said Desouki
What is a Graph?
• A graph G = (V, E) is composed of:
V: set of vertices
E: set of edges connecting the vertices in V
• An edge e = (u,v) is a pair of vertices
• Example:
a b V = {a,b,c,d,e}
E = {(a,b),(a,c),(a,d),(b,e),(c,d),(c,e),(d,e)}
d e
Applications
• Transportation networks
• Communication networks
• Social Networks
• Biology (analyzing DNA)
• Computer and logic circuits
• Computer aided design (surface modeling)
• Geographic Information Systems (maps)
• Scheduling Systems (precedence constraints)
• Program structures
• architectural diagrams
• program flow
3
Directed vs. Undirected Graph
• An undirected graph is one in which the pair of vertices in a edge is
unordered, (v0, v1) = (v1,v0)
• A directed graph is one in which each edge is a directed pair of
vertices, <v0, v1> != <v1,v0>
Paths: Simple / Cycles
• path: sequence of vertices v1,v2,. . .vk such that consecutive
vertices vi and vi+1 are adjacent.
a b
• simple path: no repeated vertices bec
c
d e
• cycle: simple path, except that the last vertex is the same as the
first vertex
a b
acda
c
d e
Connectivity
• connected graph: any two vertices are connected by some path
connected not connected
• connected component: maximal connected subgraph. E.g., the graph below has
3 connected components.
Connectivity
• Let n = #vertices, and m = #edges
• A complete graph: one in which all pairs of vertices are adjacent
• How many total edges in a complete graph?
• Each of the n vertices is incident to n-1 edges, however, we would have
counted each edge twice! Therefore, intuitively, m = n(n -1)/2.
• Therefore, if a graph is not complete, m < n(n -1)/2
• If m < n - 1, G is not connected
n 5
m (5
• tree - connected graph without cycles m = n - 1
• forest - collection of trees
tree
tree
forest
tree
tree
Weighted Graphs
• In a weighted graph each edge has a weight
3 1
• Each edge’s weight represents the cost to travel
4
along that edge 2 1
2
• The cost depends on the underlying problem, 3 2
5
could be distance, time, money or some other
3
measure
9
Sub-Graphs
• A sub-graph is a subset of vertices and edges forming a graph.
• The subset of vertices of a graph is called a clique (1,2,4,6) if the
sub-graph induced by it is complete, and is called independent
set (3,4,7,8) if the sub-graph induced by it has no edges.
• A bipartite graph is an undirected graph in which the vertices
can be partitioned into two sets V1 and V2 and all edges go
between a vertex in V1 and V2
10
Representing a graph
a
b
d
adjacency matrix adjacency list
a b c d
a 0 1 0 1 a b d 0
b a c 0
b 1 0 1 0
c d 0
c 0 0 0 1 d 0
d 0 0 0 0
11
Graph Representations Adjacency Matrix
0 4
0
0
2 1 5
1 2
3 6
3 1
0 1 1 1 0 1 0
1 0 1 1 7
1 0 1
2 0 1 1 0 0 0 0 0
1 1 0 0 0 1 1 0 0 0 0
1 0
0 0
1 1 1 0
1 1 0 0 0 0
G2 0 0
G1
0 1 1 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 1 0 1 0
symmetric 0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 0
G4
0 4
Adjacency Lists
0
2 1 5
1 2 3 6
3 7
0 1 2 3 0 1 2
1 0 2 3 1 0 3
2 0 1 3 2 0 3
3 0 1 2 3 1 2
G1 0 4 5
5 4 6
0 1 6 5 7
1 0 2 1
7 6
2
G3 G4
2
Graph Traversal
• Search for a certain node or traverse all nodes in the graph
• Many problems require processing all graph vertices (and edges) in
systematic fashion
• Breadth First Search
• Start several paths at a time, and advance in each one step at a time
• Depth First Search
• Once a possible path is found, continue the search until the end of the path
Breadth First Search
After visiting a vertex, v, visit every
vertex adjacent to v before moving on
Use a queue to store nodes
Queues are FIFO
BFS:
visit and insert start
while (q not empty)
remove node from q and make it
current to move to next vertex
visit and insert the unvisited nodes
adjacent to current
15
BFS - A Graphical Representation
0 0 1
A B C D A B C D
E F G H E F G H
I J K L I J K L
M N O P M N O P
0 1 2
0 1 2 3
A B C D A B C D
E F G H E F G H
I J K L
I J K L
M N O P
M N O P
16
Depth First Search
Visit a vertex, v, move from v as deeply as possible
Use a stack to store nodes
Stacks are LIFO
DFS:
visit and push start
while (s not empty)
move to next node(nd), and push it.
if nd has an unvisited neighbour visit it and push it onto s
else pop nd from s
17
Depth-First Search
A B C D
E F G H
I J K L
M N O P
Konigsberg Bridge Problem
• A city on the Pregel River joined by 7 bridges.
• Question: Is it possible to cross all 7 bridges without
visiting any bridge twice?
• Has the graph an Eulerian Path?
• A graph has an Eulerian Path if all but at most two of
the verices must have even degree (Euler).
19
Eulerian Path/Cycle
• A postman has to visit a set of streets in order to
deliver mails and packages.
• find a path that starts and ends at the post-office, and
passes through each street (edge) exactly once.
• This way the postman will deliver mails and
packages to all streets he has to, and in the same time
will spend minimum efforts/time for the road
20
Hamiltonian Path/Cycle
• A postman has to visit a set of houses (vertices)
instead of visiting a set of streets (edges) in order to
deliver mails and packages.
• find a path that starts and ends at the post-office and
passes through each house (vertex) exactly once.
• This way the postman will deliver mails and
packages to all houses he has to, and in the same
time will spend minimum efforts/time for the road
21