Ugenz Academy/Tutorial

Graphs

19 min read3,784 words

Reading progress

Keep learning

Graphs

A Graph is a non-linear data structure used to represent relationships or connections between objects.

If a tree represents a hierarchy:

A / \ B C

a graph can represent much more general relationships:

A -------- B | \ | | \ | C -------- D \ / \-------E

There is no requirement that there be a single root, and cycles are allowed.

Graph = Vertices (nodes) + Edges (connections)

1. What Is a Graph?

A graph is mathematically represented as:

G = (V, E)

where:

  • V = set of vertices
  • E = set of edges

For example:

Vertices: A, B, C, D Edges: A-B A-C B-D C-D

Graph:

A / \ B C \ / D

Here:

V = {A, B, C, D} E = {(A,B), (A,C), (B,D), (C,D)}

2. Real-Life Examples

Graphs are everywhere.

Social Network

Alice ---- Bob | | | | Charlie --- David
  • Person = vertex
  • Friendship = edge

Google Maps

City A ---- City B | | City C ---- City D
  • City = vertex
  • Road = edge

Computer Network

PC1 ---- Router ---- PC2 | PC3
  • Device = vertex
  • Connection = edge

Website Links

Page A → Page B ↓ ↓ Page C → Page D
  • Web page = vertex
  • Link = edge

3. Graph Terminology ⭐

Before algorithms, you need to understand the vocabulary.

Vertex / Node

A point in the graph.

A

Here A is a vertex.

Edge

A connection between two vertices.

A ----- B

A-B is an edge.

Adjacent Vertices

Two vertices connected directly by an edge.

A ----- B

A and B are adjacent.

Degree

The number of edges connected to a vertex.

Example:

B | A ---- C ---- D | E

Degree of C:

degree(C) = 4

because it connects to:

A, B, D, E

4. Directed Graph

In a directed graph, edges have a direction.

A → B

means:

A can go to B

but not necessarily:

B → A

Example:

A → B → C ↓ ↓ D ←-----E

This is called a:

Directed Graph / Digraph

5. Undirected Graph

In an undirected graph, connections have no direction.

A ----- B

means:

A is connected to B B is connected to A

Example:

A / \ B---C

6. Directed vs Undirected

FeatureUndirectedDirected
DirectionNoYes
EdgeA-BA → B
RelationshipUsually mutualCan be one-way
ExampleFriendshipInstagram follow

For example:

Friendship

Alice ----- Bob

Usually mutual.

Following

Alice → Bob

Alice follows Bob, but Bob doesn't necessarily follow Alice.

7. Weighted Graph ⭐

An edge can have a weight.

Example:

A ----5---- B \ / 2 3 \ / C

Weights could represent:

  • Distance
  • Cost
  • Time
  • Network latency
  • Price

For example:

Kathmandu ----200km---- Pokhara

The 200 is the edge weight.

8. Unweighted Graph

If edges don't have weights:

A ----- B | | C

we simply care about whether a connection exists.

9. Weighted vs Unweighted

Unweighted

A ----- B

Question:

Are A and B connected?

Weighted

A ---10--- B

Question:

What is the cost/distance between A and B?

10. Graph With Self-Loop

An edge can sometimes connect a vertex to itself.

↺ A

This is called a:

Self-loop

11. Parallel Edges

Sometimes two vertices can have multiple edges between them.

===== A -------- B =====

This is called:

Parallel edges / Multiple edges

Whether these are allowed depends on the graph type/model.

12. Simple Graph

A simple graph generally has:

  • No self-loops
  • No parallel/multiple edges

Example:

A ----- B | | | | C ----- D

13. Path ⭐

A path is a sequence of vertices connected by edges.

Example:

A ----- B ----- C ----- D

Path from A to D:

A → B → C → D

The path contains:

4 vertices 3 edges

14. Path Length

The number of edges in a path.

A → B → C → D

Number of edges:

3

Therefore:

Path length = 3

15. Cycle ⭐

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

