Graph

(part 1)

CSD202
FPT University

11/16/2025 Data Structures and Algorithms in C++ 1

 Objectives
• Graph Introduction

• Graph definition

• Graph Terminology

• Graph applications

• Graph Representation

• Graph Traversals

• Shortest Paths

– Dijsktra algorithm
– Floyd algorithm
11/16/2025 Data Structures and Algorithms in C++ 2
 Graph Introduction
⚫ What is a Graph?
– A graph is a non-linear data structure consisting of:
• Vertices (Nodes) (unique value)

• Edges (Connections between nodes) (multiple value)

– Formally defined as: G = (V, E)

• where V is a set of vertices

• E is a collections of edges

⚫ This notion of a “graph” should not be confused with bar

charts and function plots, as these kinds of “graphs” are
unrelated to the topic of this chapter.
11/16/2025 Data Structures and Algorithms in C++ 3
 Applications of Graphs

• Scheduling tasks (DAG)

• Social networks (e.g., Facebook graph)
• Google Maps (shortest path, routing)
• Web page ranking (PageRank)
• Network routing

11/16/2025 Data Structures and Algorithms in C++ 4

 Graph Terminology - 1
⚫ Edges in a graph are either directed or undirected.
– An edge (u,v) is said to be directed from u to v if the pair (u,v) is
ordered, with u preceding v.
– An edge (u,v) is said to be undirected if the pair (u,v) is not ordered.
– Undirected edges are sometimes denoted with set notation, as {u,v}.
⚫ If all the edges in a graph are undirected, then we say the
graph is an undirected graph.
⚫ A directed graph, also called a digraph, is a graph whose
edges are all directed.
⚫ A graph that has both directed and undirected edges is often
called a mixed graph.
Note that an undirected or mixed graph can be converted into a directed
graph by replacing every undirected edge (u,v) by the pair of directed edges
(u,v) and (v,u). It is often useful, however, to keep undirected and mixed
graphs represented as they are, for such graphs have several applications.
11/16/2025 Data Structures and Algorithms in C++ 5
 Graph Examples - 1
⚫ A city map can be modeled as a graph
– Vertices are intersections or dead ends
– Edges are stretches of streets without intersections.
– This graph has undirected edges  stretches of two-way streets
– This graph has directed edges  stretches of one-way streets
➔ a graph modeling a city map is a mixed graph.
⚫ A graphs are present in the electrical wiring and
plumbing networks of a building:
– where each connector, fixture, or outlet is viewed as a vertex
– each uninterrupted stretch of wire or pipe is viewed as an edge
➔networks can be modeled as graphs
– The graphs are actually components of much larger graphs, namely
the local power and water distribution networks.
11/16/2025 Data Structures and Algorithms in C++ 6
 Graph Terminology - 2

⚫ End vertices (endpoints): The two vertices joined by an

edge
⚫ If an edge is directed:
– its first endpoint is its origin
– the other is the destination
⚫ Two vertices u and v are said to be adjacent if there is an
edge whose end vertices are u and v.
⚫ An edge is said to be incident to a vertex if the vertex is
one of the edge’s endpoints.
⚫ The outgoing edges of a vertex are the directed edges
whose origin is that vertex.

11/16/2025 Data Structures and Algorithms in C++ 7

 Graph Terminology – 2 (cont.)
⚫ The incoming edges of a vertex are the directed edges
whose destination is that vertex.
⚫ The degree of a vertex v, denoted deg(v), is the number of
incident edges of v.
⚫ If deg(u) = 0 then u is called isolated vertex.
⚫ The in-degree of a vertex v are the number of the incoming
edges of v, and are denoted indeg(v)
⚫ The out-degree of a vertex v are the number of the outgoing
edges of v, and are denoted outdeg(v)

11/16/2025 Data Structures and Algorithms in C++ 8

 Graph Examples
⚫ We can study flight network:
– Vertices are associated with airports
– Edges are associated with flights
– In graph G, the edges a directed graph: The flight has a specific travel
direction
– The endpoints of an edge: The origin and destination of the flight

• Two airports are adjacent in G if

