Data Structure & Algorithms

231-CCS-6

Chapter 9: Graphs
TextBook: Chapter 8 pages 376-392, 395-405

Subject Coordinator : Mrs.Mariyam Aysha Bivi

Subject Teachers : Dr. Talal Qaid, Dr. Makki Akasha Babikier

Chapter 9: Graphs 1
CHAPTER 9 : GRAPHS OUTLINE
 GRAPH TERMINOLOGY
 GRAPH REPRESENTATION
 GRAPH TRAVERSALS
 SHORTEST PATHS
Dijkstra’s Algorithm
All-to-All Shortest path Algorithm
 SPANNING TREES
 CONNECTIVITY
Connectivity in Undirected Graphs
Connectivity in Directed Graphs

Chapter 9: Graphs 2
9.1 GRAPH TERMINOLOGY
 Graphs are Generalization of Trees.
 A simple graph G = (V, E) consists of a non-empty set V, whose members are called the vertices of
G, and a set E of pairs of distinct vertices from V, called the edges of G.

 A directed graph(digraph), G=(V,E) consists of a non empty set V of vertices and a set E of
edges(also called arcs). In a digraph each edge is of the form(vi,vj) ,where (vi,vj) ≠ (vj,vi)
 Weighted Graph : If each edge has a n assigned number, The Number assigned to an edge is called
its weight, cost, distance, length or some other name.
 Multi Graph : It is a graph in which two vertices can be joined by multiple edges.
Definition : A Multigraph G = (V,E,f) is composed of a set of vertices V, a set of edges E, and a
function f: E {{vi,vj} : vi,vj ε V and vi ≠ vj}
Undirected Directed (Digraph) Weighted Multi Graph

Chapter 9: Graphs 3
 A Pseudo graph : It is a Multigraph with the condition vi ≠ vj removed, which allows for loops to
occur. In Pseudo graph, a vertex can be joined with itself by an edge.
 A Path : A path from v1 to vn is a sequence of edges edge(v1,v2), edge(v2,v3),… edge(vn-1,vn) and is
denoted as path v1,v2,v3,….vn-1,vn.
 If v1 = vn and no edge is repeated, then the path is called a circuit.
 If all vertices in a circuit are different, then it is called a cycle.
 Complete Graph : A graph with n vertices is called complete and is denoted Kn if for each pair of
distinct vertices there is exactly one edge connecting them; that is each vertex can be connected to
any other vertex.
 Adjacent vertices : Vertices vi and vj are called adjacent if the edge(vi,vj) is in E. Such an edge is
called incident with the vertices vi and vj.
 Degree : The degree of a vertex v, deg(v), is the number of edges incident with v.
 Isolated Vertex : If deg(v) = 0, then v is called an isolated vertex..
Pseudo Graph Circuit Cycles Complete Graph

Chapter 9: Graphs 4
9.2 GRAPH REPRESENTATION
A . ADJACENCY LIST : It specifies all vertices adjacent to each vertex of the graph. It can be
implemented as a 1) TABLE or (STAR representation) 2) LINKED LIST
Fig : a) Graph b) Star representation(List) c) Linked List representation

Chapter 9: Graphs 5
9.2 GRAPH REPRESENTATION (Cont…)
B. MATRIX REPRESENTATION
1) Adjacency Matrix : An adjacency matrix of graph G =(V,E) is a binary
|V| X |V| matrix such that each entry of this matrix

2) Incident Matrix : An incidence matrix of graph G =(V,E) is a V| X |V| matrix such that

Chapter 9: Graphs 6
9.3 GRAPH TRAVERSALS
1. DEPTH FIRST SEARCH ALGORITHM : DFS uses stack
 Each vertex v is visited and then each unvisited vertex adjacent to v is visited.
 If a vertex v has no adjacent vertices or all of its adjacent vertices have been visited,
we backtrack to the predecessor of v.
 The traversal is finished if this visiting and backtracking process leads to the first
vertex where the traversal started.
 If there are still some unvisited vertices in the graph, the traversal continues restarting
for one of the unvisited vertices.
DFS ALGORITHM

Chapter 9: Graphs 7
 An example of application of the depthFirstSearch() algorithm to a graph.

The depthFirstSearch() algorithm applied to a digraph.

Chapter 9: Graphs 8
2. BREADTH FIRST SEARCH ALGORITHM : BFS uses queue
BFS ALGORITHM