Example:

A / \ B---C

Cycle:

A → B → C → A

Graphs can contain cycles.

Trees cannot contain cycles.

16. Connected Graph

An undirected graph is connected if every vertex can be reached from every other vertex.

Example:

A ----- B | | C ----- D

Every vertex is reachable.

So it is connected.

17. Disconnected Graph

Example:

A ----- B C ----- D

There is no path between:

A/B

and:

C/D

Therefore, the graph is disconnected.

18. Connected Components

Each separate connected part is called a connected component.

Example:

Component 1: A ----- B | | C ----- D Component 2: E ----- F

There are:

2 connected components

19. Tree vs Graph

You already learned trees, so this distinction is important.

Tree

A tree is a special type of graph.

For n vertices, a tree has:

n - 1 edges

and is:

Connected + Acyclic

Example:

A / \ B C / D

No cycle.

Graph

A general graph can have:

  • Cycles
  • Multiple components
  • Different numbers of edges
  • Directed edges
  • Weighted edges

Example:

A ----- B | \ | | \ | C ----- D

20. Important Relationship

Remember:

Every tree is a graph, but every graph is NOT a tree.

Think:

Graph ┌──────┴──────┐ │ │ Trees Other graphs

21. Graph Representations

This is one of the most important parts.

There are three common ways to represent graphs:

  1. Adjacency Matrix
  2. Adjacency List
  3. Edge List

22. Adjacency Matrix

Suppose:

A ----- B | | | | C ----- D

Vertices:

A B C D

We can create a matrix.

For an unweighted graph:

A B C D A 0 1 1 0 B 1 0 0 1 C 1 0 0 1 D 0 1 1 0

1 means:

Edge exists

0 means:

No edge

23. Matrix Example

If:

A ----- B

then:

matrix[A][B] = 1 matrix[B][A] = 1

because it is undirected.

For directed:

A → B

we have:

matrix[A][B] = 1 matrix[B][A] = 0

24. C++ Adjacency Matrix

int graph[4][4] = { {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 0, 1}, {0, 1, 1, 0} };

For:

A = 0 B = 1 C = 2 D = 3

25. Weighted Adjacency Matrix

Suppose:

A --5-- B A --2-- C

Matrix could be:

A B C A 0 5 2 B 5 0 ∞ C 2 ∞ 0

∞ means no direct edge.

26. Adjacency Matrix Complexity

For V vertices:

Space = O(V²)

Checking whether an edge exists:

O(1)

Adding/removing an edge:

O(1)

But traversing all neighbors can take:

O(V)

27. Adjacency List

An adjacency list stores the neighbors of each vertex.

For:

A ----- B | | C ----- D

we can write:

A → B, C B → A, D C → A, D D → B, C

This is much more memory-efficient for sparse graphs.

28. C++ Adjacency List

The most common representation:

vector<vector<int>> graph;

Example:

int V = 4; vector<vector<int>> graph(V); graph[0].push_back(1); graph[0].push_back(2); graph[1].push_back(0); graph[1].push_back(3); graph[2].push_back(0); graph[2].push_back(3); graph[3].push_back(1); graph[3].push_back(2);

29. Building an Undirected Graph

Instead of manually writing both directions:

void addEdge(vector<vector<int>>& graph, int u, int v) { graph[u].push_back(v); graph[v].push_back(u); }

Then:

addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 3); addEdge(graph, 2, 3);

Graph:

0 ----- 1 | | | | 2 ----- 3

30. Building a Directed Graph

For:

0 → 1

we only add:

graph[0].push_back(1);

We do not add:

graph[1].push_back(0);

unless the reverse edge actually exists.

31. Edge List

An edge list simply stores all edges.

Example:

A-B A-C B-D C-D

C++:

vector<pair<int, int>> edges;

Then:

edges.push_back({0, 1}); edges.push_back({0, 2}); edges.push_back({1, 3}); edges.push_back({2, 3});

For weighted graphs:

