Table of Content

Introduction to Graphs

• Graphs are fundamental data structures used to model complex relationships between entities. A graph consists of:
  • Vertices (Nodes): These represent the entities or objects. For example, in a social network, each person can be represented as a vertex.
  • Edges: These are the connections between the vertices. In a social network, an edge might represent a friendship or a follow relationship.
• Applications of Graphs:
  • Social Networks: Represent users and their connections.
  • Transportation Networks: Represent cities and the roads connecting them.
  • Computer Networks: Represent computers (vertices) and the connections (edges) between them.

Types of Graphs

• Undirected Graphs:
  • In an undirected graph, edges do not have a direction. If there is an edge between vertex A and vertex B, you can traverse from A to B and from B to A.
  • Example: A social network where friendships are mutual. If Alice is friends with Bob, Bob is also friends with Alice. This mutual relationship is represented by a bidirectional edge.
  • Use Cases: Mutual relationships, bidirectional communication networks, undirected social networks.
• Directed Graphs (Digraphs):
  • In a directed graph, edges have a direction, indicating a one-way relationship. Each edge is like a one-way street, allowing traversal in only one direction.
  • Example: On Instagram, if Alice follows Bob, it doesn’t necessarily mean that Bob follows Alice back. This one-way relationship is represented by a directed edge from Alice to Bob.
  • Use Cases: Social media follow relationships, task scheduling, web page linking.
• Weighted Graphs:
  • In a weighted graph, each edge has a weight (or cost) associated with it, representing the cost, distance, or any quantifiable metric.
  • Example: Google Maps uses a weighted graph where intersections are vertices, and roads are edges with weights representing the distance or travel time between points.
  • Use Cases: Route optimization, network routing, logistics.
• Unweighted Graphs:
  • Edges do not have any weights. They simply represent connections between vertices without any additional information.
  • Example: A simple social network where the presence of a friendship is the only important factor.
  • Use Cases: Basic network representations, simple relationships.
• Cyclic Graphs:
  • A cyclic graph contains at least one cycle—a path that starts and ends at the same vertex.
  • Example: An electrical circuit where the flow can loop back to the starting point.
  • Use Cases: Feedback loops in circuits, round-trip routes in transportation systems.
• Acyclic Graphs:
  • These graphs do not contain any cycles. Trees are a special type of acyclic graph.
  • Example: A family tree, where there is only one path between any two vertices, preventing any cycles.
  • Use Cases: Hierarchical data structures, task dependency graphs.
• Connected Graphs:
  • In a connected graph, there is a path between every pair of vertices, ensuring that the graph is fully navigable.
  • Example: A city’s public transportation system where you can travel between any two stations, even if it requires changing routes.
  • Use Cases: Network design, ensuring communication paths in computer networks.
• Disconnected Graphs:
  • A disconnected graph contains at least one isolated vertex or group of vertices, meaning some vertices are not connected to others by any path.
  • Example: Separate groups of friends in a social network who do not know each other.
  • Use Cases: Analyzing isolated components in networks, disconnected social circles.
• Bipartite Graphs:
  • In a bipartite graph, vertices can be divided into two disjoint sets, and every edge connects a vertex in one set to a vertex in the other set.
  • Example: Job assignment where one set of vertices represents employees, and the other represents tasks, with edges representing which employee can do which task.
  • Use Cases: Matching problems, job assignment, recommendation systems.

Graph Representation

1. Adjacency Matrix

   • A 2D array (or matrix) used to represent a graph. The rows and columns represent the vertices. A cell in the matrix contains a value (typically 1 or 0) indicating whether there is an edge between the vertices.

   • Example:

     • For an undirected graph with vertices A, B, C, D:The adjacency matrix might look like this:

       A-B, A-D, B-C, C-D
       

         A B C D
       A 0 1 0 1
       B 1 0 1 0
       C 0 1 0 1
       D 1 0 1 0
       

   • Pros:

     • Simple: Easy to understand and visualize.
     • Quick Edge Lookup: You can quickly check if an edge exists between two vertices (O(1) time complexity).

   • Cons:

     • Memory Usage: Requires O(V²) space, which can be excessive for large graphs with few edges (sparse graphs).

   • Weighted Graphs: Instead of 1, store the weight of the edge in the matrix. For example, a weighted graph might have:The adjacency matrix could look like this:

     A-B (4), A-D (2), B-C (5), C-D (1)
     

       A B C D
     A 0 4 0 2
     B 4 0 5 0
     C 0 5 0 1
     D 2 0 1 0
     

2. Adjacency List

   • A more space-efficient way to represent a graph, particularly for sparse graphs. Each vertex has a list of vertices it is connected to.

   • Example:

     • For the same undirected graph as above:

       A -> B, D
       B -> A, C
       C -> B, D
       D -> A, C
       

   • Ps:

     • Space Efficient: Requires O(V + E) space, where V is the number of vertices and E is the number of edges.
     • Easy to Traverse: Efficient for iterating through the neighbors of a vertex.

   • Cons:

     • Slower Edge Lookup: Checking for the existence of an edge can take O(V) time in the worst case.

   • Weighted Graphs: Store pairs (neighbor vertex, weight) in the adjacency list. For example:

     A -> (B, 4), (D, 2)
     B -> (A, 4), (C, 5)
     C -> (B, 5), (D, 1)
     D -> (A, 2), (C, 1)
     

Graph Traversal Techniques

1. Breadth-First Search (BFS)

   • BFS explores a graph layer by layer, starting from a source vertex and visiting all its neighbors before moving on to the next level of neighbors.

   • Algorithm:

     1. Start at the source vertex and mark it as visited.
     2. Use a queue to keep track of vertices to visit next.
     3. Dequeue a vertex, visit its unvisited neighbors, and enqueue them.
     4. Repeat until the queue is empty.

   • Example:

     • For a graph starting at vertex A with neighbors B and C, and B having a neighbor D:Result: A -> B -> C -> D

       Start at A -> Visit B, C -> Visit D (from B)
       

   • Pros:

   • Time Complexity: O(V + E)

   • Space Complexity: O(V)

   • Applications: