DATA STRUCTURES

AND ALGORITHM

Prepared by: Maxil S. Urocay MSCS ongoing

Prepared by: Maxil S. Urocay MSCS ongoing
 GRAPH
Prepared by: Maxil S. Urocay MSCS ongoing
 GRAPH
- a non-linear data structures which is a collection of
nodes/vertices that have data and are connected to
other nodes.
- each edge connects two nodes together or possibly
the same node to itself and may contain an edge
attribute.
- are method used to manipulate and analyze graphs,
solving various problems like finding the shortest path
and more.
- applications are routing and navigation, social
networking analysis, recommendation systems,
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH REPRESENTATION

Vertices – are
A B the fundamental
unit by which
E graphs are
formed and can
C D be labelled or
unlabelled.

Prepared by: Maxil S. Urocay MSCS ongoing

GRAPH REPRESENTATION

Edges – a
A B connection
E between two
vertices and
C D can be labelled
or unlabelled.
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH REPRESENTATION
Degree – the
A B number of edges
incident to that
E vertex or the
D number of edges
C
connected to a
vertex.
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH REPRESENTATION
Degree of a
A B vertex
(Undirected
E graph) – is simply
D the count of
C
edges that are
A–3 C–2 E–3 incident to it.
B–3 D–4
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH REPRESENTATION
Degree of a
A B vertex
(Directed graph)
E – In-degree (the
D number of edges
C
coming into a
A–1 C–1 E-3 vertex)
B–1 D–2
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH REPRESENTATION
Degree of a
A B vertex
(Directed graph)
E – Out-degree (the
D number of edges
C
going out from a
A–2 C–1 E–1
vertex.
B–2 D–2
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH REPRESENTATION
Isolated vertex
A B – is a vertex in a
graph that has no
E edges connected
D to it.
C
There are no
isolated vertices.
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH REPRESENTATION
Path – a sequence
A of vertices where
B
each adjacent pair
E is connected by an
edge.
C D - a sequence of
edges that allows
A – (ABE) (ABDE) you to go.
(ACDE) Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH REPRESENTATION
Cycle – a path that
A starts and ends at
B
the same vertex
E without traversing
any edge more
C D than once.

(A-B-D-A) (A-C-D-A) (B-D-A-B) (C-D-A-C) (D-

A-C-D) (D-A-B-D) (E)
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH REPRESENTATION
Subgraph – a graph
formed from a subset
A B of the vertices and
edges of a larger
E graph.
- is a subset of
C D another graph,
consisting of a
(ABD = A-B-D-A) selection of its
(CD) (DE) (E) and more. vertices and edges.
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH REPRESENTATION
Adjacent vertices
A B – two vertices are
said to be
adjacent if there
is an edge
C D
connecting them.
A:{B,C,D} B:{A,D) C:{A,D} D:{C,A,B}
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH REPRESENTATION

A B Adjacent edges
– are edges that
share a
C D common vertex.

{A-B, B-D, D-A, A-C, C-D}

Prepared by: Maxil S. Urocay MSCS ongoing
 TYPES OF
GRAPH
Prepared by: Maxil S. Urocay MSCS ongoing
 GRAPH TYPES
- null graph - regular graph
- empty graph - complete graph
- trivial graph - cycle graph
- undirected graph - cyclic graph
- directed graph - acyclic graph
- connected graph - bipartite graph
- disconnected graph - weighted graph

Prepared by: Maxil S. Urocay MSCS ongoing

GRAPH TYPE

Null graph – a graph

which has no
vertices and no *has a degree of 0
edges, or it is an for all vertices,
absence of any since there are
graph structure. none.
- denoted as G = Ø
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH TYPE

A Empty graph – a
B graph where there
are no edges
between its vertices.
C - an n vertices is
denoted by n.
A B C is an empty graph.
n=3 Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH TYPE

Trivial graph – A
A graph which has
only one vertex and
no edges, and it is
also the smallest
A is a trivial graph graph possible.
Prepared by: Maxil S. Urocay MSCS ongoing
 GRAPH TYPE
Undirected graph – a
A graph in which edges
B
do not have any
direction. The nodes
E are unordered pairs in
the definition of every
C D edge.
(AB) (BA) - denoted by G = (V, E)
(ABDE) (EBDCA)
Prepared by: Maxil S. Urocay MSCS ongoing
 GRAPH TYPE
Directed graph – also
known as digraph
A B where edges have
direction from one
E vertex to another.
- there is a predefined
C D start point and
A-E {A-B-E, A-B-D-E, endpoint.
A-B-D-A-C-D-E}
Prepared by: Maxil S. Urocay MSCS ongoing
 GRAPH TYPE
Simple graph – a
A graph that has no
B
loops or multiple
edges between the
same pair of vertices.
D - also known as strict
C
graphs and they are
(ABDC) (ADC) unweighted and
(ADB) undirected.
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH TYPE

Multigraph – can
A B have multiple
edges between
E
the same pair of
C D vertices and
loops.
(ACDEEBAB)
Prepared by: Maxil S. Urocay MSCS ongoing
 GRAPH TYPE
Weighted graph – a
1 graph in which the
A B edges are already
0 6 1
8 specified with
4 7 E suitable numerical
2 value as weight and
C D 1 can be classified as
3
AB = 10 AC = 4 3 directed and
undirected weighted
AD – 8 BE= 6 … graphs.
Prepared by: Maxil S. Urocay MSCS ongoing
 GRAPH TYPE

A B Complete graph –
which each node
there is an edge to
each other node or
C D every pair of distinct
vertices is connected
by a unique edge.
(AB, AC, AD, BC,
BD, CD)
Prepared by: Maxil S. Urocay MSCS ongoing
 GRAPH TYPE
Connected graph –
which from one node
A B we can visit any other
node in the graph.
E - where every pair of
vertices is connected
C D by a path.
{A-C-D-E-B, A-D-E-B}
Prepared by: Maxil S. Urocay MSCS ongoing
 GRAPH TYPE
Disconnected graph –
a graph that has at
A B least two nodes that
are not connected by
E a path.
- there is at least one
C D pair of vertices that
has no path
1 - {AC} 2 - connecting these
{BDE} vertices exists.
Prepared by: Maxil S. Urocay MSCS ongoing
 GRAPH TYPE
Regular graph –
which the degree of
A B every vertex is
equal to K, and also
called as K regular
C D graph.
- each vertices
Degree = 2 {A-BC, B- have the same
AD, C-AD, D-CB} degree
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH TYPE Cycle graph – which
the graph is a cycle in
itself, the minimum
A B value of degree of
each vertex is 2.
- consist of a single
cycle, meaning it is a
C D closed path where
each vertex is
(ABDCA) (ACDBA) connected in a circular
manner.
-denoted as Cn.
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH TYPE Cyclic graph – a graph
containing at least one
cycle, or a path that starts
and end at the same
A B vertex without repeating
any edges or vertices
along the way, except the
E start and endpoint.
- can have multiple cycles
C D and may have two distinct
cycles or even more,
(ABDA) (ADCA) along with other vertices
(ADEBA) … that are not part of any
cycle.
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH TYPE
Acyclic graph – which
there is no cycle present
in it.
A B - a graph that has no
cycles, or loops.
E -made up of vertices
and edges that are
C D directed from one vertex
to another and following
(ABDE) (ACDE) (ABE) those directions will
never form a closed
loop.
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH TYPE
A B Bipartite graph – a
graph where the
vertices can be divided
D into two disjoint sets
C such that all edges
connect a vertex in one
E set to a vertex in
A={AB, AD, AE} another set.
C={CB, CD, CE}
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH TYPE
A B Star graph – is a
complete bipartite graph
in which n-1 vertices
D have degree 1 and a
single vertex have
E degree (n-1).
C
- exactly looks like a star
D = {A,B,C,E} where (n-1) vertices are
n=4 connected to a single
central vertex.
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH TYPE
A B Planar graph – a graph
that can be drawn on a
plane without any of its
D edges crossing each
other.
- means that the graph is
C E drawn in such a way that
{ABECDA…} their edges intersect
only at their endpoints.
Prepared by: Maxil S. Urocay MSCS ongoing
GRAPH TYPE
A B Finite graph – a graph
in which the vertex
set and the edge set
D
are finite sets.
Infinite graph – a
C E graph that is not
Finite graph. finite.
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY
MATRIX AND
LIST
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX
- is a square matrix used
to represent a finite
graph. A B
-indicates whether pairs of
vertices in the graph are
adjacent and can be E
applied for both directed
and undirected graph. C D
- must be symmetric
(undirected) not
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX
- Let G=(V,E) be a
graph with n vertices.
- the adjacency of A B
matrix of G is a two
dimensional n by n E
array (adj_mat)
*if the edge (Vi, Vj) is C D
in E(G) = adj_mat[i][j]
is 1.
*if there is no edge in
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX

A B C D E
A 0 1 1 1 0 A B
B 1 0 0 1 1
E
C 1 0 0 1 0
D 1 1 1 0 1 C D
E 0 1 0 1 0 UNDIRECTED
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX

A B C D E
A 0 1 1 0 0 A B
B 0 0 0 1 1
E
C 0 0 0 1 0
D 0 0 0 0 1 C D
E 0 0 0 0 0 DIRECTED
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST
- uses a list for each
vertex, where each list
contains the vertices A B
that are adjacent to that
vertex.
- represents a graph as E
an array of linked list.
C D

Prepared by: Maxil S. Urocay MSCS ongoing

 ADJACENCY LIST
A B
A B C D
B A D E E

C A C D
D
UNDIRECTED
D A B C E
E B D
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST
A B
A B C
E
B D E
C D
C D
D E DIRECTED
E none
Prepared by: Maxil S. Urocay MSCS ongoing
OPERATIONS

Prepared by: Maxil S. Urocay MSCS ongoing

 SEARCHING
OPERATION

Prepared by: Maxil S. Urocay MSCS ongoing

OPERATIONS
There are two
A B different
method:
E
Breadth First
C D Search (BFS)
UNDIRECTED and Depth First
Search (DFS)
Prepared by: Maxil S. Urocay MSCS ongoing
 DEPTH FIRST
SEARCH
TRAVERSAL (DFS)
Prepared by: Maxil S. Urocay MSCS ongoing
OPERATIONS
Depth First Search Traversal
– a traversal algorithm that
visits all the vertices of a
A B graph in the decreasing
order of its depth.
E -traverses a graph in a
depthward motion and uses
C D a stack to remember to get
the next vertex to start a
UNDIRECTED search, when a dead end
occurs will apply
backtracking.
Prepared by: Maxil S. Urocay MSCS ongoing
OPERATIONS Depth First Search Traversal –
ALGORITHM
(visit the adjacent unvisited
vertex downward, mark it as
A B visited and push it in a stack) (if
no adjacent vertex is found, pop
E up a vertex from the stack / do
the backtracking algorithm in the
C D graph and search for another
unvisited adjacent vertices).
(repeat 1 and 2 until stack is
UNDIRECTED empty and all vertices has been
visited).
Prepared by: Maxil S. Urocay MSCS ongoing
 DEPTH FIRST
SEARCH
TRAVERSAL FOR
UNDIRECTED
Prepared by: Maxil S. Urocay MSCS ongoing
DEPTH FIRST
SEARCH TRAVERSAL 1st step A Top=0
push A
A B DFS = A

E
2 nd
step
D B Top=1
C push B
A
UNDIRECTED DFS = AB
Prepared by: Maxil S. Urocay MSCS ongoing
DEPTH FIRST
SEARCH TRAVERSAL 3rd
step
D Top=2
push D
A B DFS = B
ABD A
E
4 step
th

C D Top=1
pop
UNDIRECTED DFS = B
ABD A
Prepared by: Maxil S. Urocay MSCS ongoing
DEPTH FIRST
SEARCH TRAVERSAL 5th
step
E Top=2
push E
A B DFS = B
ABDE A
E
6 step
th

C D Top=1
pop
UNDIRECTED DFS = B
ABDE A
Prepared by: Maxil S. Urocay MSCS ongoing
DEPTH FIRST
SEARCH TRAVERSAL 9th
step
Top=0
pop
A B DFS =
ABDE A
E
8 step
th

C D Top=1
push C
UNDIRECTED DFS = C
ABDEC A
Prepared by: Maxil S. Urocay MSCS ongoing
DEPTH FIRST
SEARCH TRAVERSAL 10 th
step
Top=0
pop
A B DFS =
ABDEC A
E
8 step
th

C D Top=1
pop
UNDIRECTED DFS =
ABDEC
Prepared by: Maxil S. Urocay MSCS ongoing
 DEPTH FIRST
SEARCH
TRAVERSAL FOR
DIRECTED GRAPH
Prepared by: Maxil S. Urocay MSCS ongoing
DEPTH FIRST
SEARCH TRAVERSAL 1st step

A B A Top=0
push A
DFS = A
E
2nd step B Top=1
C D push B
A
DIRECTED DFS = AB
Prepared by: Maxil S. Urocay MSCS ongoing
DEPTH FIRST D
SEARCH TRAVERSAL 3rd step B
A B A Top=2
push D
DFS = ABD
E
4th step B Top=1
C D pop
A
DIRECTED DFS = ABD
Prepared by: Maxil S. Urocay MSCS ongoing
DEPTH FIRST E
SEARCH TRAVERSAL 5th step B
A B DFS = A Top=2
push E
ABDE
E
6th step B Top=1
C D pop
DFS = A
DIRECTED ABDE
Prepared by: Maxil S. Urocay MSCS ongoing
DEPTH FIRST
SEARCH TRAVERSAL 7th step

A B DFS = A Top=0
pop
ABDE
E
8th step C Top=1
C D push C
DFS = A
DIRECTED ABDEC
Prepared by: Maxil S. Urocay MSCS ongoing
DEPTH FIRST
SEARCH TRAVERSAL 9th step

A B DFS = A Top=0
pop
ABDEC
E
10th step Top=-1
C D pop
DFS =
DIRECTED ABDEC
Prepared by: Maxil S. Urocay MSCS ongoing
 BREADTH FIRST
SEARCH
TRAVERSAL (BFS)
Prepared by: Maxil S. Urocay MSCS ongoing
OPERATIONS
Breadth First Search
Traversal – a traversal
A B algorithm that explores
all the vertices at the
E present depth level
before moving on to the
C D vertices at the next
depth level.
UNDIRECTED - typically implemented
using a queue.
Prepared by: Maxil S. Urocay MSCS ongoing
OPERATIONS
Breadth First Search
Traversal
– ALGORITHM
A B (visit the adjacent
unvisited vertex, mark it as
E visited and insert it in a
queue) (if no adjacent
C D vertex is found, remove
the first vertex from the
UNDIRECTED queue) (repeat 1 and 2
until the queue is empty)
Prepared by: Maxil S. Urocay MSCS ongoing
BREADTH FIRST
SEARCH
TRAVERSAL FOR
UNDIRECTED
GRAPH
Prepared by: Maxil S. Urocay MSCS ongoing
BREADTH FIRST
1st step
SEARCH
F=0 R=0
TRAVERSAL A enqueue A
A B
BFS = A
E 2nd step
F=0 R=1
C D A B enqueue B

UNDIRECTED BFS = AB
Prepared by: Maxil S. Urocay MSCS ongoing
BREADTH FIRST
SEARCH 3rd step
F=0 R=2
TRAVERSAL A B C enqueue C
A B
BFS = ABC
E
4th step
C D B C
F=1 R=2
dequeue
UNDIRECTED BFS = ABC
Prepared by: Maxil S. Urocay MSCS ongoing
BREADTH FIRST F=1 R=3
SEARCH 5th step enqueue E
TRAVERSAL B C E
A B
BFS = ABCE
E F=1 R=4
6th step enqueue D
C D B C E
UNDIRECTED D
BFS = ABCED
Prepared by: Maxil S. Urocay MSCS ongoing
BREADTH FIRST F=2 R=4
SEARCH 7th step dequeue
TRAVERSAL C E D
A B
BFS = ABCE
E F=3 R=4
8th step enqueue E
C D E
UNDIRECTED D
BFS = ABCED
Prepared by: Maxil S. Urocay MSCS ongoing
BREADTH FIRST F=4 R=4
SEARCH 9th step dequeue
TRAVERSAL D
A B
BFS = ABCED
E F=-1 R=-1
10th step dequeue
C D
UNDIRECTED BFS = ABCED
Prepared by: Maxil S. Urocay MSCS ongoing
 BREADTH FIRST
SEARCH
TRAVERSAL FOR
DIRECTED GRAPH
Prepared by: Maxil S. Urocay MSCS ongoing
BREADTH FIRST 1st step
SEARCH F=0 R=0
TRAVERSAL A enqueue A
A B BFS = A
2 nd
step
E
F=0 R=1
A B
C D enqueue B
BFS = AB
DIRECTED
Prepared by: Maxil S. Urocay MSCS ongoing
BREADTH FIRST 3rd step
SEARCH F=0 R=2
TRAVERSAL A B enqueue C
A B C = ABC
BFS
4 step
th F=1 R=2
E dequeue
B C
C D
BFS = ABC
DIRECTED
Prepared by: Maxil S. Urocay MSCS ongoing
BREADTH FIRST F=1 R=3
5 step
th
enqueue E
SEARCH
TRAVERSAL B C E
A B BFS =
ABCE
6 step
th F=1 R=4
E enqueue D
B C E
C D
D = ABCED
BFS
DIRECTED
Prepared by: Maxil S. Urocay MSCS ongoing
BREADTH FIRST F=2 R=4
7 step
th
dequeue
SEARCH
TRAVERSAL C E
A B D
BFS =
ABCED
8 step
th F=3 R=4
E dequeue
E
C D
D = ABCED
BFS
DIRECTED
Prepared by: Maxil S. Urocay MSCS ongoing
BREADTH FIRST F=4 R=4
9 step
th
dequeue
SEARCH
TRAVERSAL
A B D
BFS =
ABCED
10 step
th F=-1 R=-1
E dequeue

C D
BFS = ABCED
DIRECTED
Prepared by: Maxil S. Urocay MSCS ongoing
 INSERT AND
DELETE
OPERATION
(ADJACENCY
Prepared by: Maxil S. Urocay MSCS ongoing
OPERATIONS
INSERTION
*adjacency list adding an
A B edge is done by inserting
both of the vertices
connected by that in
E
each others list.
C D (ADDING EDGES
BETWEEN VERTICES)
UNDIRECTED
Prepared by: Maxil S. Urocay MSCS ongoing
EDGE INSERTION
UNDIRECTED
GRAPH
(ADJACENCY
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST A B
INSERTION
A B C D E
B A D E C D
C A D UNDIRECTED
D A B C E
Add path
E B D EC/CE
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST A B
INSERTION
A B C D E
B A D E C D
C A D E UNDIRECTED
D A B C E
Added path
E B C D EC/CE
Prepared by: Maxil S. Urocay MSCS ongoing
EDGE INSERTION
DIRECTED GRAPH
(ADJACENCY
LIST)
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST
INSERTION A B
A B C
E
B D E
C D
C D
D E DIRECTED
Add path C-B
E none
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST
INSERTION A B
A B C
E
B D E
C D
C B D
D E DIRECTED
Added path C-B
E none
Prepared by: Maxil S. Urocay MSCS ongoing
OPERATIONS
INSERTION
*adjacency list can be
A B iterated to the place
where the insertion is
required and the new
E
node can be created
C D using linked list
implementation.
UNDIRECTED (ADDING VERTEX IN THE
GRAPH)
Prepared by: Maxil S. Urocay MSCS ongoing
 VERTEX
INSERTION
UNDIRECTED
GRAPH
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST A B
INSERTION
A B C D E
B A D E C D
C A D UNDIRECTED
D A B C E
Insert F
E B D at node D
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST UNDIRECTED
INSERTION
A B
A B C D
B A D E E

C A C D F
D
Inserted F
D A B C E F at node D
E B D
F D Prepared by: Maxil S. Urocay MSCS ongoing
 VERTEX
INSERTION
DIRECTED GRAPH
(ADJACENCY
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST
INSERTION A B
A B C
E
B D E
C D
C D
D E DIRECTED
Insert F at
E none node E (E-F)
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST
INSERTION A B
A B C
E
B D E
C D
C D
D E DIRECTED F
Inserted F
E F at node E
F none (F-E)
Prepared by: Maxil S. Urocay MSCS ongoing
OPERATIONS DELETION
*adjacency list – to
delete edge between (u,
A B v), u’s adjacency list is
traversed until v is found
E and it is removed from it.
(REMOVING EDGES
C D BETWEEN VERTICES)

UNDIRECTED
Prepared by: Maxil S. Urocay MSCS ongoing
EDGE DELETION
UNDIRECTED
GRAPH
(ADJACENCY
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST A B
DELETION
A B C D E
B A D E C D
C A D UNDIRECTED
D A B C E
Remove
E B D path BD/DB
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST A B
DELETION
A B C D E
B A E C D
C A D UNDIRECTED
D A C E
Removed
E B D path BD/DB
Prepared by: Maxil S. Urocay MSCS ongoing
EDGE DELETION
DIRECTED GRAPH
(ADJACENCY
LIST)
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST
DELETION A B
A B C
E
B D E
C D
C D
D E DIRECTED
Remove
E none path A-B
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST
DELETION A B
A C
E
B D E
C D
C D
D E DIRECTED
Removed
E none path A-B
Prepared by: Maxil S. Urocay MSCS ongoing
OPERATIONS DELETION
*adjacency list can be
iterated through the list
A B of each vertex if an edge
is present or not. If the
E edge is present, then
delete the vertex in the
C D same way as deletion
performed in a linked
UNDIRECTED list.
(REMOVING VERTEX IN
Prepared by: Maxil S. Urocay MSCS ongoing
 VERTEX
DELETION
UNDIRECTED
GRAPH
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST A B
DELETION
A B C D E
B A D E C D
C A D UNDIRECTED
D A B C E
Delete node B
E B D
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST
A
DELETION
A C D
E
B removed
C D
C A D UNDIRECTED
D A C E
Deleted node
E D B
Prepared by: Maxil S. Urocay MSCS ongoing
 VERTEX
DELETION
DIRECTED GRAPH
(ADJACENCY
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST
DELETION A B
A B C
E
B D E
C D
C D
D E DIRECTED
Delete node A
E none
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY LIST
DELETION B
A removed
E
B D E
C D
C D
D E DIRECTED
Deleted node A
E none
Prepared by: Maxil S. Urocay MSCS ongoing
 INSERT AND
DELETE
OPERATION
(ADJACENCY
Prepared by: Maxil S. Urocay MSCS ongoing
OPERATIONS INSERTION
*adjacency matrix to add
edges between two
A B existing vertices such as
vertex x and y , then the
E elements g[x][y] and g[y]
[x] of the adjacency
C D matrix will be assigned to
1.
UNDIRECTED (ADDING EDGES
BETWEEN VERTICES)
Prepared by: Maxil S. Urocay MSCS ongoing
 EDGE INSERTION
UNDIRECTED
GRAPH (ADJACENCY
MATRIX)
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX
A B
A B C D E
A 0 1 1 1 0 E
B 1 0 0 1 1
C D
C 1 0 0 1 0
D 1 1 1 0 1 UNDIRECTED
E 0 1 0 1 0 Add path BC/CB.
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX
A B
A B C D E
A 0 1 1 1 0 E
B 1 0 1 1 1
C D
C 1 1 0 1 0
D 1 1 1 0 1 UNDIRECTED
E 0 1 0 1 0 Added the path
BC/CB.
Prepared by: Maxil S. Urocay MSCS ongoing
EDGE INSERTION
DIRECTED GRAPH
(ADJACENCY
MATRIX)
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX

A B C D E
A 0 1 1 0 0 A B
B 0 0 0 1 1
E
C 0 0 0 1 0
D 0 0 0 0 1 C D
E 0 0 0 0 0 DIRECTED
Add path B-C.
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX

A B C D E
A 0 1 1 0 0 A B
B 0 0 1 1 1
E
C 0 0 0 1 0
D 0 0 0 0 1 C D
E 0 0 0 0 0 DIRECTED
Added path B-C.
Prepared by: Maxil S. Urocay MSCS ongoing
OPERATIONS INSERTION
*adjacency matrix to add
vertex in the graph, we
A B need to increase both the
row and column of the
E existing adjacency matrix
and then initialize the
C D new elements related to
that vertex to 0.
UNDIRECTED (ADDING VERTEX IN THE
GRAPH)
Prepared by: Maxil S. Urocay MSCS ongoing
VERTEX INSERTION
UNDIRECTED
GRAPH (ADJACENCY
MATRIX)
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX
A B
A B C D E
A 0 1 1 1 0 E
B 1 0 1 1 1
C D
C 1 1 0 1 0
D 1 1 1 0 1 UNDIRECTED
E 0 1 0 1 0 Insert F at node D.
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX
A B C D E F A B
A 0 1 1 1 0 0 E
B 1 0 0 1 1 0
C D F
C 1 0 0 1 0 0
D 1 1 1 0 1 1
UNDIRECTED
E 0 1 0 1 0 0
Inserted F at node
F 0 0 0 1 0 0
D.
Prepared by: Maxil S. Urocay MSCS ongoing
VERTEX INSERTION
DIRECTED GRAPH
(ADJACENCY
MATRIX)
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX

A B C D E
A 0 1 1 0 0 A B
B 0 0 0 1 1
E
C 0 0 0 1 0
D 0 0 0 0 1 C D
E 0 0 0 0 0 DIRECTED
Insert F at node B (B-
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX
A B C D E F
A 0 1 1 1 0 0
A B
B 1 0 0 1 1 1 F
C 1 0 0 1 0 0 E
D 1 1 1 0 1 0
C D
E 0 1 0 1 0 0
F 0 0 0 0 0 0
DIRECTED
Inserted F at node B
Prepared by: Maxil S. Urocay MSCS ongoing
OPERATIONS
DELETION
*adjacency matrix –
removing an edge between
A B two vertices i and j, set the
corresponding values in the
E adjacency matrix equal to
0. Set g[i][j]=0 and g[j][i]=0
C D if both the vertices i and j
exists.
UNDIRECTED (REMOVING EDGE IN THE
GRAPH)
Prepared by: Maxil S. Urocay MSCS ongoing
 EDGE DELETION
UNDIRECTED
GRAPH (ADJACENCY
MATRIX)
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX
A B
A B C D E
A 0 1 1 1 0 E
B 1 0 1 1 1
C D
C 1 1 0 1 0
D 1 1 1 0 1 UNDIRECTED
E 0 1 0 1 0 Remove path
CD/DC
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX
A B
A B C D E
A 0 1 1 1 0 E
B 1 0 1 1 1
C D
C 1 1 0 0 0
D 1 1 0 0 1 UNDIRECTED
E 0 1 0 1 0 Removed path
CD/DC
Prepared by: Maxil S. Urocay MSCS ongoing
EDGE DELETION
DIRECTED GRAPH
(ADJACENCY
MATRIX)
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX

A B C D E
A 0 1 1 0 0 A B
B 0 0 0 1 1
E
C 0 0 0 1 0
D 0 0 0 0 1 C D
E 0 0 0 0 0 DIRECTED
Remove path D-E
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX

A B C D E
A 0 1 1 0 0 A B
B 0 0 0 1 1
E
C 0 0 0 1 0
D 0 0 0 0 0 C D
E 0 0 0 0 0 DIRECTED
Remove path D-E
Prepared by: Maxil S. Urocay MSCS ongoing
OPERATIONS DELETION
*adjacency matrix – to remove
a vertex from the graph, we
need to check if that vertex
A B exists or not, then we need to
shift the rows to the left and the
columns upwards of the
E adjacency matrix so that the
row and column values of the
C D given vertex gets replaced by
the values of the next vertex
and then decrease the number
UNDIRECTED of vertices by 1.
(REMOVING VERTEX IN THE
GRAPH)
Prepared by: Maxil S. Urocay MSCS ongoing
VERTEX DELETION
UNDIRECTED
GRAPH (ADJACENCY
MATRIX)
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX
A B
A B C D E
A 0 1 1 1 0 E
B 1 0 1 1 1
C D
C 1 1 0 1 0
D 1 1 1 0 1 UNDIRECTED
E 0 1 0 1 0 Remove node C
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX
A B
A B D E
A 0 1 1 0 E
B 1 0 1 1
D
D 1 1 0 1
E 0 1 1 0 UNDIRECTED
Removed node C
Prepared by: Maxil S. Urocay MSCS ongoing
VERTEX DELETION
DIRECTED GRAPH
(ADJACENCY
MATRIX)
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX

A B C D E
A 0 1 1 0 0 A B
B 0 0 0 1 1
E
C 0 0 0 1 0
D 0 0 0 0 1 C D
E 0 0 0 0 0 DIRECTED
Remove node A
Prepared by: Maxil S. Urocay MSCS ongoing
 ADJACENCY MATRIX

B C D E
B 0 0 1 1 B
C 0 0 1 0
E
D 0 0 0 1
E 0 0 0 0 C D
DIRECTED
Removed node A
Prepared by: Maxil S. Urocay MSCS ongoing
 SPANNING
TREE
Prepared by: Maxil S. Urocay MSCS ongoing
SPANNING TREE
– is a subset of an undirected
1 1
graph that contains all the A B
vertices of the graph 0
connected with the minimum 8 7
number of edges in the graph. 4
- does not have any cycle and 2
C D
any vertex can be reached 3
from any other vertex.
- applications: network design,
routing algorithm, cluster
analysis and more.
Prepared by: Maxil S. Urocay MSCS ongoing
 SPANNING TREE
- has n-1 edges where n is the
number of nodes. A B
- a connected graph G can have
more than one spanning tree.
- is minimally connected, so
removing one edge from the tree
will make the graph disconnected. C D
-a tree that connects all vertices
of an undirected graph and not
applicable to directed graph.
-Type: Minimum & Maximum.
Prepared by: Maxil S. Urocay MSCS ongoing
SPANNING TREE
A B A B A B

1st
D C D C 2nd D
C
GIVEN

Prepared by: Maxil S. Urocay MSCS ongoing

 SPANNING TREE
A B A B A B

3rd
4th
C D C D C D
GIVEN

Prepared by: Maxil S. Urocay MSCS ongoing

SPANNING TREE
A B A B A B

6th
C D C 5th D C D
GIVEN

Prepared by: Maxil S. Urocay MSCS ongoing

 MINIMUM
SPANNING
TREE
Prepared by: Maxil S. Urocay MSCS ongoing
MINIMUM SPANNING TREE
- can be defined as the 1 1
spanning tree in which the A B
sum of the weights of the
0
edge is minimum.
8 7
4
-in real-world situations, this 2
weight can be measured as C D
distance, congestion, traffic
3
load or any arbitrary value
denoted to the edges.
Prepared by: Maxil S. Urocay MSCS ongoing
MINIMUM SPANNING TREE

1 A B
1
A B 8
0 4 7
8 7
4 C D
2
C D MST = 4+8+7
3
=19
Prepared by: Maxil S. Urocay MSCS ongoing
 MAXIMUM
SPANNING
TREE
Prepared by: Maxil S. Urocay MSCS ongoing
MAXIMUM SPANNING TREE
-similar to minimum 1 1
spanning tree but instead A B
maximizes the total weight
0
of the tree instead of
8 7
4
minimizing it. 2
-applications: where you C D
want to maximize
3
connectivity in a weighted
graph.
Prepared by: Maxil S. Urocay MSCS ongoing
MINIMUM SPANNING TREE
1
1 A B
1 0
A B 8
0
8 7 2
4 C D
2 3
C D Maximum ST
3 = 23 + 10 + 8
= 41
Prepared by: Maxil S. Urocay MSCS ongoing
 PRIM’S
ALGORITHM
Prepared by: Maxil S. Urocay MSCS ongoing
PRIM’S ALGORITHM
-a greedy algorithm that starts
1 1
with an empty spanning tree. A B
-used to find minimum spanning 0
tree as well as maximum 8 7
spanning tree from the graph. 4
-subset of edges that includes 2
every vertex of the graph such C D
that the sum of the weights of the 3
edges can be
minimized/maximized.
-a collection of edges in a graph,
that connects all vertices, with a
Prepared by: Maxil S. Urocay MSCS ongoing
minimum/maximum sum of edge
PRIM’S ALGORITHM
ALGORITHM:
1 1
*Determine an arbitrary vertex as
A B
the starting vertex of the 0
spanning tree.
8 7
*Find all the edges that connect 4
the tree in the above step with
the new vertices. From the edges 2
C D
found, select the 3
minimum/maximum edge and
add it to the tree if it does not
form any cycle.
*Repeat 2nd step until the
mimimum/maximum spanning
Prepared by: Maxil S. Urocay MSCS ongoing
PRIM’S ALGORITHM
1 1
APPLICATIONS: A B
*can be used in network 0
designing, 8 7
4
*to make network cycles, 2
*can be used to lay down C D
3
electrical wiring cables.

Prepared by: Maxil S. Urocay MSCS ongoing

 MINIMUM
SPANNING TREE
USING PRIM’S
ALGORITHM
1 Example
st
Prepared by: Maxil S. Urocay MSCS ongoing
PRIM’S ALGORITHM
FIRST EXAMPLE Suppose A is our Initial

1 1 State.
A B A
0 1st step
8 7 2nd step
4 A
2
C D
3 4
C
Prepared by: Maxil S. Urocay MSCS ongoing
PRIM’S ALGORITHM
FIRST EXAMPLE 3rd step
1 1
A B A
0
8 7 8
4 4
2 C D
C D
3

Prepared by: Maxil S. Urocay MSCS ongoing

PRIM’S ALGORITHM
FIRST EXAMPLE 4th step

1 1 A B
A B
0 8 7
8 4
4 7
2 C D
C D 4 Vertices and MST consist of 3
3
edges
MST = 4+8+7
= 19
Prepared by: Maxil S. Urocay MSCS ongoing
 MINIMUM
SPANNING TREE
USING PRIM’S
ALGORITHM
Prepared by: Maxil S. Urocay MSCS ongoing
 PRIM’S ALGORITHM 1st step
SECOND EXAMPLE
22
A
12 C E
9 2nd step
A 5 4 1
34 5
D F A 5
13
B 23 D

Prepared by: Maxil S. Urocay MSCS ongoing

 PRIM’S ALGORITHM
SECOND EXAMPLE 3rd step
22
12 C E
C
9
A 5 4 1
34 5 A 5 4
13 D F
D
B 23

Prepared by: Maxil S. Urocay MSCS ongoing

 PRIM’S ALGORITHM
SECOND EXAMPLE
4th step
22
C E
12 C
9
A 5 4 1 9
34 5 A 5 4
13 D F
D F
B 23

Prepared by: Maxil S. Urocay MSCS ongoing

 PRIM’S ALGORITHM
SECOND EXAMPLE 5th step
22 C
12 C E 9
9 A 5 4
A 5 4 1
34 5 F
13 D
13 D F
B
B 23

Prepared by: Maxil S. Urocay MSCS ongoing

 PRIM’S ALGORITHM
SECOND EXAMPLE 6th step
C E
22
C E 9
12 A 5 4 1
9 5
A 5 4 1
F
34 5 13 D
13 D F
B
B 23 6 edges & 6 steps
MST = 4+5+9+13+15
= 46
Prepared by: Maxil S. Urocay MSCS ongoing
MAXIMUM SPANNING
TREE USING PRIM’S
ALGORITHM
1 Example
st

Prepared by: Maxil S. Urocay MSCS ongoing

 PRIM’S ALGORITHM
FIRST EXAMPLE
Suppose A is our Initial
State.
1 1
1 step
st
A B
A 0
8 7
2 nd
step 4
2
1 C D
A 3
0 B
Prepared by: Maxil S. Urocay MSCS ongoing
PRIM’S ALGORITHM
FIRST EXAMPLE
3rd step
1 1 1
A B A B
0 0
8 8 7
4
2
D C D
3
Prepared by: Maxil S. Urocay MSCS ongoing
PRIM’S ALGORITHM
FIRST EXAMPLE
4th step
1 1 1
A B A
0 0 B
8 8
4 7
2 2
C D C D
3 3
4 vertex, 3 edges
MaximumST: 23+10+8
=41
Prepared by: Maxil S. Urocay MSCS ongoing
MAXIMUM SPANNING
TREE USING PRIM’S
ALGORITHM
2 Example
nd

Prepared by: Maxil S. Urocay MSCS ongoing

 PRIM’S ALGORITHM SECOND EXAMPLE
1st step

A 22
12 C E
9
2 nd
step A 5 4 1
C 34 5
12 F
13 D
A
B 23

Prepared by: Maxil S. Urocay MSCS ongoing

PRIM’S ALGORITHM SECOND EXAMPLE

3rd step
22
12 C E
22 9
12 C E A 5 4 1
34 5
A 13 D F
B 23

Prepared by: Maxil S. Urocay MSCS ongoing

PRIM’S ALGORITHM SECOND EXAMPLE

4th step
22
12 C E
22
12 C E 9
A 5 4 1
34 5
A 1
5 13 D F
F
B 23

Prepared by: Maxil S. Urocay MSCS ongoing

PRIM’S ALGORITHM SECOND EXAMPLE

5th step
22
22 C E
12 C E 12
9
A 1 A 5 4 1
34 5
34 5
F 13 D F
D
B 23

Prepared by: Maxil S. Urocay MSCS ongoing

PRIM’S ALGORITHM SECOND EXAMPLE
6th step 22
12 C E 22
12 C E
A 1
34 5 9
A 5 4 1
D F 34 5
13 D F
B 23
6 vertex, 5 edges B 23
MaximumST: 34+23+22+15+12
=106 Prepared by: Maxil S. Urocay MSCS ongoing
KRUSKAL’S
ALGORITHM
Prepared by: Maxil S. Urocay MSCS ongoing
KRUSKAL’S ALGORITHM
-used to find the
1 1
minimum/maximum spanning A B
tree for a connected weighted 0
graph. 8 7
-also follows greedy approach, 4
which finds an optimum 2
C D
solution at every stage instead 3
of focusing on a global
optimum.
-the greedy choice is to pick the
smallest/largest weight edge
that does not cause a cycle in
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
ALGORITHM:
*Sort all the edges from low weight
to high (Ascending to Descending
1 1
order) or Vice versa if Maximum
A B
spanning tree. 0
*Take the edge with the
8 7
lowest/largest weight and add it to 4
the spanning tree. If adding the
2
edge created a cycle, then reject
C D
this edge. 3
*Keep adding edges until we reach
all vertices (n-1 edges, where n is
Prepared by: Maxil S. Urocay MSCS ongoing
the # of vertices.
 KRUSKAL’S ALGORITHM

APPLICATIONS: 1
*can be used to layout 1
A B
electrical wiring among cities. 0
*can be used to lay down LAN 8 7
connections. 4
2
C D
3

Prepared by: Maxil S. Urocay MSCS ongoing

MINIMUM SPANNING
TREE USING
KRUSKAL’S
ALGORITHM
1 Example
st
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S
ALGORITHM
FIRST EXAMPLE WEIGHT VERTEX VERTEX

1 1 SOURCE DESTINATIO
N

A B
0 1 B B
8 7 4 A C
4 7 B D
2
C D 8 A D
3
10 A B
23 C D
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX 1st step 2nd step
SOURCE DESTINATIO
N
NO A
1 B B ❌ CHANGES
4 A C ✅
7 B D 4
8 A D
C
10 A B
23 C D
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SOURCE DESTINATIO 3rd step
N

1 B B ❌ A B
4 A C ✅
7 B D ✅ 4 7
8 A D
C D
10 A B
23 C D
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SOURCE DESTINATIO 4th step
N
A B
1 B B ❌ 8 7
4 A C ✅ 4
7 B D ✅
8 A D C D
✅
10 A B 5th step NO CHANGES
❌ 6th step NO CHANGES
23 C D ❌ MINIMUM = 4+7+8
Prepared by: Maxil S. Urocay MSCS ongoing = 19
MINIMUM SPANNING
TREE USING
KRUSKAL’S
ALGORITHM
2 Example
nd
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SECOND EXAMPLE SOURCE DESTINATIO
N
22
12 C E 4 C D
5 A D
9
A 5 4 1 9 C F
5 12 A C
34
13 D F 13
15
B
E
D
F
22 C E
B 23
23 B F
34 D F
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SOURCE DESTINATIO 1st step
N

4 C D ✅ C
5 A D
9 C F
4
12 A C
13 B D
15 E F
D
22 C E
23 B F
34 D F
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SOURCE DESTINATIO 2nd step
N

4 C D
5 A D
✅ C
✅
9 C F
12 A C
A 5 4
13 B D
15 E F D
22 C E
23 B F
34 D F
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SOURCE DESTINATIO 3rd step
N

4 C D ✅
5 A D ✅ C
9 C F ✅ 9
12 A C A 5 4
13 B D
15 E F
D F
22 C E
23 B F
34 D F
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SOURCE DESTINATIO 4th step
N
NO CHANGES
4 C D ✅
5 A D ✅ C
9 C F ✅
12 A C ❌ 9
13 B D
A 5 4
15 E F
22 C E D F
23 B F
34 D F
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SOURCE DESTINATIO 5th step
N

4 C D ✅ C
5 A D ✅ 9
9 C F ✅ A 5 4
12 A C ❌
13 B D ✅
13 D F
15 E F
22 C E
23 B F
B
34 D F
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
6th step
SOURCE DESTINATIO
N C E
4 C D ✅ 9
5 A D ✅
A 5 4 1
9 C F
5
✅
12 A C ❌ 13 D F
13 B D ✅
7th step NO CHANGES
15 E F ✅ B 8th step NO CHANGES
22 C E ❌
9th step NO CHANGES
23 B F ❌
34 D F ❌ MINIMUM = 4+5+9+13+15
= 46
Prepared by: Maxil S. Urocay MSCS ongoing
MAXIMUM SPANNING
TREE USING
KRUSKAL’S
ALGORITHM
1 Example
st
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S
ALGORITHM
FIRST EXAMPLE WEIGHT VERTEX VERTEX

1 1 SOURCE DESTINATIO
N

A B
0 23 C D
8 7 10 A B
4 8 A D
2
C D 7 B D
3
4 A C
1 B B
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SOURCE DESTINATIO
N
1st step

23 C D ✅
2
10 A B C D
8 A D 3
7 B D
4 A C
1 B B
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SOURCE DESTINATIO
N
2nd step

23 C D ✅ 1
10 A B ✅ A B
0
8 A D
7 B D
4 A C 2
C D
1 B B 3
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
3rd step
SOURCE DESTINATIO 1
N A B
0
23 C D ✅ 8
10 A B ✅
8 A D 2
✅ C D
7 B D ❌
3
4 step NO
th

4 A C ❌ 5 th
step NO
CHANGES
6 th
step NO
CHANGES
1 B B ❌ MAXIMUM = 23+10+8
CHANGES
= 41
Prepared by: Maxil S. Urocay MSCS ongoing
MAXIMUM SPANNING
TREE USING
KRUSKAL’S
ALGORITHM
2 Example
nd
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SECOND EXAMPLE SOURCE DESTINATIO
N
22
12 C E 34 D F
23 B F
9
A 5 4 1 22 C E
5 15 E F
34
13 D F 13
12
B
A
D
C
9 C F
B 23
5 A D
4 C D
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SOURCE DESTINATIO 1st step
N

34 D F ✅
23 B F 34
22 C E D F
15 E F
13 B D
12 A C
9 C F
5 A D
4 C D
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SOURCE DESTINATIO 2nd step
N

34 D F ✅
23 B F
34
22 C E
✅ D F
15 E F
13 B D B 23
12 A C
9 C F
5 A D
4 C D
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SOURCE DESTINATIO 3rd step
N

34 D F ✅ 22
23 B F
C E
✅
22 C E
✅
15 E F
13 B D 34
12 A C D F
9 C F
5 A D B 23
4 C D
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM
WEIGHT VERTEX VERTEX
SOURCE DESTINATIO 4th step
N
22
34 D F ✅ C E
23 B F
✅
22 C E 1
✅
15 E F 34 5
✅
13 B D
❌ D F
12 A C
9 C F B 23
5 A D
4 C D 5th step NO CHANGES
Prepared by: Maxil S. Urocay MSCS ongoing
 KRUSKAL’S ALGORITHM 6th step
22
WEIGHT VERTEX
SOURCE
VERTEX
DESTINATIO 12
C E
N

34 D F ✅
A
1
23 B F
✅ 34
22 C E
✅ D F5
15 E F
✅
13 B D
❌
B 23
12 A C 7th step NO CHANGES
✅ 8th step NO CHANGES
9 C F ❌
5 A D
9th step NO CHANGES
❌ MAXIMUM =
4 C D ❌ 34+23+22+15+12
Prepared by: Maxil S. Urocay MSCS ongoing
 SHORTEST
PATH
Prepared by: Maxil S. Urocay MSCS ongoing
 SHORTEST PATH 2 common types:
*Dijkstra’s Algorithm
- an algorithm that is
*Bellman Algorithm
designed essentially to
find a path of minimum
19
length between two
12 C E
specified vertices of a
connected weighted A 14
graph. 5
30
- defined as the F
minimum cost route
8 D
from one vertex to
another.
B 34
Prepared by: Maxil S. Urocay MSCS ongoing
-application: map
DIJKSTRA’S
ALGORITHM
Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM
- is designed to find the
shortest path between two
vertices of a graph or from a
19
single source node to all
12 C E
other nodes in a graph with
a non-negative edge
weights. A 14
5
- it’s commonly used for 30
applications such as GPS 8 D F
navigation, network routing,
and other pathfinding B 34
problems. Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM
- was designed and
published by Dr. Edsger
W. Dijkstra, a Dutch
19
Computer Scientist,
12 C E
Software Engineer,
Programmer, Science
Essayist, and Systems A 14
5
Scientist. 30
- Each vertex in this 8 D F
algorithm will have two
properties which is the B 34
visited property and the
Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM
ALGORITHM
*begins at the node we select
(source node), and it
19
examines the graph to find
12 C E
the shortest path between
that node and all the other
nodes in the graph. A 14
5
*the algorithm keep records 30
of the presently 8 D F
acknowledged shortest
distance from each node to B 34
the source node, and it
Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM
ALGORITHM
*once the algorithm has
retrieved the shortest path
between the source and 19
another node, that node is 12 C E
marked as visited and included
in the path. A 14
*procedure continues until all 5
nodes in the graph have been 30
included in the path. In this 8 D F
manner, we have a path
connecting the source to all B 34
other nodes, followingPrepared
theby: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM
Relaxation:
*Visited property signifies that
if (d[u] + c(u,v) < d[v]
the node has been visited, we
d[v] = d[u] + c(u,v)
do not revisit the node, and it is
being marked as visited when 19
the shortest path has been 12 C E
found.
*Path property stores the value A
14
of the current minimum path to 5
the node, implies the shortest 30
way, and will store the final 8 D F
answer for each node.
*Initially we mark all vertices B 34
unvisited and set to infinity
Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S
ALGORITHM
(UNDIRECTED
GRAPH)
Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM STEP 1
∞ ∞
19 Visited: A
12
C E
A 0
0 A 14 5 B ∞
30
∞ F∞ C ∞
8 D
D ∞
B 34 E ∞
∞ F ∞
Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM STEP 2
∞ ∞
19 Visited: A,B
12
C E
A 0
0 A 14 5 B 8
30
∞ F∞ C ∞
8 D
D ∞
B 34 E ∞
∞ F ∞
8 Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM STEP 3
∞ ∞
12 19 Visited: A,B,C
12
C E
A 0
0 A 14 5 B 8
30
∞ F∞ C 12
8 D
D ∞
B 34 E ∞
∞8 F ∞
Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM STEP 4
∞ ∞ 31
12 19 Visited: A,B,C,E
12
C E
A 0
0 A 14 5 B 8
30
∞ F∞ C 12
8 D
D ∞
B 34 E 31
∞8 F ∞
Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM STEP 5
∞ ∞ 31
12 19 Visited: A,B,C,E,F
12
C E
A 0
0 A 14 5 B 8
∞ 30
F ∞ 36 C 12
8 45 D
D 45
B 34 E 31
∞8 F 36
Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM
∞ ∞ 31
12 19 Visited: A,B,C,E,F
12
C E
A 0
0 A 14 5 B 8
∞
F ∞ 36 C 12
8 45 D
D 45
B Total shortest path distance E 31
∞8 = 0+8+12+45+31+36 F 36
= 132 Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S
ALGORITHM
(DIRECTED GRAPH)
Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM STEP 1
∞ ∞
21 Visited: A
3
C E
8 A 0
0 A 56 7 B ∞
33 F C ∞
10
∞ D ∞
B E ∞
∞ 2 79
F ∞
∞ D Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM STEP 2
∞3 ∞
21 Visited: A,C
3
C E
8 A 0
0 A 56 7 B ∞
33 F C 3
10
∞ D ∞
B E ∞
∞ 2 79
F ∞
∞ D Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM STEP 3
∞3 ∞
21 Visited: A,C,B
3
C E
8 A 0
0 A 56 7 B 10
33 F C 3
10
∞ D ∞
∞ B E ∞
2 79
1 F ∞
0 ∞ D Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM STEP 4
∞3 ∞
21 Visited: A,C,B,D
3
C E
8 A 0
0 A 56 7 B 10
33 F C 3
10
∞ D 12
∞ B E ∞
2 79
1 F ∞
0 ∞ D Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM STEP 5
∞3 ∞ 19
21 Visited: A,C,B,D,E
3
C E
8 A 0
0 A 56 7 B 10
33 F C 3
10
∞ D 12
∞ B E 19
2 79
1 F ∞
0 ∞ D Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM STEP 6
∞3 ∞ 19
21 Visited: A,C,B,D,E,F
3
C E
8 A 0
0 A 56 7 B 10
33 F C 3
10
∞ D 12
∞ B 27 E 19
2 79
1 F 27
0 ∞ D Prepared by: Maxil S. Urocay MSCS ongoing
 DIJKSTRA’S ALGORITHM
∞3 ∞ 19
C Visited: A,C,B,D,E,F
3 E
8 A 0
0 A 7
B 10
10 F C 3
∞ 27 D 12
∞ B
2 Total shortest path distanceE 19
1 = 0+10+3+12+19+27 F 27
0 ∞ D = 71
Prepared by: Maxil S. Urocay MSCS ongoing

12
 BELLMAN
FORD
ALGORITHM
Prepared by: Maxil S. Urocay MSCS ongoing
 BELLMAN FORD ALGORITHM
Relaxation:
- an algorithm used to find the
if (d[u] + c(u,v) < d[v]
shortest paths from a single d[v] = d[u] + c(u,v)
source node to all other nodes
in the graph. 19
- useful for graphs that have 12 C E
negative weight edges.
- guarantees the correct A 14
answer even if the weighted
5
30
graph contains the negative 8 D F
weight values.
- relaxing all the edges n-1 B 34
times where n is the number
Prepared by: Maxil S. Urocay MSCS ongoing
 BELLMAN FORD ALGORITHM
- to find the shortest path, first
step is note down all the
edges
19
ALGORITHM 12 C E
*set initial distance to zero for
the source vertex, and set A 14
initial distances to infinity for 5
all other vertices.
30
*for each edges, check if a 8 D F
shorter distance can be
calculated, and update the B 34
distance if the calculated
Prepared by: Maxil S. Urocay MSCS ongoing
 BELLMAN FORD ALGORITHM
*check all edges (step 2) V-1
times. This is as many times
as there are vertices (V), 19
minus one. 12 C E
*Optional: Check for negative
cycles. A 14
Iteration is N-1
5
30
8 D F
Best case O(E)
Average case O(VE) B 34
Worst case O(VE) Prepared by: Maxil S. Urocay MSCS ongoing
 BELLMAN FORD
ALGORITHM
(DIRECTED GRAPH)
Prepared by: Maxil S. Urocay MSCS ongoing
 BELLMAN FORD ALGORITHM 1st Iteration
∞ 10 STEP 1
SEQUENCE:
10 C AC, AB, AD, BE, CD, CE, ED
1 1st
0 A 9 -2
20 A 0
8 ∞ D E B ∞
∞ C 10
B 36
∞ D ∞
E ∞
Prepared by: Maxil S. Urocay MSCS ongoing
 BELLMAN FORD ALGORITHM 1st Iteration
∞ 10 STEP 2
SEQUENCE:
10 C AC, AB, AD, BE, CD, CE, ED
1 1st
0 A 9 -2
20 A 0
8 ∞ D E B 8
∞ C 10
B 36
∞8 D ∞
E ∞
Prepared by: Maxil S. Urocay MSCS ongoing
 BELLMAN FORD ALGORITHM 1st Iteration
∞ 10 STEP 3
SEQUENCE:
10 C AC, AB, AD, BE, CD, CE, ED
1 1st
0 A 9 -2
20 A 0
8 ∞9 D E B 8
∞ C 10
B 36
∞8 D 9
E ∞
Prepared by: Maxil S. Urocay MSCS ongoing
 BELLMAN FORD ALGORITHM 1st Iteration
∞ 10 STEP 4
SEQUENCE:
10 C AC, AB, AD, BE, CD, CE, ED
1 1st
0 A 9 -2
20 A 0
8 ∞9 D E B 8
∞ 44 C 10
B 36
∞8 D 9
E 44
Prepared by: Maxil S. Urocay MSCS ongoing
 BELLMAN FORD ALGORITHM 1st Iteration
∞ 10 STEP 5
SEQUENCE:
10 C AC, AB, AD, BE, CD, CE, ED
1 1st
0 A 9 -2
20 A 0
8 ∞9 D E B 8
8 ∞ 44 C 10
B 36
∞8 D 8
E 44
Prepared by: Maxil S. Urocay MSCS ongoing
 BELLMAN FORD ALGORITHM 1st Iteration
∞ 10 STEP 6
SEQUENCE:
10 C AC, AB, AD, BE, CD, CE, ED
1 1st
0 A 9 -2
20 A 0
8 ∞9 D E B 8
8 ∞ 44 C 10
B 36
11
∞8 D 8
E 11
Prepared by: Maxil S. Urocay MSCS ongoing
 BELLMAN FORD ALGORITHM 1st Iteration
∞ 10 STEP 7
SEQUENCE:
10 C AC, AB, AD, BE, CD, CE, ED
1 1st
0 A 9 -2
20 A 0
8 ∞9 D E B 8
8 31 ∞ 44 C 10
B 36
11
∞8 D 8
E 11
Prepared by: Maxil S. Urocay MSCS ongoing
 BELLMAN FORD ALGORITHM 2nd Iteration
∞ 10 ALL STEP
SEQUENCE:
10 C AC, AB, AD, BE, CD, CE, ED
1 1st 2nd
0 A 9 -2
20 A 0 0
8 ∞9 D E B 8 8
8 31 ∞ 44 C 10 10
B 36
11
∞8 D 8 8
E 11 11
Prepared by: Maxil S. Urocay MSCS ongoing
 BELLMAN FORD ALGORITHM 3rd Iteration
∞ 10 ALL STEP
SEQUENCE:
10 C AC, AB, AD, BE, CD, CE, ED
1 1st 2nd 3rd
0 A 9 -2
20 A 0 0 0
8 ∞9 D E B 8 8 8
8 31 ∞ 44 C 10 10 10
B 36
11
∞8 D 8 8 8
E 11 11 11
Prepared by: Maxil S. Urocay MSCS ongoing
 BELLMAN FORD ALGORITHM 4th Iteration
∞ 10 ALL STEP
SEQUENCE:
10 C AC, AB, AD, BE, CD, CE, ED
1 1st 2nd 3rd 4th
0 A 9 -2
20 A 0 0 0 0
8 ∞9 D E B 8 8 8 8
8 31 ∞ 44 C 10 10 10 10
B 36
11
∞8 D 8 8 8 8
= 0+8+10+8+11 E 11 11 11 11
= 37 Prepared by: Maxil S. Urocay MSCS ongoing
THANK YOU
PRODUCT
OFFERS
Prepared by: Maxil S. Urocay MSCS ongoing
BELLMAN FORD ALGORITHM
46
A 20 F
B
5 16 33 29
C 40 D

Prepared by: Maxil S. Urocay MSCS ongoing

QUIZ 2 FINAL TERM
DIRECTED GRAPH (1st question)
1.1 Get the Adjacency of List
1.2 Insert vertex F (E-F) (update the
adjacency and draw the new graph,
based on 1.1 answer)
1.3 Insert path C to D(update the
adjacency and draw the new graph,
based on 1.1 answer)
Prepared by: Maxil S. Urocay MSCS ongoing
QUIZ 2 FINAL TERM
UNDIRECTED GRAPH (2nd question)
2.1 Get the Adjacency of Matrix
2.2 Remove vertex E (update the
adjacency and draw the new graph,
based on 2.1 answer)
2.3 Remove path C to A (update the
adjacency and draw the new graph,
based on 2.1 answer)
Prepared by: Maxil S. Urocay MSCS ongoing