Chapter 9: Graphs 9
 An example of application of the breadthFirstSearch() algorithm to a graph.

The breadthFirstSearch() algorithm applied to a digraph.

Chapter 9: Graphs 10
9.4 SHORTEST PATHS
9.4.1. DIJKSTRA’S ALGORITHM
 A number of paths p1,…..pn from a vertex v are tried, and each time, the shortest path is chosen
among them, which may mean that the same path pi can be continued by adding one more edge
to it.
 If pi is longer than any other path that can be tried. pi is abantoned and this other path is tried by
resuming from where it was left and by adding one more edge to it.
 Since paths can lead to vertices with more than one outgoing edge, new paths for possible
exploration are added for each outgoing edge.
 Each vertex is tried once, all paths leading from it are opened, and the vertex itself is put away
and not used anymore.
 After all vertices are visited, the algorithm is finished.

Chapter 9: Graphs 11
Fig : An Execution of Dijkstra Algorithm()

Chapter 9: Graphs 12
An Execution of Dijkstra Algorithm()

Chapter 9: Graphs 13
9.4.2. ALL-TO-ALL SHORTEST PATH PROBLEM: Initial Matrix using All-to all- algorithm
ALGORITHM (Floyd’s Method)
Wfalgorithm(matrix weight)
a b c d e
for i = 1 to |v|
for j = 1 to |v| a 0 2 ∞ -4 ∞
for k = 1 to |v| b ∞ 0 -2 1 3
if weight[j][k] > weight[j][i] + weight[i][k] c ∞ ∞ 0 ∞ 1
weight[j][k] = weight[j][i] + weight[i][k]
d ∞ ∞ ∞ 0 4
e ∞ ∞ ∞ ∞ 0
Iterations :

Chapter 9: Graphs 14
9.5 SPANNING TREES
A spanning tree of a graph is just a sub graph that contains all the vertices and is a tree.
A graph may have many spanning trees.

Graph A Some Spanning Trees from Graph A

or or or

Minimum Spanning Trees

The Minimum Spanning Tree for a given graph is the Spanning Tree of minimum cost
for that graph.
Complete Graph Minimum Spanning Tree

7
2 2
5 3 3
4
1 1
Chapter 9: Graphs 15
Kruskal’s Algorithm :
In this method, All edges are ordered by weight
STEP 1 : Find out the edge with the next minimum
weight in the Graph.
STEP 2 : Remove this edge from the graph and add
this edge to the tree, if it does not form a
Cycle. Otherwise discard that edge.
STEP 3: If tie occurs then arbitrarily select one.
Repeat the process step 1 and 2 until all
vertices are connected.

Chapter 9: Graphs 16
Kruskal’s Algorithm (Cont…)

Chapter 9: Graphs 17
9.6 CONNECTIVITY
9.6.1.CONNECTIVITY IN UNDIRECTED GRAPHS
 An undirected graph is called connected when there is a path between any two vertices of
the graph.
 A Graph is called n-connected if there are at least n different paths between any two
vertices, that is there are n paths between any two vertices that have no vertices in
common.
 A graph is a 2-connected, or biconnected graph for which there are atleat two different
paths between any two vertices.
 Articulation Point(Cut vertices) : If a vertex is removed from the graph then there is no way
to find a path from a to b,which means that the graph is split into two separate subgraph.
Ex : vertices a and b are articulation point.

 If an edge causes a graph to be split into two sub graphs, it is called bridge.
Ex : edge(bc)
 The subgraphs that result from removing an articulation point or a bridge are called
blocks,or biconnected components.

Chapter 9: Graphs 18
9.6 CONNECTIVITY (Cont…)
9.6.2.CONNECTIVITY IN DIRECTED GRAPHS
 A directed graph G = (V, E) is strongly connected if there is a directed path between
every pair of vertices [i.e, given any pair of vertices v1 and v2, there is a directed path
from v1 to v2, and there is a directed path from v2 to v1].
 A directed graph G =(V, E) is weakly connected if:
- The underlying undirected graph is connected, and if
- The is at least one pair of vertices v1 and v2 that are not reachable from one
another.
 A directed graph G = (V, E) is disconnected if the underlying undirected graph is
disconnected.

Example: A weakly connected directed graph

Chapter 9: Graphs 19