there is a flight that flies
between them.
• An edge e is incident to a vertex
v in G if the flight for e flies to or
from the airport for v.
11/16/2025 Data Structures and Algorithms in C++ 9
 Graph Terminology - 3
⚫ In graph: the group of edges as a collection, not a set
– allowing two undirected edges to have the same end vertices
– for two directed edges to have the same origin and the same
destination → parallel edges or multiple edges.
– A flight network can contain parallel edges.
– A graph containing multiple edges but no loops is called
multigraph.
– Self-loop if its two endpoints coincide: (in city map it is
roundabout)

⚫ Simple graph: graphs do not have parallel edges or self-

loops (the edges of a simple graph are a set of vertex
pairs)
11/16/2025 Data Structures and Algorithms in C++ 10
 Graph Terminology - 4
⚫ A path is a sequence of vertices where each consecutive
pair is connected by an edge

⚫ A cycle is a path that starts and ends at the same

vertex, and all other vertices (and edges) are distinct
along the way

⚫ A directed path is a sequence of vertices in a directed

graph such that:
• Each edge goes from one vertex to the next in the specified
direction.
• The direction of traversal must follow the arrows.

⚫ A directed cycle is a path in a directed graph

11/16/2025 Data Structures and Algorithms in C++ 11
 Graph Terminology - 5
⚫ A undirected graph G is connected if, for any two vertices, there is a
path.

⚫ A directed graph G is strongly connected if for any two vertices u

and v, there is a directed path.

⚫ A directed graph is called weakly connected if replacing all of its

directed edges with undirected edges produces a connected
(undirected) graph.

⚫ A subgraph of a graph G is a graph H whose vertices and edges are

subsets of the vertices and edges of G.

⚫ The connected components is maximal connected subgraphs

11/16/2025 Data Structures and Algorithms in C++ 12

 Graph Terminology - 6
⚫ A forest is a graph without cycles

⚫ A tree is a connected forest, that is, a connected graph

without cycles

⚫ A spanning tree of a graph is a spanning subgraph that is a

tree.

⚫ Note that this definition of a tree is somewhat different from

the one given in previous chapter, as there is not necessarily
a designated root.

11/16/2025 Data Structures and Algorithms in C++ 13

 Graph Terminology - 7
⚫ If the vertex is removed from a graph (along with incident
edges) and there is no way to find a path from a to b,
then the graph is split into two separate subgraphs called
articulation points, or cut-vertices

⚫ If an edge causes a graph to be split into two subgraphs,

it is called a bridge or cut-edge

⚫ Connected subgraphs with no articulation points or

bridges are called blocks
We can use depth first traverse to
check the connectivity of a graph
11/16/2025 Data Structures and Algorithms in C++ 14
 Graph Examples
Single Weighted
Single graph
undirected Directed
graph graph
It is also a simple
graph because it has
no mutiple edges and
no loops

An undirected graph An directed graph An undirected graph

with multiple edges with multiple edges with loops

11/16/2025 Data Structures and Algorithms in C++ 15

 Graph Terminology - 8
• A complete graph is a graph where every pair of vertices is
connected by an edge.
• A simple complete graph on n vertices has n vertices and n(n-1)/2
edges, and is denoted by Kn

• A graph G'=(V', E') is a subgraph of another graph G=(V, E) iff V

11/16/2025 Data Structures and Algorithms in C++ 16

 Summary for Basic Notions on Graph
• Vertex • Connected,
• Edge, (directed, undirected • Strongly connected,
edge), (directed, undirected • Weakly connected,
graph), • Subgraph,
• Adjacent vertices, • Spanning subgraph,
• Incident edge, • Forest,
• Degree, • Tree,
• Isolated vertex, • Spanning tree,
• Parallel edge or multiple edge, • Complete graph,
• Loop, • Simple complete graph,
• Simple graph, • Cut-vertex (articulation point),
• Multigraph, • Bridge(cut-edge),
• Path, • Block,...
• Simple path,
• Cycle,
11/16/2025 Data Structures and Algorithms in C++ 17
 Graph applications
• Electronic circuits
• Transportation
networks
• Computer networks
• Database
– Entity-relationship diagram

11/16/2025 Data Structures and Algorithms in C++ 18

 Graph Representation – 1
