Graph Data Structure – Complete Beginner to Advanced Guide with BFS, DFS and Examples

Graph Data Structure – Complete Beginner to Advanced Guide with BFS, DFS and Examples

Graphs are one of the most powerful and widely used data structures in computer science. They are used to represent networks such as social media connections, road maps, computer networks, recommendation systems, and many real-world problems.

What is a Graph?

A graph is a non-linear data structure that consists of a set of vertices (nodes) and a set of edges that connect these vertices.

Basic Terminology

  • Vertex (Node): An individual point in the graph.
  • Edge: A connection between two vertices.
  • Degree: Number of edges connected to a vertex.
  • Path: A sequence of vertices connected by edges.
  • Cycle: A path that starts and ends at the same vertex.

Types of Graphs

  • Undirected Graph
  • Directed Graph (Digraph)
  • Weighted Graph
  • Unweighted Graph
  • Cyclic Graph
  • Acyclic Graph

Graph Representation

1. Adjacency Matrix

A 2D matrix where rows and columns represent vertices and values represent edges.

2. Adjacency List

Each vertex stores a list of connected vertices. This is more memory efficient.

Graph Traversal Algorithms

1. Breadth First Search (BFS)

BFS explores the graph level by level using a queue.

Applications of BFS

  • Finding shortest path in unweighted graphs
  • Web crawling
  • Social network analysis

2. Depth First Search (DFS)

DFS explores as deep as possible before backtracking. It uses recursion or stack.

Applications of DFS

  • Detecting cycles
  • Topological sorting
  • Finding connected components

Shortest Path Algorithms

  • Dijkstra’s Algorithm
  • Bellman-Ford Algorithm
  • Floyd-Warshall Algorithm

Minimum Spanning Tree (MST)

  • Prim’s Algorithm
  • Kruskal’s Algorithm

Real Life Applications of Graphs

  • Google Maps and GPS navigation
  • Social media friend suggestions
  • Computer networks routing
  • Search engines
  • Recommendation systems

Graph Interview Questions

  • What is a graph?
  • Difference between BFS and DFS?
  • What is a directed graph?
  • What is a cycle in a graph?
  • Explain Dijkstra’s algorithm.

Common Graph Problems

  • Detect cycle in a graph
  • Find shortest path
  • Count connected components
  • Topological sorting
  • Find bridges and articulation points

Practice Tips

  • Start with small graphs and draw them
  • Implement BFS and DFS from scratch
  • Solve graph problems daily
  • Understand recursion and queue usage

Conclusion

Graphs are extremely important in both academics and real-world applications. Mastering graph concepts and algorithms will greatly improve your problem-solving skills and help you crack technical interviews.

Next Post: Sorting and Searching Algorithms – Complete Guide with Time Complexity

Comments

Post a Comment

Popular posts from this blog

5 JavaScript Console Methods You're Not Using (But Should Be)

5 JavaScript Console Methods You're Not Using (But Should Be) JavaScript, Debugging, Developer Tools, Productivity https://images.unsplash.com/photo-1555066931-4365d14bab8c?ixlib=rb-4.0.3&auto=format&fit=crop&w=1000&q=80 Everyone uses console.log() , but JavaScript's console object has powerful debugging methods that can save you hours. Here are 5 underused console methods that will make you a better debugger. 1. console.table() - View Arrays & Objects Beautifully Instead of expanding objects in the console, display them as a table. JavaScript const users = [ { name: 'Alice', age: 25, city: 'NYC' }, { name: 'Bob', age: 30, city: 'London' }, { name: 'Charlie', age: 35, city: 'Tokyo' } ]; console.table(users); // Displays a beautiful sortable table Use case: When working with arrays of objects (API responses, user data). 2. console.group() - Organize Your Logs...
Read more

Build a Simple Calculator with HTML, CSS & JavaScript

Build a Simple Calculator with HTML, CSS & JavaScript JavaScript, Projects, HTML, CSS, Beginner Projects https://images.unsplash.com/photo-1581276879432-15e50529f34b?ixlib=rb-4.0.3&auto=format&fit=crop&w=1000&q=80 In this tutorial, we'll build a fully functional calculator from scratch. This is a perfect project for beginners to practice HTML structure, CSS styling, and basic JavaScript logic. What we're building: A calculator with number buttons (0-9), operators (+, -, ×, ÷), equals (=), and clear (C) functions. Step 1: HTML Structure First, create the basic HTML structure for our calculator. calculator.html <!DOCTYPE html> <html lang="en"> <head> <title>Simple Calculator</title> <link rel="stylesheet" href="style.css"> </head> <body> <div class="calculator"> ...
Read more

How to Center a Div - The 3 Modern Ways (2026)

Centering a <div> used to be a meme in the CSS world because it was surprisingly hard. But in 2024, we have three clean, modern solutions. Here's how to do it properly. Method 1: Flexbox (Most Popular) CSS .container { display: flex; justify-content: center; align-items: center; height: 100vh; /* Full viewport height */ } When to use: Modern layouts, when you need to center both horizontally AND vertically. Method 2: CSS Grid CSS .container { display: grid; place-items: center; height: 100vh; } When to use: When working with grid-based layouts already. Method 3: The Classic Margin Auto CSS .centered-div { width: 300px; margin: 0 auto; } When to use: Simple horizontal centering only (still works perfectly!). 💡 Pro Tip: For simple horizontal centering, use margin: 0 auto . For modern full centering, use Flexbox. For grid layouts, use CSS Grid's place-items: center . ...
Read more