Graphs and Their Representation

Graphs

• A graph is a non-linear data structure used to represent relationships between entities.
• Nodes (or vertices) represent individual entities.
• Edges represent connections or relationships between nodes.

Types of Graphs

• Directed graphs: Relationships flow in one direction (e.g., Instagram followers)
• Undirected graphs: Relationships flow bi-directionally (e.g., Facebook friendships)
• Weighted graphs: Edges have additional data associated with them (e.g., distance between airports)
• Cycles: A node can point back to itself, creating a loop (e.g., an airplane returning to its departure airport)

Graph Representation

• Adjacency matrix: 2D array with rows and columns representing nodes. A '1' at the intersection indicates a connection, while a '0' indicates no connection.
  • Advantages: Fast lookup and edge addition.
  • Disadvantages: Quadratic space complexity and time complexity for node insertion.
• Adjacency list: Each node is linked to an array of its neighbors.
  • Advantages: Efficient for graphs with many nodes and few edges, faster iteration over node edges.
  • Disadvantages: Slower lookup compared to the matrix.

Graph Traversal Algorithms

• Depth-First Search (DFS): Explores a branch of the graph as deeply as possible before backtracking.
  • Implementation: Recursive function.
• Breadth-First Search (BFS): Visits nodes in layers starting from the root node.
  • Implementation: Queue.

Graph Applications

• Social networks: Representing connections between users (e.g., Facebook, Instagram)
• Recommendation engines: Connecting users, items, and preferences (e.g., Yelp, Netflix)
• Geographic data: Representing locations and connections (e.g., Google Maps)

Code Example: Building a Graph in JavaScript

• The code implements an undirected, unweighted graph using an adjacency list.
• Function addNode: Adds a new node to the graph by creating a key-value pair in the adjacencyList map.
• Function addEdge: Creates a connection between two nodes by adding each node to the other's adjacency list.
• BFS Algorithm:
  • Uses a queue to explore nodes in layers.
  • Keeps track of visited nodes using a set.
  • Uses shift to remove and access the first element of the queue.
• DFS Algorithm:
  • Uses a recursive function to explore the graph.
  • Keeps track of visited nodes using a set.

Time Complexity of Traversal Algorithms

• BFS and DFS: O(V + E), which is linear based on the number of nodes (V) and edges (E) in the graph.

This quiz covers the fundamentals of graphs, including types, properties, and various methods of representation such as adjacency matrices and lists. You'll explore directed and undirected graphs, weighted graphs, and cycles, enhancing your understanding of these essential data structures.