Course

CSE318 - Algorithm Design Strategies & Analysis

Topic

Unit-3
Shri B. Srinivasan
Assistant Professor-III, School of Computing
SASTRA Deemed To Be University
Topics
 Graph – Basic Terminologies
 Traversal Algorithms
 Breadth First Search (BFS)
 Depth First Search (DFS)
 Topological Sort
 Minimum Spanning Tree
 Prim’s Algorithm
 Kruskal’s Algorithm
 Shortest Path Algorithms
 Bellman-Ford Algorithm
 Dijkstra’s Algorithm
 Floyd-Wharshall Algorithm

 Flow Network Problem

 Ford-Fulkerson Algorithm
Graph – Basic Terminologies
 List
A

C Node May Have

Single Predecessor
&
D Single Successor
4
Data Structures & Algorithms
 Tree

Node May Have

Single Predecessor
&
Multiple Successor
5
Data Structures & Algorithms
 Graph

Node May Have

Multiple Predecessor
&
6
Multiple Successor
Data Structures & Algorithms
 Graph - Definition
A graph is simply a collection of Vertices plus Edges.
A graph G is a pair (V, E) where

 V is a set of vertices (singular “Vertex”) or nodes

 E is a set of edges that connect vertices

 A node in a graph – Vertex
 A line that connect 2 vertices – Edge
 Each edge is represented as a pair (v1, v2), where v1, v2 are vertices in V

Note: Linked lists and Tree are special cases of graphs

7
Data Structures & Algorithms
 Graph - Example
Here is a graph G = (V, E)
V = {A, B, C, D, E, F}

E = {(A,B), (A,D), (B,C), (C,D), (C,E), (D,E)}

B
C
A

D E

8
Data Structures & Algorithms
 Graph - Directed Graph vs Undirected Graph
Directed Graph (also called as “digraph”):
 Each edge has a Direction. The edge in digraph is usually called as “ARC”.
 If the order of edge pairs (v1, v2) matters, the graph is directed (also called a digraph):
(v1, v2)  (v2, v1)

v1 v2

Undirected Graph:
 The edges does not have any direction.
 If the order of edge pairs (v1, v2) does not matter, the graph is called an undirected graph:
(v1, v2) = (v2, v1)
v1 v2
9
Data Structures & Algorithms
 Digraph - Example
A vertex

arc
B E F

C D

10
Data Structures & Algorithms
 Undirected Graph - Example
A vertex

B E edge
F

C D

11
Data Structures & Algorithms
 Graph – Basic Terminology
Adjacent Vertices (neighbors)

In an undirected graph G:

 Two vertices u and v are said to be adjacent, if there exist an edge,

(u, v) in the graph G.

In a digraph G:

 Vertex u is said to be adjacent to vertex v AND Vertex v is said to be

adjacent from vertex u, if there exist an edge, (u, v) in the graph G.

 Here, u is initial vertex and v is terminal vertex.

12
Data Structures & Algorithms
 Graph – Basic Terminology
Degree of Vertex

In an undirected graph G:

 The degree of the vertex is number of edges associated with it.

In a digraph G:

 The in-degree is the number of edges with the vertex as the

terminal vertex.

 The out-degree is the number of edges with the vertex as the

initial vertex

13
Data Structures & Algorithms
 Graph – Basic Terminology

B
C Self-loop

A
F
D E Degree = 0
Degree = 3

Since an edge (A,B) is there, A and B are said to be adjacent to each other.
But, the vertices A and C are not adjacent vertices.

14
Data Structures & Algorithms
 Graph – Basic Terminology
B Loop
C
A
F
D E In-degree = 0
Out-degree = 0
In-degree = 2
Out-degree = 1

Since an edge (A,B) is there, A adjacent to B and B adjacent from A.

15
Data Structures & Algorithms
 Graph – Basic Terminology
Path

A path is a sequence of vertices with the property that each vertex in the sequence is
adjacent to the vertex next to it.

Cycle

A path consisting of at least three vertices that starts and ends with the same vertex.
Must follow the proper direction in a digraph

