12.

Graphs
Data Structures and Algorithms EEE2020-01
Prof. Jongyoo Kim
 Graph Definition
▪ A graph is a non-linear data structure consisting of vertices (nodes) and edges
(connections).
▪ A graph 𝐺 is formally defined by a pair of sets: 𝐺 = 𝑉, 𝐸
▪ 𝑽 is a set of vertices: G
• A vertex or “node” is a data entity. H
• 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹, 𝐺, 𝐻
▪ 𝑬 is a set of edges: F
• An edge is a connection between two vertices.
• 𝐸 = { 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐷 , 𝐴, 𝐻 , 𝐶, 𝐵 , A
𝐵, 𝐷 , 𝐷, 𝐸 , 𝐷, 𝐹 , 𝐹, 𝐺 , 𝐺, 𝐻 }
D C

B
E

Multimedia AI Lab. 2
 Applications
❑ Transportation Networks:
▪ Airline Maps: Vertices are airports, edges are flight paths.
▪ Traffic Systems: Vertices are addresses/intersections,
edges are streets.

❑ Modeling Relationships:
▪ Social Media Graphs: Vertices are user accounts, edges
are follower relationships.
▪ Code Bases: Vertices are classes, edges represent usage or
dependency.

❑ Information Systems & Ranking:

▪ Web Page Ranking: Vertices are web pages, edges are
hyperlinks.
▪ Wikipedia: Vertices are articles, edges are links between
articles.

Multimedia AI Lab. 3
 Graph Terminologies
▪ A graph is defined by 𝐺 = 𝑉, 𝐸 .
• 𝑉 is a set of vertices. G
• 𝐸 is a set of edges. H
▪ Neighbor or Adjacent
• Two vertices 𝑢 and 𝑣 are neighbors (or adjacent) if they are F
directly connected by an edge.
• Formal notation: 𝑢, 𝑣 ∈ 𝐸 A
• (meaning an edge exists between u and v).
D C
• 𝑁 𝑣 denotes the neighborhood of a vertex v
▪ Order of a graph B
• The number of vertices, denoted as 𝑉 . E

▪ Size of a graph
• The number of edges, denoted as 𝐸 .

Multimedia AI Lab. 4
 Graph Terminologies
▪ Path:
• A sequence of edges that can be followed from a starting vertex a to reach a target vertex
b.
• Can be represented as a sequence of visited vertices (e.g., V,X,Z) or edges taken (e.g.,
(V,X),(X,Z)).
• Example: one path from V to Z: {b, h} or {V, X, Z}

V
▪ Path length: The number of edges contained in the path. a b

U d X Z
h
c e
W g
f
Y

Multimedia AI Lab. 5
 Graph Terminologies
▪ Reachable:
• Vertex a is reachable from vertex b if a path exists from b to a. a b
▪ Connected Graph:
• A graph is connected if every vertex is reachable from every other vertex. d
c
▪ Disconnected Graph:
e
• A graph where at least two vertices exist without a path connecting them.
▪ Complete Graph:
• A graph in which every vertex has a direct edge to every other vertex.
a b

c d

Multimedia AI Lab. 6
 Graph Terminologies
▪ Cycle: A path that begins and ends at the same node.
• example: {V, X, Y, W, U, V}.
• example: {U, W, V, U}.
V
a b
▪ Acyclic graph: A graph that does not contain any cycles. d
U X Z
h
e
▪ Loop: An edge that connects a node directly to itself. c
W g
• Many graphs do not allow loops..
f
Y

Multimedia AI Lab. 7
 Graph Terminologies
▪ Weight: A cost or value associated with a given edge.
• Weighted Graphs: Edges have associated weights (e.g., distance, cost, time).
• Unweighted Graphs: Edges have no explicit weights; all connections are considered
equal (often implicitly weighted as 0 or 1).
• Most graphs do not allow negative weights.
• Example: An airline flight graph weighted by miles between cities.

PVD
ORD
SFO
LGA