vector<tuple<int, int, int>> edges;

where:

(u, v, weight)

Example:

edges.push_back({0, 1, 5});

means:

0 --5-- 1

32. Matrix vs List vs Edge List

RepresentationSpaceEdge CheckBest For
MatrixO(V²)O(1)Dense graphs
ListO(V+E)O(degree)Sparse graphs
Edge ListO(E)O(E)Edge-based algorithms

For most graph traversal problems in C++, you'll frequently use:

vector<vector<int>>

33. Sparse vs Dense Graph

This is important.

Sparse Graph

Few edges:

V = 1000 E = 1500

Adjacency list is usually better.

Space:

O(V + E)

Dense Graph

Many edges:

V = 1000 E ≈ V²

Adjacency matrix may be useful.

Space:

O(V²)

34. Directed Graph Degree

For directed graphs, we have two types of degree.

Indegree

Number of edges coming into a vertex.

A → B C → B

For B:

indegree(B) = 2

Outdegree

Number of edges going out of a vertex.

B → D B → E

For B:

outdegree(B) = 2

35. Example of Directed Degree

A → B → C ↓ D

For B:

Indegree = 1 Outdegree = 2

Because:

A → B B → C B → D

36. Handshaking Theorem

For an undirected graph:

Sum of degrees = 2E

where:

E = number of edges

Example:

A ----- B | | C ----- D

Each vertex has degree 2.

So:

2 + 2 + 2 + 2 = 8

There are:

E = 4

Therefore:

2E = 2 × 4 = 8

37. Important Graph Types

You should recognize these:

Undirected

A ----- B

Directed

A → B

Weighted

A --5-- B

Unweighted

A ----- B

Connected

Every vertex reachable.

Disconnected

Multiple components.

Cyclic

Contains a cycle.

Acyclic

Contains no cycle.

Complete Graph

Every pair of distinct vertices has an edge.

For 4 vertices:

A / | \ B--|--C \ | / D

Number of edges in an undirected complete graph:

E = V(V - 1) / 2

38. Complete Graph Example

For:

V = 4

maximum number of undirected edges:

4(4-1)/2 = 4×3/2 = 6

So:

E = 6

39. Bipartite Graph

A graph is bipartite if its vertices can be divided into two groups such that no edge connects vertices within the same group.

Example:

Group A Group B A ------------- 1 | | B ------------- 2 | | C ------------- 3

There are no edges:

A-B B-C

inside Group A.

And no edges between:

1-2 2-3

inside Group B.

40. Real-Life Bipartite Example

Students and courses:

Students Courses Uday ---------- C++ | | | | └------------ Web Ram ---------- C++ | └------------ Networks

One group:

Students

Other group:

Courses

Edges represent enrollment.

41. DAG — Directed Acyclic Graph

A DAG is:

Directed + Acyclic

Example:

A → B → D ↓ C → D

There is direction, but no cycle.

DAGs are extremely important in:

  • Task scheduling
  • Course prerequisites
  • Build systems
  • Dependency resolution
  • Topological sorting

42. Example: Course Prerequisites

Suppose:

Programming Basics ↓ DSA ↓ Algorithms

You must learn:

Programming Basics

before:

DSA

and DSA before Algorithms.

This can be represented as a DAG.

43. Graph Traversal

Once we have a graph, we usually want to visit its vertices.

Two fundamental traversal algorithms are:

BFS DFS

You have already seen these ideas with trees.

44. BFS — Breadth First Search

BFS explores level by level.

It uses a:

Queue

Example:

0 / \ 1 2 / \ 3 4

Starting from 0:

0 ↓ 1 2 ↓ 3 4

Traversal:

0 1 2 3 4

45. BFS C++

void bfs(int start, vector<vector<int>>& graph) { int n = graph.size(); vector<bool> visited(n, false); queue<int> q; visited[start] = true; q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } }

46. Why visited[] Is Necessary

Consider:

A ----- B \ / \ / C