Loop

A special case of a cycle in which a single arc begins and ends with the same vertex

16
Data Structures & Algorithms
 Graph – Basic Terminology
A
Loop

B E F

Cycle Examples:

Path: ABEDC, ABEF, DCEF,

C D EDC, ABCED, etc.,

Cycle: EDCE

Loop: FF
17
Data Structures & Algorithms
 Graph – Basic Terminology
Connected Vertices

Two vertices are said to be connected if there exist a path between them

Strongly Connected Graph

A Directed Graph is said to be strongly connected if there is a path from every

vertex to every other vertex in the digraph

Weakly Connected Graph

A Directed Graph is said to be weakly connected when there are at least two
vertices that are not connected

18
Data Structures & Algorithms
 Graph – Basic Terminology

B E G

C D H I

Strongly Connected – For each and every pair of vertices, there exist a path.

19
Data Structures & Algorithms
 Graph – Basic Terminology

B E G

C D H I

Weakly Connected – No path exist from G to all other vertices.

20
Data Structures & Algorithms
 Graph – Basic Terminology
Complete Graph

A complete graph is a simple undirected graph in which every pair of distinct

vertices is connected by a unique edge.

B
C
A

D E

21
Data Structures & Algorithms
 Graph – Basic Terminology
Weighted Graph

The weighted graph is either directed or undirected. But every edge will
have a numerical COST or WEIGHT associated with it. The cost of the edge
is not specified, then it will be 1 by default.

22
Data Structures & Algorithms
 Graph – Basic Terminology
Directed Acyclic Graph (DAG)

A directed graph is said to be directed acyclic graph if there is no cycle in

the graph.

23
Data Structures & Algorithms
 Graph – Representation
Space and time complexity of graph algorithms are analyzed in terms of:
 Number of vertices = |V| and
 Number of edges = |E|

There are TWO basic representations for graph.

1. Adjacency Matrix
2. Adjacency List

24
Data Structures & Algorithms
 Graph – Representation
Adjacency Matrix – Undirected Graph
A B C D E F
B
C A 0 1 0 1 0 0
A
B 1 0 1 0 0 0
F
C 0 1 0 1 1 0
D E
D 1 0 1 0 1 0
E 0 0 1 1 0 0
1 if [v, w] is in E
M(v, w) =
0 otherwise F 0 0 0 0 0 0
Space = |V|2

25
Data Structures & Algorithms
 Graph – Representation
Adjacency Matrix – Digraph

B
C A 0 1 0 1 0 0
A
B 0 0 1 0 0 0
F
C 0 0 0 1 1 0
D E
D 0 0 0 0 1 0
E 0 0 0 0 0 0
1 if [v, w] is in E
M(v, w) =
0 otherwise
F 0 0 0 0 0 0

Space = |V|2

26
Data Structures & Algorithms
 Graph – Representation
Adjacency List – Undirected Graph
For each v in V, L(v) = list of w such that [v, w] is in E
a b

1 0 1 3
2 1
0 0 2

5 2 1 3 4
3 4 3 0 2 4
4 2 3
5
Space = a |V| + 2 b |E|

27
Data Structures & Algorithms
 Graph – Representation
Adjacency List – Digraph
For each v in V, L(v) = list of w such that (v, w) is in E
a b

1 0 1 3
2 1
0 2

5 2 3 4
3 4 3 4
4
0 is a source
4 is a sink 5
5 is disconnected from the rest Space = a |V| + b |E|

28
Data Structures & Algorithms
Traversal Algorithms – Breadth First Search
Traversal Algorithms – Depth First Search
Topological Sort of Edges
Minimum Spanning Tree – Prim’s
Minimum Spanning Tree – Kruskal’s
Shortest Path Algorithms – Dijkstra’s
Shortest Path Algorithms – Bellman-Ford
Bellman-Ford Algorithm
 Used to find shortest path from the given starting vertex to all other vertices
in a given graph.
 Also, used to check whether a graph contains Negative Weight Cycle (NWC)