HNL
LAX
DFW
MIA
Multimedia AI Lab. 8
 Types of Graph
▪ Undirected graph
• Edges do not have any direction.
• Nodes are unordered pairs in the definition of every edge.
• Symmetry: 𝑢, 𝑣 ∊ 𝐸, then 𝑣, 𝑢 ∊ 𝐸
• Degree of a Vertex: The number of edges connected to that vertex.

▪ Directed graphs
• Edges have a specific direction.
• Nodes are ordered pairs in the definition of every edge.
• Asymmetry: 𝑢, 𝑣 ∊ 𝐸, it does not necessarily imply that 𝑣, 𝑢 ∊ 𝐸
• In-Degree of a Vertex: The number of edges pointing towards the vertex.
• Out-Degree of a Vertex: The number of edges pointing away from the vertex.

Multimedia AI Lab. 9
 Types of Graph
▪ Unweighted graph
• The edges between vertices have no associated values or weights
• All connections are considered equal
• Only the presence or absence of an edge matters
• Applications:
• Social networks, Web page links, Simple connectivity problems
▪ Weighted graphs
• Each edge has an associated value (weight)
• Weights can represent various metrics like distance, cost, time, etc.
• The weight values are considered when processing the graph
• Applications:
• Road networks (distances between cities), Network routing (connection
costs), Flow networks (capacity)

Multimedia AI Lab. 10
 Representation of Graph Data Structure
▪ Graphs are represented in data structures to efficiently store and manipulate their
relationships. The two most common representations are:
• Adjacency Matrix
• Adjacency List

1 v1 → v2
2 v2 → v4
3 v3 → v2 → v4
4 v4
5 v5 → v3 → v4

Multimedia AI Lab. 11
 Adjacency Matrix
▪ A square matrix used to represent a graph by storing the relationships between nodes in their
respective cells.
▪ Unweighted graph
• A[i][i] = 1 if there is an edge between vertex i and vertex j.
• A[i][i] = 0 if there is NO edge between vertex i and vertex j.
▪ Required space: 𝑂 𝑉 2

Multimedia AI Lab. 12
 Adjacency Matrix
▪ A square matrix used to represent a graph by storing the relationships between nodes in their
respective cells.
▪ Weighted graph
• A[i][j] = INF if there is no edge between vertex i and vertex j.
• A[i][j] = w if there is an edge between vertex i and vertex j with weight w.
▪ Required space: 𝑂 𝑉 2

Multimedia AI Lab. 13
 Graph Density
▪ Dense Graph 1 4

• A graph with a relatively large number of edges.

• The number of edges 𝐸 ≈ 𝑂 𝑉 2
• A complete graph is a dense graph where every vertex is 2 3
connected to every other vertex..

▪ Sparse Graph
5
• A graph with a relatively small number of edges. 1

• The number of edges 𝐸 ≈ 𝑂 𝑉

• An Adjacency Matrix can be inefficient for sparse graphs 4
due to wasted space. 2

Multimedia AI Lab. 14
 Adjacency List
▪ A graph is represented as a collection of linked lists or arrays, where each vertex has a list of
its adjacent vertices.
▪ Structure: Each entry in the list corresponds to a vertex, and its associated list contains all
vertices directly connected to it.
▪ Adaptability: Can easily represent directed, undirected, and weighted graphs by storing
additional information (e.g., weight) in the list nodes.
▪ Required space: 𝑂 𝑉 + 𝐸
1 v1 → v2

v2 2 v2 → v4
v3
v1 3 v3 → v2 → v4
4 v4
v4
v5 5 v5 → v3 → v4
Multimedia AI Lab. 15
 Adjacency List
❑ Undirected graph
▪ Required space: 𝑂 𝑉 + 𝐸

1 v1 → v2
2 v2 → v1 → v3 → v4
v2 v3
v1 3 v3 → v2 → v4 → v5
4 v4 → v2 → v3 → v5
v4 5 v5 → v3 → v4
v5

