DSA Graphs

DSA Tutorial

DSA Graphs – Complete Beginner Guide

(Concept • Types • Representation • Traversals • Examples • Complexity)

A Graph is one of the most powerful non-linear data structures in DSA.
It is used to represent networks, connections, and relationships.

1️⃣ What is a Graph?

A Graph consists of:

  • Vertices (Nodes) → represent entities

  • Edges → represent connections between nodes

G = (V, E)

Example


2️⃣ Why Graphs Are Important

✔ Represent real-world networks
✔ Used in social media, maps, internet
✔ Core of advanced algorithms
✔ Frequently asked in interviews

3️⃣ Basic Graph Terminology

Term Meaning
Vertex Node
Edge Connection
Degree Number of edges
Path Sequence of vertices
Cycle Path that starts & ends same
Connected Graph All vertices reachable
Disconnected Graph Some vertices unreachable

4️⃣ Types of Graphs

1. Undirected Graph

Edges have no direction.

A —— B

 2. Directed Graph (Digraph)

Edges have direction.

A → B

 3. Weighted Graph

Edges have weights / cost.

A --5--> B

 4. Unweighted Graph

All edges have same weight.

 5. Cyclic Graph

Contains at least one cycle.

 6. Acyclic Graph

No cycles (example: Tree).

5️⃣ Graph Representation (Very Important)

 1. Adjacency Matrix

  • 2D array V × V

  • 1 means edge exists

Example:

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

✔ Fast edge check
❌ High memory usage

 2. Adjacency List (Most Used)

  • Each vertex stores list of neighbors

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

✔ Space efficient
✔ Preferred in interviews

6️⃣ Graph Representation Code (Adjacency List – C++)


 

7️⃣ Graph Traversals ( Most Important)

Traversal = visiting all vertices.

 1. Breadth First Search (BFS)

  • Uses Queue

  • Level by level traversal

BFS Code (C++)


 

 2. Depth First Search (DFS)

  • Uses Recursion / Stack

  • Goes deep first

DFS Code (C++)


 

8️⃣ Time Complexity

Using Adjacency List

Operation Time
BFS O(V + E)
DFS O(V + E)

9️⃣ Space Complexity

Representation Space
Adjacency Matrix O(V²)
Adjacency List O(V + E)

🔟 Graph vs Tree

Feature Graph Tree
Cycles Possible ❌ No
Root Optional Mandatory
Direction Yes / No No
Structure General Hierarchical

1️⃣1️⃣ Real-Life Applications

✔ Google Maps (shortest path)
✔ Social networks
✔ Computer networks
✔ Recommendation systems
✔ Scheduling problems

Interview Questions (Graphs)

Q1. Difference between BFS and DFS?
👉 Queue vs recursion

Q2. Which traversal finds shortest path in unweighted graph?
👉 BFS

Q3. Adjacency matrix vs list?
👉 Space vs speed trade-off

 Final Summary

✔ Graphs represent connections
✔ Vertices + edges
✔ Many types (directed, weighted)
✔ BFS & DFS are core algorithms
✔ Extremely important for DSA & interviews

You may also like...