Graphs in Data Structures Explained (BFS, DFS, Real-World Networks)
A Graph is a data structure used to represent relationships between objects. Unlike trees, graphs do not follow a strict parent-child hierarchy.
Graphs are used in:
- Google Maps
- Social Networks
- Flight Networks
- Recommendation Systems
- Computer Networks
Two fundamental graph traversal algorithms are:
- BFS (Breadth First Search) → explores level by level
- DFS (Depth First Search) → explores deeply before backtracking
If Trees model hierarchy, Graphs model connections.
A Simple Story Before We Start
Open Instagram. You
follow:
- Rahul
- Priya
- Arjun
Rahul follows:
- Sneha
- Karan
Priya follows:
- Neha
- Karan
Suddenly something interesting appears
Karan is connected to both Rahul and Priya. This is no longer a hierarchy.
This is a network.
And networks cannot be represented efficiently using arrays, linked lists, stacks, queues, or even trees.
They require a different structure. That structure is called a Graph.
Why Graphs Exist
Most real-world systems are built on relationships. Examples:
| System | Relationship |
|---|---|
| User ↔ User | |
| Professional ↔ Professional | |
| Google Maps | City ↔ City |
| Flight Network | Airport ↔ Airport |
| Internet | Device ↔ Device |
Whenever objects are connected to other objects, graphs become useful.
What is a Graph?
A Graph consists of:
Vertices (Nodes) Entities or objects.
Entities or objects.
Examples:
- Users
- Cities
- Websites
Edges
Connections between nodes.
Example:
A B
\ /
C
Nodes:
A, B, C
Edges:
A-B
B-C
A-C
Graph Visualization
explores level by level.
Imagine searching for friends.
You first visit:
- direct friends
Then:
- friends of friends
Then:
- third-level connections
BFS Visualization A
/ \
B C
/ \ / \
D E F G
BFS order:
A → B → C → D → E → F → G
BFS Example: Graph
Breadth First Search
BFS Uses Queue Java
Example:
Queue<Integer> queue = new LinkedList<>(); Because nodes are processed in arrival order.
Depth First Search (DFS)
DFS goes as deep as possible before returning. Imagine exploring a maze.
You continue moving forward until you hit a dead end.
Then you backtrack.
DFS Visualization Using
the same graph:
A → B → D
Backtrack
→ E
Backtrack
→ C
→ F
→ G
Depth First Search
DFS Example - Graph
DFS Uses Stack
Either:
- Explicit Stack
- Recursion (which internally uses Stack)
BFS vs DFS
| Feature | BFS | DFS |
|---|---|---|
| Strategy | Level-wise | Deep exploration |
| Data Structure | Queue | Stack |
| Shortest Path | Yes (unweighted) | Not guaranteed |
| Memory Usage | Higher | Lower |
| Typical Use | Navigation | Exploration |
Real-World Applications
Google Maps
Finding shortest routes.
Finding professional connections.
Instagram Recommendations
Discovering connected users.
Network Routing
Finding paths between devices.
Flight Reservation Systems
Route optimization.
Why Graphs Matter So Much
Graphs represent something fundamental:
- Relationships.
- Modern software is built on relationships. Users
- connect to users.
- Services connect to services. Servers
- connect to servers.
- Cities connect to cities.
Understanding graphs means understanding how modern systems think.
Common Mistakes Beginners Make
Thinking Graphs Are Trees
Trees are a special type of graph. Not every graph is a tree.
Mixing BFS and DFS
They solve different problems.
Ignoring Graph Representation
Choosing the wrong representation impacts performance.
Frequently Asked Questions (FAQ)
Yes. Every tree is a graph. Not every graph is a tree.
Because nodes must be explored level by level.
Because it must return to previous nodes after exploring deeply.
Both. Most graph problems use either BFS or DFS.
Final Thoughts
Arrays taught you storage.
Linked Lists taught you connections. Trees taught you hierarchy.
Graphs teach something bigger:
Relationships at scale.
Once you understand graphs, you begin seeing them everywhere:
- social media
- maps
- cloud infrastructure
- recommendation engines
- distributed systems
And that is why graphs are considered one of the most powerful concepts in computer science.