Graphs
Lecture Flow
1 Pre-requisites 6 Graph representations
2 Definition of Graphs 7 Graphs & Trees
3 Types of Graphs 8 Receiving Inputs on Graph
4 Graph terminologies Problems
5 Checkpoint 9 Practice questions
10 Quote of the day
2
Pre-requisites
● Arrays / Linked list
● Matrices
● Dictionaries
● Time and space complexity analysis
3
What is a Graph?
4
Definition
● A way to represent relationships between objects.
● A collection of nodes that have data and are connected to other
nodes.
5
Example: Friendship Graph
● Nodes or vertices: The objects in
graph
○ These people our case
● Edges: the relation between nodes.
○ The friendship between them
(the lines)
6
What are the types of graphs?
7
Undirected Graph
● Facebook friendship
● If Alice is friends with Bob,
Bob is also friends with alice
8
Directed Graph
● Twitter's "following" relation
● If person A follows person B,
that does not mean that
person B follows person A.
9
Let’s say we want to add a weight parameter which
represents the strength of the friendship.
How can we do that?
10
Unweighted Graph
All edges have the same value.
11
Weighted Graph
Weighted graphs assign numerical
values to edges.
12
Graph Terminologies
13
Terminology: Node / Vertex
● Represent entities (e.g., people, devices).
● Connected to other nodes by edges.
Terminology: Edge
● Connection between two nodes.
● Represented by lines or arrows.
● model relationships in various systems.
15
Terminology: Neighbors
● Two nodes are neighbors or adjacent if there is an edge between
them
16
Terminology: Degree
● Node degree = number of neighbors.
● In directed graphs:
○ Indegree = edges ending at node.
○ Outdegree = edges starting at
node.
17
Terminology: Path
● A path leads from one node to another.
● The length of a path is the number of edges in it.
● Let’s consider the path between node A and node F
18
Terminology: Cycle
A path is a cycle if the first and the last node of the path is the same.
19
Terminology: Connectivity
A graph is connected if there is a path between any two nodes
20
Terminology: Components
The connected parts of a graph are called its components.
21
Terminology: Complete Graph
A complete graph is a graph in which each pair of node is connected by an
edge.
22
Summary
23
Common Terminologies
Node: _____?
Edge: _____?
Path: _____?
Cycle: _____?
Connectivity: _____?
Components: _____?
24
Common Terminologies
Node: represents elements
Edge: is like a line connecting two points or nodes
Path: list of edges that connects nodes
Cycle: if start and end of a path is the same
Connectivity: if there is a path between any two nodes of the graph
Components: connected part of a graph
25
Common Terminologies
Tree: _____?
Neighbours(adjacent): _____?
Degree: _____?
Indegree: _____?
Outdegree: _____?
Complete Graph: _____?
Traverse: _____?
26
Common Terminologies
Tree: is undirected, connected graph consists of n nodes and n-1 edges
Neighbours(adjacent): two nodes are neighbors if there is an edge between them
Degree: is number of neighbours a node has
Indegree: number of edges that end at the node
Outdegree: number of edges that start at the node
Complete Graph: every node has n-1 degree (an edge from every node to every other node)
Traverse: going through the graph using edges
27
Graph Representations
28
Graph Representations
● Adjacency Matrix
● Adjacency List
● Edge List
● Grids as Graphs
29
Graph Representation: Adjacency matrix
30
Advantages and disadvantages of
Adjacency Matrix
31
Graph Representation: Adjacency matrix
Advantages: Disadvantages:
● To represent dense graphs. ● It takes more time to build and
consume more memory
● Edge lookup is fast
(O(N**2) for both cases)
● Finding neighbors of a node is
costly
32
Graph Representation: Adjacency List using List
33
Graph Representation: Adjacency List using Linked List
34
Advantages and Disadvantages of
Adjacency List
35
Graph Representation: Adjacency list
Advantages: Disadvantages:
● It uses less memory ● Edge look up is slow
● Neighbours of a node can be
found pretty fast
● Best for sparse graphs
36
Graph Representation: Edge list
37
Advantages and Disadvantages of
Edge List
38
Graph Representation: Edge list
Advantages: Disadvantages:
● It uses less memory. ● Edge look up is slow
● Easy to represent ● Hard to traverse
39
Graph Representation: Grids as Graph
● Matrix cells = nodes
● Edges between adjacent cells:
○ 4 perpendicular
○ 2 diagonal/antidiagonal.
40
Graph Representation: Grids
- Direction vectors
41
Graph and Tree
42
Tree
● A tree is a connected and acyclic graph.
● A tree has a unique path between any two vertices.
● How many edges does a tree have?
43
Receiving Inputs on Graph Problems
44
Adjacency List Inputs
45
Receiving Inputs: Directed Unweighted Graphs - AL
46
Receiving Inputs: Directed Unweighted Graphs - AL
47
Think of ways to implement this
48
Receiving Inputs: Directed Weighted Graphs - AL
49
Receiving Inputs: Directed Weighted Graphs - AL
50
Receiving Inputs: DWG Complexity Analysis - AL
● Time Complexity: O(n + m)
● Space Complexity: O(2m)
n = number of nodes
m = number of edges
51
Adjacency Matrix Inputs
52
Receiving Inputs: Directed Weighted Graphs - AM
53
Receiving Inputs: DWG Illustration - AM
54
Receiving Inputs: DWG Complexity Analysis - AM
● Time Complexity: O(n^2)
● Space Complexity: O(n^2)
n = number of nodes(matrix length)
55
Receiving Inputs: Undirected Weighted Graphs - AM
56
Receiving Inputs: UDWG Illustration - AM
57
Receiving Inputs: UDWG Complexity Analysis - AM
● Time Complexity: O(n^2)
● Space Complexity: O(n^2)
n = number of nodes (matrix length)
58
Edge List Inputs
59
Receiving Inputs: Directed Weighted Graphs - EL
60
Receiving Inputs: DWG Illustration - EL
61
Receiving Inputs: DWG Complexity Analysis - EL
● Time Complexity: O(n)
● Space Complexity: O(n)
n = number of edges
62
For Multiple Graph Problems
(Generic Templates)
63
Generic template - I
t = int(input()) # number of test cases
for _ in range(t):
# number of nodes and edges
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
Which kind of input is
the graph?
for j in range(m):
u, v = map(int, input().split())
graph[u - 1].append(v - 1)
graph[v - 1].append(u - 1)
# do something with the graph 64
OR
65
Generic template - II
from collections import defaultdict
t = int(input()) # number of test cases
for _ in range(t):
# number of nodes and edges
n, m = map(int, input().split())
graph = defaultdict(list)
for j in range(m):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
66
Tip - To make your inputs faster…
import sys
input = sys.stdin.readline
● This replaces the input() function with sys.stdin.readline() which
is faster.
67
Common Pitfalls
68
Common Pitfalls
● Not considering cycles in the graph.
● Not checking whether the graph is directed or undirected
● Not understanding input format well
● Falling in to infinite loop (because of cycles)
69
Types of Graph Questions
● Graph questions can be classified into different categories based on
the problem requirements.
● Some common types of graph questions include:
● Shortest path: find the shortest path between two vertices.
● Connectivity: determine if there is a path between two vertices.
● Cycle detection: detect cycles in the graph.
● Topological sorting: order the vertices in a directed acyclic graph.
70
Approaches to Solving Graph Problems
There are several approaches to solving graph problems, including:
● Breadth-first search (BFS)
● Depth-first search (DFS)
● Dijkstra's algorithm
● Bellman-Ford algorithm
● Kruskal's algorithm
● Floyd-Warshall algorithm
The choice of algorithm depends on the problem's requirements.
71
What is next?
72
Graph Traversal: DFS and BFS
73
Shortest path: Dijkstra
74
Shortest path: Bellman Ford
75
Topological Sort
76
Exercise problems…
1. Operations on graph
2. Cities and roads
3. From adjacency matrix to adjacency list
4. From adjacency list to adjacency matrix
5. Regular graph
6. Sources and sinks
For more graph representation Problems: Link
77
Quote of The Day
"You can always recognize truth by
its beauty and simplicity."
- Richard P. Feynman