or not.
 So, for BF algorithm, negative edges are allowed, where as the Dijkstra’s
algorithm won’t work, if graph contains negative weight cycle.
 BF algorithm report “False”, if graph contains any NWC.
 BF algorithm report “True” and calculate the shortest distance from the
starting vertex to all other vertices, only if the graph has no NWC.
60
Data Structures & Algorithms
Bellman-Ford Algorithm

61
Data Structures & Algorithms
 BF algorithm – Example – Step-by-Step

 Totally, ‘n-1’ Iterations. i.e., All the edges needs to be relaxed for n-1 times in a particular order
 In this, example, n=5, So, Need to relax all the edges for 4 times.
 Assume the order of edges as:

62
Data Structures & Algorithms
63
Data Structures & Algorithms
64
Data Structures & Algorithms
65
Data Structures & Algorithms
66
Data Structures & Algorithms
  At the end of n-1 iterations, need to check all the edges are RELAXED or NOT.
 In this example, after 4th iteration, all edges are relaxed.
 So the algorithm will return TRUE with this final Table
 The following is the shortest Path from s to all others and distances.

7 -3 -2 -4
s y x t z
7 4 2 -2

67
Data Structures & Algorithms
Shortest Path Algorithms – Floyd-Warshall
Ford-Fulkerson – Flow Network Problem
Maximum Flow Problem
 Graph problem.
 Graph is mapped with Flow Network.
 Example: Water Flow Network
 The vertices represent the tanks
 The edges represent the pipes connected between the tanks
 Edge cost maps to the capacity of the pipe. How much water it can flow?
 Problem Objective: Need to find how much stuff can be pushed from the
source to the sink.
 Known as maximum flow problem.
 Algorithm: Ford-Fulkerson Algorithm
 Conditions: 1. Flow<=Capacity
2. Incoming == Outgoing
 Some improvements done by Edmonds-Karp. So sometimes called as
Edmond-Karp algorithm.
78
Data Structures & Algorithms
Maximum Flow Problem
Residual Capacity:
 It is the capacity of the edge after subtracting the flow from the maximum
capacity
Residual Graph:
 A graph with the same vertices and same edges, but we use the residual
capacities as capacities.
Augmenting Path:
 An augmenting path is simple path in the residual graph., i.e., along the
edges whose residual capacity is positive

79
Data Structures & Algorithms
Algorithm
max_flow = 0

For each edge (u,v) in G:

flow(u,v) = w(u,v)
End For

While there is a PATH p from st in RG:

min_cap = minimum residual capacity in path p
max_flow = max_flow + min_cap
For each edge (u,v) in p:
flow(u,v) = flow(u,v) – min_cap
flow(v,u) = flow(v,u) + min_cap
End For
End While

Return max_flow

80 Note: Use BFS to find the best PATH in each iteration

Maximum Flow Problem

81
Data Structures & Algorithms
Maximum Flow Problem

82
Data Structures & Algorithms
Maximum Flow Problem

83
Data Structures & Algorithms
Maximum Flow Problem

84
Data Structures & Algorithms
Maximum Flow Problem

85
Data Structures & Algorithms
Maximum Flow Problem

86
Data Structures & Algorithms
Summary

 Breadth First Search (BFS) – Greedy Approach – O(V+E)

 Depth First Search (DFS) – Greedy Approach – O(V+E)
 Topological Sort - O(V+E)
 Prim’s Algorithm – Greedy Approach – O((V+E)log V)
 Kruskal’s Algorithm – Greedy Approach – O(E log V)
 Bellman-Ford Algorithm – Dynamic Programming – O(VE)
 Dijkstra’s Algorithm – Greedy Approach - O((E + V) log V)
 Floyd-Wharshall Algorithm – Dynamic Programming – O(V3)
 Ford-Fulkerson Algorithm – Greedy Approach - O(max_flow * E)

Problem statement - Algorithm – Example (step-by-step tracing) – Complexity – Design strategy

 2
6 7

11
1 3
5

-1 4
10 -2

5 9 4

88
Data Structures & Algorithms Introduction to Stack