Graph

• A graph is an Abstract Data Type (ADT) because it models relationships between objects without specifying implementation.
• It defines operations like adding vertices and edges, and traversing connections.
• Vertices (nodes): Represent objects.
• Edges (links): Represent relationships
• Traversal: Explore connections between vertices.
• Use Cases:
  • Graphs are useful when relationships matter, e.g., social networks, transport routes, computer networks, or task dependencies
• Weighted Graph: Edge has an associated value (weight), representing cost, distance, time, or capacity.
• Directed Graph: Edges have a direction, going from one vertex to another

Examples of ADTs and Possible Implementations

• Stack
  • Using lists/arrays: Append to the end and remove from the end.
  • Using linked lists: Insert and remove at the head.
• Queue
  • Using lists/arrays: Append at the end and remove from the front (or use circular arrays).
  • Using linked lists: Insert at tail, remove from head
• Linked List
  • Using nodes and pointers explicitly.
    Can also be emulated using arrays/lists where each element stores the value and index of the next element.
• Dictionary: Stores key-value pairs, allowing retrieval of values by keys
  • Using hash tables (built-in dict in Python).
  • Using linked lists or binary trees for ordered or chained implementations
• Binary Tree
  • Using nodes with pointers to left and right children.
  • Using arrays/2D arrays for complete binary trees where children indices are calculated.