If we don't track visited nodes, we could repeatedly travel:

A → B → C → A → B → C ...

So we maintain:

vector<bool> visited(n, false);

When we visit a node:

visited[node] = true;

47. DFS — Depth First Search

DFS explores as deeply as possible before coming back.

It can use:

  • Recursion
  • Explicit stack

Example:

0 / \ 1 2 / \ 3 4

DFS could produce:

0 → 1 → 3 → 4 → 2

depending on adjacency order.

48. DFS C++ Recursive

void dfs( int node, vector<vector<int>>& graph, vector<bool>& visited ) { visited[node] = true; cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs(neighbor, graph, visited); } } }

Call:

vector<bool> visited(n, false); dfs(0, graph, visited);

49. DFS Using Stack

DFS can also be implemented iteratively:

void dfs(int start, vector<vector<int>>& graph) { int n = graph.size(); vector<bool> visited(n, false); stack<int> st; st.push(start); while (!st.empty()) { int node = st.top(); st.pop(); if (visited[node]) { continue; } visited[node] = true; cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { st.push(neighbor); } } } }

Remember:

DFS → Stack BFS → Queue

50. BFS vs DFS

FeatureBFSDFS
Full nameBreadth First SearchDepth First Search
Main structureQueueStack/Recursion
ExplorationLevel by levelDeep first
Shortest path in unweighted graphYesNot generally
Cycle detectionYesYes
Connected componentsYesYes
Topological sortPossibleCommon
Maze/path explorationYesYes

51. Graph Traversal Complexity

With an adjacency list:

O(V + E)

Why?

Each vertex is processed approximately once:

O(V)

and each edge is examined:

O(E)

Therefore:

Total = O(V + E)

Space:

O(V)

for:

visited[] + queue/stack/recursion

52. BFS Shortest Path

One major application of BFS:

Shortest path in an unweighted graph.

Example:

A ----- B ----- C | | D ------------- E

Suppose we want shortest path:

A → C

Possible paths:

A → B → C = 2 edges A → D → E → C = 3 edges

BFS finds:

A → B → C

because BFS explores by distance:

Distance 0 → Distance 1 → Distance 2 → ...

53. Graph Cycle

A graph contains a cycle if we can start at a vertex and return to it following edges.

Example:

A ----- B | | | | D ----- C

Cycle:

A → B → C → D → A

Cycle detection is a very common graph problem.

54. Cycle Detection in Undirected Graph

With DFS, we can keep track of the parent.

bool hasCycle( int node, int parent, vector<vector<int>>& graph, vector<bool>& visited ) { visited[node] = true; for (int neighbor : graph[node]) { if (!visited[neighbor]) { if (hasCycle( neighbor, node, graph, visited )) { return true; } } else if (neighbor != parent) { return true; } } return false; }

The important idea:

If we reach an already visited node that isn't our parent, we found a cycle.

55. Connected Components

Suppose:

A ----- B C ----- D ----- E F

There are:

3 components

We can run DFS/BFS from every unvisited vertex.

int components = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { components++; dfs(i, graph, visited); } }

This pattern is extremely important.

56. Graph Algorithms You Will Learn Later

Graphs are a huge DSA topic.

After basic graphs and traversal, you'll encounter:

Traversal

BFS DFS

Shortest Path

BFS Dijkstra Bellman-Ford Floyd-Warshall

Minimum Spanning Tree

Prim's Algorithm Kruskal's Algorithm

Directed Graph

Topological Sort Cycle Detection

Advanced

Disjoint Set Union Strongly Connected Components Bridges Articulation Points

57. Dijkstra's Algorithm

Used for shortest paths when edge weights are non-negative.

Example:

A --4-- B | | 2 1 | | C --3-- D

Find shortest distance from:

A

to:

D

Possible paths:

A → B → D = 4 + 1 = 5 A → C → D = 2 + 3 = 5

Dijkstra finds the minimum distance.

A Min Priority Queue is commonly used.

This connects directly to the topic you just learned:

