Learn Complete Graph DSA with Animation - Interactive Learning
Master Graph Algorithms - DSA Learning Platform 🗺️ Master Graph Algorithms BFS / DFS Dijkstra / A* MST Learn graph traversal and pathfinding algorithms with interactive animations 📖 Understanding Graph Data Structures & Algorithms Introduction Representation Traversal Shortest Path MST Applications What is a Graph? A Graph is a non-linear data structure consisting of vertices (nodes) and edges that connect pairs of vertices. Graphs are used to represent relationships and connections. G = (V, E) where V is the set of vertices and E is the set of edges. Types of Graphs Undirected: Edges have no direction (A—B) Directed: Edges have direction (A→B) Weighted: Edges have associated costs Unweighted: All edges have equal cost Cyclic/Acyclic: Contains cycles or not 🔑 Key Terminology Vertex: Node in the graph Edge: Connection between vertices Degree: Number of edges at a vertex Path: Sequence of vertices connected by edges Cycle: Path that starts and ends at same vertex Connected: Path exists between all pairs DAG: Directed Acyclic Graph Graph Representations 1. Adjacency List Each vertex stores a list of its neighbors. Space: O(V + E) Best for: Sparse graphs 0 → [1, 2] 1 → [0, 3] 2 → [0, 3] 3 → [1, 2] 2. Adjacency Matrix 2D array where matrix[i][j] = 1 if edge exists. Space: O(V²) Best for: Dense graphs, quick edge lookup 📊 Comparison Operation List Matrix Add Edge O(1) O(1) Remove Edge O(E) O(1) Check Edge O(V) O(1) Get Neighbors O(1) O(V) Space O(V+E) O(V²) Graph Traversal Algorithms 🌊 Breadth-First Search (BFS) Explores level by level using a Queue. Finds shortest path in unweighted graphs Visits all vertices at distance k before k+1 Uses more memory (stores all neighbors) 🏊 Depth-First Search (DFS) Explores as deep as possible using a Stack. Good for detecting cycles Used in topological sorting Uses less memory (recursion stack) ⏱️ Time Complexity BFS: O(V + E) DFS: O(V + E) 💾 Space Complexity BFS: O(V) for queue DFS: O(V) for recursion stack 📋 When to Use BFS: Shortest path, level-order DFS: Cycle detection, topological sort Shortest Path Algorithms 📍 Dijkstra's Algorithm Finds shortest path from source to all vertices. Time: O((V + E) log V) with priority queue Limitation: No negative weights ⭐ A* Algorithm Dijkstra + Heuristic for goal-directed search. Time: O(E) best case with good heuristic Heuristic: f(n) = g(n) + h(n) 🔄 Bellman-Ford Handles negative edge weights. Time: O(V × E) Detects: Negative weight cycles 🔑 Algorithm Selection Unweighted: Use BFS Non-negative weights: Use Dijkstra Negative weights: Use Bellman-Ford Goal-directed: Use A* All pairs: Use Floyd-Warshall Minimum Spanning Tree (MST) A subset of edges that connects all vertices with minimum total weight and no cycles. 🌲 Kruskal's Algorithm Greedy: Sort edges, add if no cycle (Union-Find). Time: O(E log E) Best for: Sparse graphs 🌳 Prim's Algorithm Greedy: Grow tree from start vertex. Time: O(E log V) with priority queue Best for: Dense graphs 📊 MST Properties Connec...
Subject: Data Structures with Animation | Chapter: Graph Data Structure