Multimedia AI Lab. 16
 Adjacency List
❑ Weighted graph
▪ Required space: 𝑂 𝑉 + 𝐸

5 v2 2
v3
v1
4
3 7
v4
8 v5

Multimedia AI Lab. 17
 Pros and Cons

Feature Adjacency Matrix Adjacency List

𝑂 deg 𝑢 or 𝑂 𝑉 in worst case (linear

Edge Check 𝑂 1 (direct lookup)
scan of list)

Finding Neighbors 𝑂 𝑉 (iterate row/column) 𝑂 deg 𝑢 (traverse list for vertex u)

𝑂 𝑉 + 𝐸 (proportional to vertices and

Space Efficiency 𝑂 𝑉 2 (always, regardless of edges)
edges)

Dense graphs (many edges), frequent Sparse graphs (few edges), frequent
Best Use Case
edge checks neighbor queries

Multimedia AI Lab. 18
 Problems on Graphs
▪ Graphs are fundamental for modeling and solving a wide range of real-world problems. Common
problems include:
▪ Connectivity:
• Is the graph fully connected?
• Can an edge be removed while maintaining full connectivity?
• Is one vertex reachable from another?
▪ Pathfinding:
• What is the cheapest cost path from vertex v to vertex w? (e.g., Shortest Path algorithms)
• Which vertices are reachable from a given vertex v? (Transitive Closure)
▪ Cycles:
• Does a cycle exist that passes through all vertices? (Hamiltonian Cycle)
▪ Spanning Structures:
• Is there a tree that links all vertices? (Spanning Tree)
• What is the minimum spanning tree?
▪ These problems are often mapped from real-world scenarios (e.g., network routing, logistics,
social influence) to graph problems, allowing graph algorithms to provide solutions.

Multimedia AI Lab. 19
 Traversal algorithms
▪ Graph traversal involves visiting all vertices in a graph in a systematic manner. The two basic
algorithms are:
▪ Depth-first-search (DFS)
• After visiting node v, DFS strategy proceeds along a path from v as deeply into the graph as
possible before backing up
▪ Breadth-first-search (BFS)
• After visiting node v, BFS strategy visits every node adjacent to v before visiting any other
nodes

Multimedia AI Lab. 20
 Recap: Breadth First Search in Tree
▪ Level-Order Traversal:
• Visit nodes level by level from left to right using a queue.
• Use: Finding shortest paths, serialization.

A Level 0

B C Level 1

D E F F Level 2

Multimedia AI Lab. 21
 Breadth First Search
▪ BFS systematically explores a graph by visiting all vertices at a given "level" (distance from
the starting node) before moving on to the next level. It is analogous to a level-order traversal
in a tree.
▪ Strategy: From a given node v, it first visits v itself, then all nodes directly adjacent to v, then
all nodes adjacent to those, and so on.
▪ Implementation: Typically implemented using a queue data structure.

▪ Applications:
• Finding the shortest path in an unweighted graph (finds the path with the least number of
edges).
• Detecting cycles in a graph.
• Topological sorting.

Multimedia AI Lab. 22
 Breadth First Search
❑ BFS Algorithm Steps:
▪ Initialize a queue and a visited set (or array) to keep track of visited nodes.
▪ Add the starting node to the queue and mark it as visited.
▪ While the queue is not empty:
• Dequeue a node and denote it as current.
• Process the current node (e.g., print it, perform an operation).
• Explore all current node's unvisited neighbors:
• Enqueue each unvisited neighbor.
• Mark each enqueued neighbor as visited.
▪ The traversal finishes when the queue is empty, indicating all reachable nodes have been
visited.

Multimedia AI Lab. 23
 Breadth First Search
▪ Initialize a queue and visited.

Visited Queue

1 3 0 F

1 F
0 2 F
Start node
3 F
2 4
4 F

Multimedia AI Lab. 24
 Breadth First Search
▪ Add the start node to the queue.
▪ Mark the start node as visited.

