🌉 Graphs – Comprehensive Study Guide

A **Graph** is a **collection of nodes (vertices) and edges** that connect them. Graphs are widely used in **networking, AI, and real-world applications**.

⚡ Why are Graphs Important?

• ✅ **Used in shortest path finding (Google Maps, GPS, AI).**
• 📡 **Essential for social networks & web crawling.**
• 🚀 **Applied in networking, game development & robotics.**
• 🔍 **Forms the foundation of AI-based recommendation systems.**

📌 Types of Graphs

📥 **1. Directed vs Undirected Graphs**

• 📌 **Directed Graph (Digraph)** – Edges have a direction (e.g., social media followers).
• 📌 **Undirected Graph** – Edges are bidirectional (e.g., Facebook friends).

📤 **2. Weighted vs Unweighted Graphs**

• 📌 **Weighted Graph** – Edges have weights (e.g., distance in Google Maps).
• 📌 **Unweighted Graph** – Edges have no weight (e.g., friendships in social networks).

🛠️ Graph Representation

📌 **1. Adjacency Matrix (O(V²) Space Complexity)**

                int graph[V][V]; // If graph[i][j] = 1, there is an edge from i to j
                

📌 **2. Adjacency List (O(V + E) Space Complexity, More Efficient)**

                vector adj[V]; // Stores neighbors for each vertex
                

🔍 Graph Traversal Techniques

📌 **1. Breadth-First Search (BFS) (O(V + E))**

Explores neighbors before moving deeper into the graph.

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

📌 **2. Depth-First Search (DFS) (O(V + E))**

Explores as deep as possible before backtracking.

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

📏 Shortest Path Algorithms

📌 **1. Dijkstra’s Algorithm (O(V + E log V))**

                void dijkstra(vector>>& graph, int src) {
                    priority_queue, vector>, greater>> pq;
                    vector dist(graph.size(), INT_MAX);
            
                    pq.push({0, src});
                    dist[src] = 0;
            
                    while (!pq.empty()) {
                        int u = pq.top().second;
                        pq.pop();
                        for (auto edge : graph[u]) {
                            int v = edge.first, weight = edge.second;
                            if (dist[u] + weight < dist[v]) {
                                dist[v] = dist[u] + weight;
                                pq.push({dist[v], v});
                            }
                        }
                    }
                }
                

📌 **2. Bellman-Ford Algorithm (O(VE))**

                void bellmanFord(vector>& edges, int V, int src) {
                    vector dist(V, INT_MAX);
                    dist[src] = 0;
            
                    for (int i = 1; i < V; i++) {
                        for (auto edge : edges) {
                            int u = edge[0], v = edge[1], weight = edge[2];
                            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                                dist[v] = dist[u] + weight;
                            }
                        }
                    }
                }
                

📌 **3. Floyd-Warshall Algorithm (O(V³))**

                void floydWarshall(vector>& dist, int V) {
                    for (int k = 0; k < V; k++) {
                        for (int i = 0; i < V; i++) {
                            for (int j = 0; j < V; j++) {
                                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                            }
                        }
                    }
                }
                

⏳ Time Complexity Analysis

🌍 Real-World Applications of Graphs

• 📡 **Google Maps & GPS Navigation** – Shortest route finding.
• 🔗 **Social Networks** – Analyzing connections between users.
• 🤖 **AI & Robotics** – Pathfinding in automated systems.
• 🎮 **Game Development** – AI-based movement & level design.

🔗 Next Topics

• 🌉 Graph Traversal (BFS & DFS)
• 📡 Dijkstra’s Algorithm
• 🌲 Minimum Spanning Tree (MST)