Unit 10: Graphs  (DSA)– Exam Revision Notes

1. Introduction to Graphs

• Graph = Non-linear data structure consisting of vertices (nodes) and edges (connections).
  
• Vertices (V) – Represent entities.
  
• Edges (E) – Represent relationships between vertices.
  
• Graph Representation:
  
  1. Adjacency Matrix – 2D array; 1 if edge exists, 0 otherwise.
     
  2. Adjacency List – List of neighbors for each vertex; memory-efficient for sparse graphs.
     

2. Types of Graphs

1. Undirected Graph – Edges have no direction.
   
2. Directed Graph (Digraph) – Edges have a direction.
   
3. Weighted Graph – Each edge has a weight (cost, distance).
   
4. Unweighted Graph – Edges have no weight.
   
5. Connected Graph – Path exists between all vertex pairs.
   
6. Disconnected Graph – Some vertices are isolated.
   

3. Graph as an Abstract Data Type (ADT)

• ADT Operations:
  
  1. AddVertex(v) – Add new vertex.
     
  2. AddEdge(u, v) – Add edge between vertices u and v.
     
  3. RemoveVertex(v) – Delete vertex and its edges.
     
  4. RemoveEdge(u, v) – Delete edge between u and v.
     
  5. TraverseGraph() – Visit all vertices (DFS/BFS).
     

4. Graph Traversal

1. Breadth-First Search (BFS)
   
   • Level-wise traversal using queue.
     
   • Finds shortest path in unweighted graphs.
     
2. Depth-First Search (DFS)
   
   • Traverses as far as possible along a branch using recursion or stack.
     
   • Useful for detecting cycles, connectivity, topological sorting.
     

5. Shortest Path & Spanning Trees

• Shortest Path Algorithm – Find minimum path between vertices:
  
  • Dijkstra’s Algorithm – Weighted graph with non-negative edges.
    
• Minimum Spanning Tree (MST) – Subset of edges connecting all vertices with minimum total weight:
  
  • Kruskal’s Algorithm – Greedy, sorts edges by weight.
    
  • Prim’s Algorithm – Greedy, expands tree one vertex at a time.
    

6. Transitive Closure

• Determines reachability between all pairs of vertices.
  
• Warshall’s Algorithm – Efficient method using adjacency matrix.
  

7. Applications of Graphs

1. Network Routing – Internet packet routing, shortest path.
   
2. Social Networks – Represent connections among users.
   
3. Project Scheduling – PERT/CPM uses directed acyclic graphs.
   
4. Circuit Design – Represent dependencies among components.
   
5. Game Theory / AI – Decision trees, game trees.
   

✅ Key Takeaways – Unit 10

• Graph = vertices + edges; represented by matrix or list.
  
• Traversal: BFS (queue), DFS (stack/recursion).
  
• Shortest path: Dijkstra, Minimum Spanning Tree: Kruskal/Prim.
  
• Applications in networking, scheduling, AI, social graphs.
• ADT operations include add/remove vertex/edge, traverse, search.