+
CS310 – Data Structure
Lecture –10– Graph
2018-2019
+ 2
Objectives
At the end of this topic, you should be able
to:
Analyze
and define memory requirements for
GRAPH ADT
Applyprogramming skills to implement GRAPH
data structures.
For this purpose, we will discuss:
What
is a GRAPH, GRAPH terminology, types of
GRAPH
Learn how to implement a GRAPH as an array,
and linked list February 2, 2025
+ 3
Recommended Readings
Page – 573: Graphs - Chapter 14 - (Data Structure &
Algorithm in Java 6th Edition) By GoodRich
February 2, 2025
+ What is a Graph 4
Airline
routes
Flowcharts
Network
Topologies February 2, 2025
+ 5
What is a Graph
A set of points (Nodes/Vertices) that are connected by lines (Edges)
Graphs also represent the relationships among data items
Mathematically,
G = { V , E };
Where graph (G) is a set of vertices (V) and edges (E)
February 2, 2025
+ 6
Example
A vertex represents an airport and stores the three-letter
airport code
An edge represents a flight route between two airports and
stores the mileage of the route
849 PVD
1843 ORD 2
SFO 14
802
337
743 LGA
2555
1
387 10
HNL 1 99
1233
LAX 1120
DFW
MIA
February 2, 2025
+ 7
Graph Terminology
A graph is connected if there is a path from each vertex to at
least one other vertex
A graph is complete if there is an edge from each vertex to
every other vertex
February 2, 2025
+ 8
Graph Terminology
Subgraph: Subset of the graph’s vertices and the edges
connecting those vertices
Connected component: Subgraph consisting of the set of
vertices reachable from a given vertex. [maximal connected
subgraph]
One vertex is adjacent to another vertex if there is an edge
connecting the two vertices (neighbors)
February 2, 2025
+ 9
Graph Terminology
Path: Sequence of edges that allows one vertex to be reached from
another vertex
A vertex is reachable from another vertex if and only if there is a path between
the two vertices
Simple path: Path that does not pass through the same vertex more than
once BCDB
Cycle: Path that begins and ends at the same vertex
Path Length: Number of edges on the path
February 2, 2025
+ 10
Types of Graph
Three types of Graphs
Undirected Graphs
Directed Graphs
Weighted Graphs
February 2, 2025
+ 11
Undirected graph
A graph in which edges have no direction.
Mathematically, an undirected graph is a pair G = (V, E)
In the given figure,
V = {1, 2, 3, 4, 5, 6}
E = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4, 5}, {4, 6}}
Or
E = {{6, 4}, {4, 3}, {5, 4}, {5, 2}, {5, 1}, {3, 2}, {2, 1}}
February 2, 2025
+ 12
Directed graph (DiGraph)
A graph in which vertices are connected by edges and edges have a direction
associated with them.
Directed graphs are also known as Digraph
Mathematically, a directed graph is a pair G = (V, E)
Example
V = {1, 2, 3, 4, 5, 6}
E = {(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (5, 4), (4, 6)}
Can’t use the reverse paths, because they are not directed in reverse.
February 2, 2025
E = {(6, 4), (4, 3), (4, 5), (5, 2), (5, 1), (3, 2), (2, 1)}
+ 13
Weighted Graph
A weighted graph associates a label (weight) with every edge in the
graph.
Mathematically, a weighted graph is a triple G = (V, E, W)
where (V, E) is a graph (directed or undirected) and W is a weight of the E from V1
to V2. 5
1 7
Example,
V = {1, 2, 3, 4, 5, 6} 8
7
6
E = {(1, 2, 6), (1, 5,7), (2, 3,9), (2, 5,8), (3, 4,7), (5, 4,1), (4, 6,5)}
9
Graph Terminology
Path Cost: the sum of the weight of each February 2, 2025
+ 14
Degree of a Vertex
Undirected Graph: degree of a vertex is the number of edges
connected to it, excepts that a loop at a vertex (cycle edge) is
considered as 2 edges.
Directed Graph:
Indegree(V)=number of edges coming into vertex V
Outdegree(V)=number of edges coming out vertex V
Ref:
https://www.tutorialspoint.com/graph_theory/graph_theory_fundamentals.htm
https://algs4.cs.princeton.edu/42digraph/
February 2, 2025
+ 15
Degree of a Vertex
February 2, 2025
+ 16
Graph ADT implementation
To implement a graph ADT, we need a proper way to store the
vertices and the edges that connect them
Two commonly used representations of graphs:
The Adjacency Matrix
The Adjacency Linked - List
February 2, 2025
+ 17
Adjacency Matrix
Using Matrix to represent graph in the memory
If a graph has N vertices labeled 0, 1, . . . , N – 1:
The adjacency matrix for the graph is a grid G with N rows and N
columns
Cell G[i][ j] = 1 if there’s an edge from vertex i to j
Cell G[i][ j] = 0 if there’s no edge from vertex i to j
February 2, 2025
+ 18
Adjacency Matrix - Example
1 2 3 1 2 3 4
1 0 1 1 0
1 0 0 1
2 1 0 0 0
2 0 1 0 3 1 0 0 0
3 1 1 0 4 0 0 0 0
February 2, 2025
+ 19
Adjacency Matrix - Example
0 1 2
0 0 1 0
1 1 0 1
2 0 0 0
Size of the matrix: 9
Number of edges: 3
0 1 2 3
0 0 1 1 1
1 1 0 1 1
Size of the matrix: 16
2 1 1 0 1 Number of edges: 6
3 1 1 1 0
February 2, 2025
+ 20
Adjacency Linked List
Using Linked-List to represent graph in the memory
If a graph has N vertices labeled 0, 1, . . . , N – 1
The adjacency linked list for the graph is an array of N linked lists
The linked list contains a node for vertices if there is an edge from
vertices
February 2, 2025
+ 21
Adjacency Linked List - Example
February 2, 2025
+ 22
Adjacency Linked List - Example
1 3 1 2 3
2 1
2 2
3 1
3 12
4
February 2, 2025
+ 23
Example
February 2, 2025
+ 24
Example - Adjacency Matrix
February 2, 2025
+ 25
Example - Linked List
February 2, 2025
+ 26
Graph Traversal Extra
Unlike trees, we might stuck in infinite loop when we traverse a
graph since we may have cycles.
Traversing methods:
Breadth-first traversal (which uses a queue)
Depth-first traversal (uses a stack)
Ref:
https://www.youtube.com/watch?v=0u78hx-66Xk
https://www.youtube.com/watch?v=Y40bRyPQQr0
https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm
https://algorithms.tutorialhorizon.com/breadth-first-search-in-disconnected-graph/
February 2, 2025
https://algorithms.tutorialhorizon.com/graph-depth-first-search-using-recursion/
+ 27
Application of Graphs
Graphs serve as models for a variety of applications:
A roadmap
A map of airline routes
A layout of an adventure game world
A schematic of the computers and connections that make up the Internet
The links between pages on the Web
The relationship between students and courses
A diagram of the flow capacities in a communications or transportation
network
February 2, 2025
+ 28
1. Java Implementation
(DiGraph using Arrays)
>> Graph class
February 2, 2025
+ 29
1. Java Implementation
(DiGraph using Arrays)
>> Main class
February 2, 2025
+ 30
1. Java Implementation
(DiGraph using Arrays)
>> Run Sample
February 2, 2025
+ 31
Extra
2. Java Implementation
(Weighted Undirected
Graph LL)
>> LL class
February 2, 2025
+ 32
Extra
(Weighted Undirected
Graph LL)
>> Graph Class
February 2, 2025
+ 33
Extra
(Weighted Undirected
Graph LL)
>> Main class
February 2, 2025
+ 34
Extra
(Weighted Undirected Graph LL)
>> Run Sample
February 2, 2025
+ 35
End of Graph- 11
February 2, 2025