Priority Queue ↓ Dijkstra ↓ Graphs

58. Topological Sort

Used for a DAG.

Example:

A → B A → C B → D C → D

A valid ordering:

A → B → C → D

Another valid ordering may be:

A → C → B → D

provided all dependencies are respected.

Applications:

  • Course scheduling
  • Build dependencies
  • Package dependencies
  • Task scheduling

59. Minimum Spanning Tree

Given a connected weighted undirected graph:

A --4-- B | \ | 2 5 3 | \ | C --1-- D

A Minimum Spanning Tree (MST) connects all vertices with minimum total edge weight and no cycles.

Main algorithms:

Prim's Kruskal's

60. Graph Learning Roadmap

Your DSA roadmap now reaches the graph section:

Graphs | ┌──────────────┴──────────────┐ ↓ ↓ Representation Traversal | | Matrix / List BFS / DFS | | └──────────────┬──────────────┘ ↓ Graph Problems | ┌───────────────┼────────────────┐ ↓ ↓ ↓ Shortest Path MST Topological Sort | | | Dijkstra/BF/FW Prim/Kruskal DAG

61. Graph vs Tree vs BST vs Heap vs Trie

Now you have covered many tree-based structures.

StructureMain Idea
TreeHierarchical structure
Binary Tree≤ 2 children
BSTOrdered binary tree
HeapPriority-based complete tree
TriePrefix/character tree
GraphGeneral connections

The biggest difference is:

Tree ↓ Hierarchical BST ↓ Ordered Heap ↓ Priority Trie ↓ Prefix Graph ↓ Relationships / Connections

62. A Complete C++ Graph Example

Let's put the important basics together.

#include <iostream> #include <vector> #include <queue> using namespace std; void addEdge( vector<vector<int>>& graph, int u, int v ) { graph[u].push_back(v); graph[v].push_back(u); } void bfs( int start, vector<vector<int>>& graph ) { int n = graph.size(); vector<bool> visited(n, false); queue<int> q; visited[start] = true; q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } } void dfs( int node, vector<vector<int>>& graph, vector<bool>& visited ) { visited[node] = true; cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs( neighbor, graph, visited ); } } } int main() { int V = 5; vector<vector<int>> graph(V); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 3); addEdge(graph, 1, 4); addEdge(graph, 2, 4); cout << "BFS: "; bfs(0, graph); cout << "\nDFS: "; vector<bool> visited(V, false); dfs(0, graph, visited); return 0; }

Possible output:

BFS: 0 1 2 3 4 DFS: 0 1 3 4 2

The exact DFS order can change depending on the order neighbors are stored.

🧠 Final Summary

You should now have this mental model:

GRAPH │ ├── Vertices │ └── Nodes │ ├── Edges │ └── Connections │ ├── Types │ ├── Directed │ ├── Undirected │ ├── Weighted │ ├── Unweighted │ ├── Connected │ ├── Disconnected │ ├── Cyclic │ ├── Acyclic │ ├── Bipartite │ └── DAG │ ├── Representations │ ├── Adjacency Matrix │ ├── Adjacency List ⭐ │ └── Edge List │ └── Traversal ├── BFS → Queue └── DFS → Stack / Recursion

The most important things to remember:

1. Graph = Vertices + Edges 2. Undirected: A ----- B 3. Directed: A → B 4. Weighted: A --5-- B 5. Adjacency Matrix: Space = O(V²) 6. Adjacency List: Space = O(V + E) 7. BFS: Queue O(V + E) 8. DFS: Stack/Recursion O(V + E) 9. BFS can find shortest paths in unweighted graphs. 10. Graphs can contain cycles, unlike trees.

And your roadmap is now:

Graphs ↓ Graph Traversal ↓ Sorting ↓ Searching ↓ Greedy Algorithms ↓ Divide and Conquer ↓ Dynamic Programming ↓ Bit Manipulation ↓ Advanced Data Structures ↓ Problem Solving

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy