4 | Data Structures & Algorithms 42
UNIT 5: Graphs
5.0 Learning Outcomes
After completing this module, you are expected to:
1. Explain the various shortest path algorithms and their pros/cons.
2. Apply existing data structures in an algorithm
3. Combine existing data structures to get new functionality
5.1 Introduction
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:
Graph Terminology
• adjacent vertices: connected by an edge
• degree (of a vertex): # of adjacent vertices
4 | Data Structures & Algorithms 43
More Graph Terminology
4 | Data Structures & Algorithms 44
4 | Data Structures & Algorithms 45
Connectivity
Let n = #vertices
m = #edges
complete graph - all pairs of vertices are adjacent
4 | Data Structures & Algorithms 46
4 | Data Structures & Algorithms 47
4 | Data Structures & Algorithms 48
5.2 References
Bullinaria, John. Lecture Notes for Data Structures and Algorithms. United Kingdom,
2019.
4 | Data Structures & Algorithms 49
Del Tongo, Luca, et. Al. Data Structures and Algorithms: Annotated Reference with
Examples. 1st Edition. 2008
https://www.geeksforgeeks.org/abstract-data-types/
http://cslibrary.stanford.edu/103/LinkedListBasics
https://algs4.cs.princeton.edu/32bst/
5.3 Acknowledgement
All the figures and information presented in this module were taken from the
references enumerated above. This module is for educational purposes only.
4 | Data Structures & Algorithms 50
SUMMATIVE TEST NO.5
Name:_________________________ Year, Course and Section: _____________
Instruction: Read comprehensively the following questions. Write your answers in a yellow
paper.
1. True or false. Let x be a BST node. The next largest key (successor of x) can be found
by traversing up the tree toward the root until encountering a node with a non-empty
right subtree (possibly x itself); then finding the minimum key in the right subtree
(by following its rightmost path).
2. Reverse a BST. Given a standard BST (where each key is greater than the keys in its
left subtree and smaller than the keys in its right subtree), design a linear-time
algorithm to transform it into a reverse BST (where each key is smaller than the keys
in its left subtree and greater than the keys in its right subtree). The resulting tree
shape should be symmetric to the original one.
3. Level-order traversal reconstruction of a BST. Given a sequence of keys, design a
linear-time algorithm to determine whether it is the level-order traversal of some BST
(and construct the BST itself).
4. Find two swapped keys in a BST. Given a BST in which two keys in two nodes have
been swapped, find the two keys.
Consider the in order traversal a[] of the BST. There are two cases to consider. Suppose there is
only one index p such that a[p] > a[p+1]. Then swap the keys a[p] and a[p+1]. Otherwise, there
are two indices p and q such a[p] > a[p+1] and a[q] > a[q+1]. Let's assume p < q. Then, swap the
keys a[p] and a[q+1].
4 | Data Structures & Algorithms 51
The following table shows the rubric that will be used in evaluating your answer.
Excellent Good Average Needs
improvement
5 3 2 1
Insufficient use of
Strong use of sources -
Some use of sources and/or
including summary, Good use of
Knowledge and sources and sources
quotations, sources and
argumentation very little or misunderstood.
interpretation and some
unclear Unclear or
analysis. argumentation.
argumentation. lacking
Argumentation.
argumentation.
Vocabulary in
this paper is
Vocabulary and Wide and growing limited. There are
Most elements
style vocabulary. Some elements several instances
Variety of sentence achieved.
achieved. of incorrect word
types. choices. There is a
narrow range of
sentence variety.
Main ideas Paper has Use of
Paragraphs and
appropriately divided examples of paragraphs and
punctuation
by paragraphs. Good control. proper use of punctuation
Sentences divided by paragraphs and needs
proper punctuation. punctuation. improvement.
Paper has
Good control.
several errors Several sentences
Paper has some
Spelling and that could and/or ideas are
Precise and consistent errors that do
grammar control. interfere with difficult to
not interfere
understanding understand
with
or affect because of errors.
understanding.
readability.