Visited Queue

1 3 0 T 0

1 F
0 2 F

3 F
2 4
4 F

Multimedia AI Lab. 25
 Breadth First Search
▪ Dequeue the node from and denote as current.
▪ Explore all the current node’s neighbors.
• Enqueue them if not visited and mark them as visited.

Visited Queue

1 3 0 T 1

1 T 2
0 2 T
Current
3 F
2 4
4 F

Multimedia AI Lab. 26
 Breadth First Search
▪ Dequeue the node from and denote as current.
▪ Explore all the current node’s neighbors.
• Enqueue them if not visited and mark them as visited.

Visited Queue

1 3 0 T 2

Current 1 T 3
0 2 T

3 T
2 4
4 F

Multimedia AI Lab. 27
 Breadth First Search
▪ Dequeue the node from and denote as current.
▪ Explore all the current node’s neighbors.
• Enqueue them if not visited and mark them as visited.

Visited Queue

1 3 0 T 3

1 T 4
0 2 T

3 T
2 4
4 T
Current
Multimedia AI Lab. 28
 Breadth First Search
▪ Dequeue the node from and denote as current.
▪ Explore all the current node’s neighbors.
• Enqueue them if not visited and mark them as visited.

Visited Queue

1 3 0 T 4

Current 1 T
0 2 T

3 T
2 4
4 T

Multimedia AI Lab. 29
 Breadth First Search
▪ Dequeue the node from and denote as current.
▪ Explore all the current node’s neighbors.
• Enqueue them if not visited and mark them as visited.

Visited Queue

1 3 0 T

1 T
0 2 T

3 T
2 4
4 T
Current
Multimedia AI Lab. 30
 Breadth First Search
▪ All nodes are visited.
▪ Finished.

Visited Queue

1 3 0 T

1 T
0 2 T

3 T
2 4
4 T

Multimedia AI Lab. 31
Breadth First Search

Multimedia AI Lab. 32
 BFS Analysis
❑ Time Complexity:
▪ 𝑂 𝑉 + 𝐸
▪ Each vertex is visited at most once (𝑂 𝑉 ).
▪ Each edge is examined at most twice (once for each direction in an undirected graph, once
for a directed graph) (𝑂 𝐸 ).
▪ Assumes an adjacency list representation.

❑ Auxiliary Space:
▪ 𝑂 𝑉
▪ (for the queue and visited set).

Multimedia AI Lab. 33
 Recap: Depth First Search in Tree
A
▪ Pre-order Traversal:
1. Visit the root node.
2. Traverse the left subtree. B C
3. Traverse the right subtree.
▪ In-order Traversal:
A
1. Traverse the left subtree.
2. Visit the root node.
3. Traverse the right subtree. B C
▪ Post-order Traversal:
1. Traverse the left subtree.
A
2. Traverse the right subtree.
3. Visit the root node.
B C

Multimedia AI Lab. 34
 Depth First Search
▪ DFS explores a graph by going as "deep" as possible along each branch before backtracking.
It is similar to a pre-order traversal in a tree.
▪ Strategy: After visiting node v, DFS proceeds along a path from v as deeply into the graph as
possible before backing up to explore other branches.
▪ Implementation: Typically implemented using a stack data structure or recursion.

▪ Applications:
• Searching for solutions in artificial intelligence (e.g., game trees).
• Web crawling.
• Detecting cycles in a graph.
• Finding connected components.
• Topological sorting.

Multimedia AI Lab. 35
 Depth First Search
❑ DFS Algorithm Steps (using a stack):
▪ Initialize a stack and a visited set (or array).
▪ Push the starting node onto the stack and mark it as visited.
▪ While the stack is not empty:
• Pop a node from the stack and denote it as current.
• Process the current node.
• Explore all current node's unvisited neighbors:
• Push each unvisited neighbor onto the stack.
• Mark each pushed neighbor as visited.
▪ The traversal finishes when the stack is empty.

