Graph in DSA

Graphs and Their Representations

What is a Graph?

• Graph: A non-linear data structure made up of vertices (nodes) and edges (connections).
• Vertices: Points in the graph (also called nodes).
• Edges: Connections between two vertices.
• Non-linear: Unlike arrays or linked lists, graphs allow different paths to connect vertices.

Applications of Graphs:

• Social Networks: People as vertices, relationships as edges.
• Maps/Navigation: Locations as vertices, roads as edges.
• Internet: Web pages as vertices, hyperlinks as edges.
• Biology: Neural networks, disease spread modeling.

Graph Representations:

Graph Representation: How a graph is stored in memory. Different representations impact space and speed of operations.

Adjacency Matrix: A 2D array representing edges between vertices.

Types of Graph Representations:

1. Adjacency Matrix:

• 2D array where cell (i, j) stores information about the edge from vertex i to vertex j.
• Undirected Graph: Matrix is symmetric (edges go both ways).
• Directed Graph: Matrix is not symmetric (edges have a direction).
• Weighted Graph: Values in the matrix can represent edge weights.

Example (undirected graph):

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

Example (directed and weighted graph):

    A B C D
    A 0 3 0 0
    B 0 0 2 0
    C 0 0 0 4
    D 0 0 0 0
    

2. Adjacency List:

• Array of vertices, each having a linked list of adjacent vertices.
• Efficient for sparse graphs (many vertices with few edges).

Example (undirected graph):

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

Example (directed and weighted graph):

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

Summary of Representations:

Adjacency Matrix:

• Best for dense graphs.
• Simpler to implement, but consumes more memory.
• Can represent both directed and weighted graphs.

Adjacency List:

• Best for sparse graphs.
• More memory-efficient as it only stores existing edges.
• Flexible for representing both directed and weighted graphs.

Graphs are essential for representing interconnected data and solving problems like route finding, social network analysis, and web page linking. Understanding different graph representations helps choose the right structure based on the graph's density and the required operations.

How to Assign Weights in Adjacency List:

To assign weights in an Adjacency List representation of a graph, we follow the idea that each edge between vertices (nodes) can have an associated weight (or cost). In the Adjacency List format, each vertex points to a list (or another structure) that contains its neighboring vertices and the weight of the edges connecting them.

Formula for Representing Weights in Adjacency List:

There isn't exactly a "formula" per se, but here's the general approach to represent a weighted edge in an adjacency list:

• Adjacency List Format: Each vertex has a list (or linked list/array) of tuples, where:
• First Element of the Tuple: The neighbor vertex (the connected vertex).
• Second Element of the Tuple: The weight of the edge connecting the two vertices.

Example Breakdown:

Let’s take the example:

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

1. A -> (B, 3), (C, 1):

This means there are two edges originating from vertex A:

• An edge from A to B with weight 3.
• An edge from A to C with weight 1.

This can be represented as:

    A: [(B, 3), (C, 1)]
    

2. B -> (C, 2):

This means there's one edge originating from vertex B:

• An edge from B to C with weight 2.

This can be represented as:

    B: [(C, 2)]
    

3. C -> (D, 4):

This means there's one edge originating from vertex C:

• An edge from C to D with weight 4.

This can be represented as:

    C: [(D, 4)]
    

4. D -> (A, 4):

This means there's one edge originating from vertex D:

• An edge from D to A with weight 4.

This can be represented as:

    D: [(A, 4)]
    

How to Assign Weights?

• Identify the Edge: First, you need to know which two vertices are connected by the edge.
• Determine the Weight: Then, you need the weight (or cost) of that edge. The weight is usually provided in the problem (or computed based on some logic, like distance or time).
• Create the Tuple: For each edge, you store a tuple (neighbor, weight) in the list associated with the source vertex.

General Steps to Add Weighted Edges:

1. Create a list or dictionary for the adjacency list.
2. For each vertex:
• Store a list of tuples representing its neighbors and the weights of the edges connecting them.
3. For each edge:
• Add a tuple (neighbor_vertex, edge_weight) to the list of the source vertex.

Example in Python Code:

    # Adjacency list representation using a dictionary
    graph = {
        'A': [('B', 3), ('C', 1)],  # A -> B with weight 3, A -> C with weight 1
        'B': [('C', 2)],             # B -> C with weight 2
        'C': [('D', 4)],             # C -> D with weight 4
        'D': [('A', 4)]              # D -> A with weight 4
    }

    # Display the adjacency list
    for vertex, edges in graph.items():
        print(f"{vertex} -> {edges}")
    

When to Use Weights in Graphs?

• Shortest Path Algorithms: In algorithms like Dijkstra’s Algorithm or Bellman-Ford, weights are used to find the least-cost path between vertices.
• Network Flow: In problems like maximum flow in networks, weights represent the capacity of edges.
• Route Planning: In maps or GPS systems, weights could represent distances or travel times between locations.

Summary:

• The weight of an edge is just a value associated with a tuple (neighbor, weight) in an adjacency list.
• Weights can represent any cost or distance between two vertices (e.g., time, distance, cost).
• The structure you use (Adjacency List or Matrix) depends on the size and sparsity of your graph. For sparse graphs, an Adjacency List with weighted edges is more efficient.

Summary

1.