(Adjacency list)

11/16/2025 Data Structures and Algorithms in C++ 19

 Graph Representation – 2
(Adjacency matrix)

Graph represented by an adjacency matrix

11/16/2025 Data Structures and Algorithms in C++ 20

 Graph Representation – 3
(Incident matrix)
A vertex is said to be incident to an edge if the edge is connected to the vertex.

Graph represented by incident matrix

11/16/2025 Data Structures and Algorithms in C++ 21

 Graph Traversals
Breadth-first Search (BFS)
BFS is a graph traversal algorithm
that explores all vertices of a graph
layer by layer, starting from a
selected source node.

How it works
• Start at the source node.
• Visit all immediate neighbors (level 1).
• Then visit all neighbors of neighbors (level 2), and so on.
• Use a queue (FIFO) to keep track of the next node to visit.
• Maintain a visited array to avoid cycles and repeated visits.

11/16/2025 Data Structures and Algorithms in C++ 22

 Algorithm Steps
1. Initialize an empty queue and mark the source node as
visited.
2. Enqueue the source node.
3. While the queue is not empty:
– Dequeue a node u.
– Visit u.
– Enqueue all unvisited neighbors of u.

11/16/2025 Data Structures and Algorithms in C++ 23

 Pseudocode
BFS(Graph, start){
create queue Q
mark start as visited and enqueue it into Q
while Q is not empty{
current = [Link]()
visit(current)
for each neighbor in Graph[current]
if (neighbor is not visited){
mark as visited
[Link](neighbor)
}
}
}
11/16/2025 Data Structures and Algorithms in C++ 24
 Source code example

11/16/2025 Data Structures and Algorithms in C++ 25

 Applications

⚫ Finding shortest path in unweighted graphs

⚫ Crawling web pages
⚫ Peer-to-peer networks
⚫ GPS navigation systems
⚫ Network broadcasting

11/16/2025 Data Structures and Algorithms in C++ 26

 Depth-first Traversal
⚫ Depth-First Search (DFS) is a graph traversal algorithm that
explores as far as possible along each branch before
backtracking.
How DFS Works
1. Start at a source node.
2. Mark it as visited.
3. Recursively visit all unvisited neighbors.
4. Use a stack (explicit or via recursion) to manage traversal.

An example of application of the depthFirstSearch() algorithm to a graph

11/16/2025 Data Structures and Algorithms in C++ 27
 DFS Algorithm – Pseudocode

Using recursion Using stack

DFS(node){ DFS_iterative(start){
mark node as visited create empty stack
visit(node) push start onto stack
for neighbor in [Link]{ while stack is not empty{
if neighbor is not visited{ node = [Link]()
DFS(neighbor) if node is not visited{
} visit(node)
} push all unvisited neighbors
} onto stack
}
}
}

11/16/2025 Data Structures and Algorithms in C++ 28

 DFS in C++ Example
⚫ Using recursion

11/16/2025 Data Structures and Algorithms in C++ 29

 DFS in C++ Example
⚫ Using stack:

11/16/2025 Data Structures and Algorithms in C++ 30

 Applications of DFS
⚫ Topological Sorting (DAGs)
⚫ Detecting Cycles in Graphs
⚫ Finding Connected Components
⚫ Solving Mazes or Puzzles
⚫ Strongly Connected Components (Tarjan/Kosaraju)

11/16/2025 Data Structures and Algorithms in C++ 31

 DFS vs BFS

Feature DFS BFS

Strategy Depth first Level by level
Data Structure Stack / Recursion Queue
Finds shortest
(not guaranteed) (in unweighted graph)
path?
Shortest path,
Use case Puzzle, backtracking
networking

11/16/2025 Data Structures and Algorithms in C++ 32

 Shortest Path problem

• The problem: find the shortest path between a pair

of vertices of a graph
• The graph: may contain negative edges but no
negative cycles
• A representation: a weighted matrix where
W(i,j) = 0 if i=j.
W(i,j) =  if there is no edge between i and j.
W(i,j) = weight of the edge (i,j)

11/16/2025 Data Structures and Algorithms in C++ 33

 Dijkstra’s Algorithm