Multimedia AI Lab. 36
 Depth First Search
▪ Initialize a stack and visited.

Visited Stack

0 1 0 F

Start node 1 F

2 2 F

3 F
3 4
4 F

Multimedia AI Lab. 37
 Depth First Search
▪ Add the start node to the stack.
▪ Mark the start node as visited and set its previous node to None.

Visited Stack

0 1 0 T

1 F

2 2 F

3 F
3 4
4 F 0

Multimedia AI Lab. 38
 Depth First Search
▪ Pop the node from and denote as current.
▪ Explore all the current node’s neighbors.
• Push them if not visited and mark them as visited.

Visited Stack

0 1 0 T

Current 1 T

2 2 T 3

3 T 2
3 4
4 F 1

Multimedia AI Lab. 39
 Depth First Search
▪ Pop the node from and denote as current.
▪ Explore all the current node’s neighbors.
• Push them if not visited and mark them as visited.

Visited Stack

0 1 0 T

1 T

2 2 T

3 T 2
3 4
4 F 1
Current
Multimedia AI Lab. 40
 Depth First Search
▪ Pop the node from and denote as current.
▪ Explore all the current node’s neighbors.
• Push them if not visited and mark them as visited.

Visited Stack

0 1 0 T

Current 1 T

2 2 T

3 T 4
3 4
4 T 1

Multimedia AI Lab. 41
 Depth First Search
▪ Pop the node from and denote as current.
▪ Explore all the current node’s neighbors.
• Push them if not visited and mark them as visited.

Visited Stack

0 1 0 T

1 T

2 2 T

3 T
3 4
4 T 1
Current
Multimedia AI Lab. 42
 Depth First Search
▪ Pop the node from and denote as current.
▪ Explore all the current node’s neighbors.
• Push them if not visited and mark them as visited.

Visited Stack

0 1 0 T

Current 1 T

2 2 T

3 T
3 4
4 T

Multimedia AI Lab. 43
 Depth First Search
▪ All nodes are visited.
▪ Finished.

Visited Stack

0 1 0 T

1 T

2 2 T

3 T
3 4
4 T

Multimedia AI Lab. 44
 Depth First Search Analysis
❑ Time Complexity:
▪ 𝑂 𝑉 + 𝐸
▪ Each vertex is visited at most once (𝑂 𝑉 ).
▪ Each edge is examined at most twice (once for each direction in an undirected graph, once
for a directed graph) (𝑂 𝐸 ).
▪ Assumes an adjacency list representation.

❑ Auxiliary Space:
▪ 𝑂 𝑉

Multimedia AI Lab. 45
Depth First Search

Multimedia AI Lab. 46
Depth First Search using recursion

Multimedia AI Lab. 47
 Spanning Tree
▪ A spanning tree of an undirected graph 𝐺 is a subgraph that is a
tree and connects all the vertices of 𝐺.

▪ Properties:
• It connects all vertices of the original graph.
• It contains the minimum possible number of edges to
connect all vertices without forming any cycles.
• A graph may have more than one spanning tree.
▪ Construction:
• Both BFS and DFS can be used to find a spanning tree of a
connected graph.
• Pathfinding algorithms such as Dijkstra's algorithm and A*
algorithm.
All possible spaccning trees

Multimedia AI Lab. 48
 Spanning Tree
❑ BFS

Multimedia AI Lab. 49
 Spanning Tree
❑ DFS

Multimedia AI Lab. 50
 Advanced Graph Problems
▪ Beyond basic traversal, graphs are used to solve more complex problems:
▪ Shortest Distance:
• Algorithms like Dijkstra's or Bellman-Ford can find the shortest path (minimum total
weight) between two nodes in a weighted graph. This involves recording the cumulative
distance from the starting node.
▪ Finding Paths:
• To reconstruct the actual path, algorithms typically record the previously visited node for
each vertex as the search progresses. This "parent" information allows backtracking from
the destination to the source.

Multimedia AI Lab. 51