Data Structures and Algorithms

Trong-Hop Do
University of Information Technology, HCM city

1
Graph

2
set of vertices V = {0,1,2,3,4}
set of edges E = {01, 12, 23, 34, 04, 14, 13}.
Graph representations
The following two are the most commonly used representations of a graph.

1. Adjacency Matrix

2. Adjacency List

There are other representations also like, Incidence Matrix and Incidence List. The
choice of graph representation is situation-specific. It totally depends on the type
of operations to be performed and ease of use.
Adjacency Matrix
• Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the
2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j.
• Adjacency matrix for undirected graph is always symmetric.
• Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge
from vertex i to vertex j with weight w.
Adjacency Matrix
• Pros: Representation is easier to implement and follow. Removing an edge takes O(1) time. Queries like
whether there is an edge from vertex ‘u’ to vertex ‘v’ are efficient and can be done O(1).

• Cons: Consumes more space O(V^2). Even if the graph is sparse(contains less number of edges), it consumes
the same space. Adding a vertex is O(V^2) time.
Adjacency List:
• An array of lists is used. The size of the array is equal to the number of vertices. Let the array be
an array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex. This
representation can also be used to represent a weighted graph. The weights of edges can be
represented as lists of pairs.
Adjacency List:
• Pros: Saves space O(|V|+|E|) . In the worst case, there can be C(V, 2) number of edges in a graph
thus consuming O(V^2) space. Adding a vertex is easier.

• Cons: Queries like whether there is an edge from vertex u to vertex v are not efficient and can be
done O(V).
Adjacency List:
Edge list: 2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Depth First Search
Approach:

• Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node
(selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before
backtracking. So the basic idea is to start from the root or any arbitrary node and mark the node and move to the adjacent
unmarked node and continue this loop until there is no unmarked adjacent node. Then backtrack and check for other unmarked
nodes and traverse them. Finally print the nodes in the path.

Algorithm:

• Create a recursive function that takes the index of node and a visited array.

• Mark the current node as visited and print the node.

• Traverse all the adjacent and unmarked nodes and call the recursive function with index of adjacent node.
Depth First Search
Depth First Search
Depth First Search
Depth First Search
Depth First Search
Depth First Search
Depth First Search
• Time complexity: O(V + E), where V is the number of vertices and E is
the number of edges in the graph.
• Space Complexity: O(V).
• Since, an extra visited array is needed of size V.
Depth First Search (Handling Disconnected Graph )
Solution:
• The above code traverses only the vertices reachable from a given source vertex. All the vertices
may not be reachable from a given vertex as in the case of a Disconnected graph. To do complete
DFS traversal of such graphs, run DFS from all unvisited nodes after a DFS.
• The recursive function remains the same.
Algorithm:
• Create a recursive function that takes the index of node and a visited array.
• Mark the current node as visited and print the node.
• Traverse all the adjacent and unmarked nodes and call the recursive function with index of
adjacent node.
• Run a loop from 0 to number of vertices and check if the node is unvisited in previous DFS then
call the recursive function with current node.
• Implementation:
Breadth First Search
• Breadth First Traversal (or Search) for a graph is similar to Breadth First Traversal of a tree . The
only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node
again. To avoid processing a node more than once, we use a boolean visited array. For simplicity, it
is assumed that all vertices are reachable from the starting vertex.

• A Breadth First Traversal of the following graph is 2, 0, 3, 1.

Breadth First Search
Breadth First Search
Breadth First Search
Step 1: enqueue 1 Step 4: dequeue 3, print 3, enqueue 5
1 2 3 4 5 1 2 3 4 5
Visited: 1 0 0 0 0 Visited: 1 1 1 1 1

Queue: 1 Queue: 4, 5

Print: Print: 1, 2, 3

Step 2: dequeue 1, print 1, enqueue 2 and 3 Step 5: dequeue 4, print 4, enqueue nothing
1 2 3 4 5 1 2 3 4 5
Visited: 1 1 1 0 0 Visited: 1 1 1 1 1

Queue: 2, 3 Queue: 5

Print: 1 Print: 1, 2, 3, 4

Step 3: dequeue 2, print 2, enqueue 4 Step 6: dequeue 5, print 5, enqueue nothing

1 2 3 4 5 1 2 3 4 5
Visited: 1 1 1 1 0 Visited: 1 1 1 1 1

Queue: 3, 4 Queue:

Print: 1, 2 Print: 1, 2, 3, 4, 5
Dijkstra’s shortest path algorithm
Dijkstra’s shortest path algorithm
Uniform cost search