⚫ Dijkstra's algorithm finds the shortest path from a source
vertex to all other vertices in a graph with non-negative
weights.
– Works for directed/undirected graphs

– Does not work with negative weights

Use Cases

GPS & Maps: Fastest route

Network Routing Protocols (like OSPF)

Pathfinding in games

Task scheduling with priorities

11/16/2025 Data Structures and Algorithms in C++ 34

 Algorithm Steps

⚫ Initialize all distances as ∞, except the source (0)

⚫ Use a priority queue to pick the vertex with the
minimum distance
⚫ For each neighbor, relax the edge:
⚫ If dist[u] + weight < dist[v] → update dist[v]
⚫ Repeat until the queue is empty

11/16/2025 Data Structures and Algorithms in C++ 35

 Dijkstra's Algorithm example - 1

A(1), B(2), C(3), D(4), E(5), F(6)

Dijkstra’s algorithm keeps two sets of vertices: int [][] b = {

S Vertices whose shortest paths have already { 0, 7, 9, 99, 99, 14},
been determined { 7, 0, 10, 15, 99, 99},
V-S Remainder { 9, 10, 0, 11, 99, 2},
{99, 15, 11, 0, 6, 99},
Also {99, 99, 99, 6, 0, 9},
d Best estimates of shortest path to each vertex {14, 99, 2, 99, 9, 0}
p Predecessors for each vertex };

11/16/2025 Data Structures and Algorithms in C++ 36

 Dijkstra's Algorithm example - 2
The complexity of Dijkstra's
algorithm is O(|V|2). This
algorithm is not general
enough in that it may fail
when negative weights are
used in graphs.

11/16/2025 Data Structures and Algorithms in C++ 37

 C++ Code Implementation

11/16/2025 Data Structures and Algorithms in C++ 38

 Time and Space Complexity

Item Value
Time Complexity O((V + E) log V)
Space Complexity O(V) for distances
Data Structure Min-Heap (priority_queue)

Notes & Limitations

• Only works with non-negative weights
• For negative weights, use Bellman-Ford Algorithm
• Optimal for sparse graphs using min-heap

11/16/2025 Data Structures and Algorithms in C++ 39

 Floyd Algorithm
All pairs shortest path
Floyd-Warshall is an algorithm to find the shortest paths
between all pairs of vertices in a weighted graph.

• Works with directed/undirected graphs

• Supports negative edge weights

• No negative cycles allowed

11/16/2025 Data Structures and Algorithms in C++ 40

 Floyd Algorithm

⚫Key Features
– Uses Dynamic Programming
– Works on adjacency matrix representation
– Time Complexity: O(V³)
– Space Complexity: O(V²)

⚫Use Cases
– Traffic or routing networks (shortest distance between all locations)
– Finding transitive closure of a graph
– Network reliability & delay analysis

11/16/2025 Data Structures and Algorithms in C++ 41

 Algorithm Overview
⚫ For each pair of vertices (i, j), check if an intermediate vertex
k improves the shortest path:
for each k:
for each i:
for each j:
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j];

11/16/2025 Data Structures and Algorithms in C++ 42

 Floyd-Warshall Algorithm

Detecting Negative Cycles

for (int i = 0; i < V; i++) {
if (dist[i][i] < 0) {
cout << "Negative cycle detected\n";
break;
}
}
11/16/2025 Data Structures and Algorithms in C++ 43
 Floyd Algorithm example

The final distance matrix and P

The values in parenthesis are the non zero P values.

11/16/2025 Data Structures and Algorithms in C++ 44

 Time and Space Complexity
Property Value
Time Complexity O(V³)
Space Complexity O(V²)
Directed/Weighted, supports negative
Graph Type
edges

Summary
• Simple to implement
• Solves all-pairs shortest path
• Not suitable for large graphs (due to O(V³))
• Cannot handle negative cycles
11/16/2025 Data Structures and Algorithms in C++ 45
 Summary
• Graph Introduction

• Graph definition

• Graph Terminology

• Graph applications

• Graph Representation

• Graph Traversals

• Shortest Paths

• Dijsktra algorithm

• Floyd algorithm
11/16/2025 Data Structures and Algorithms in C++ 46