Introduction

Graph representation is a crucial concept in understanding and working with graphs. It involves the methods used to store and manipulate graph data in a computer. There are several ways to represent graphs, each with its own advantages and disadvantages. The two most common representations are:

Adjacency Matrix
Adjacency List

Adjacency Matrix

Definition

An adjacency matrix is a 2D array of size VxV where V is the number of vertices in the graph. Each cell in the matrix represents the presence (or absence) of an edge between two vertices.

Structure

Undirected Graph: If there is an edge between vertex i and vertex j, then matrix[i][j] = 1 and matrix[j][i] = 1.
Directed Graph: If there is an edge from vertex i to vertex j, then matrix[i][j] = 1.
Weighted Graph: Instead of 1, the cell contains the weight of the edge.

Example

Consider a simple undirected graph with 4 vertices (0, 1, 2, 3) and edges (0-1, 0-2, 1-2, 2-3):

	0	1	2	3
0	0	1	1	0
1	1	0	1	0
2	1	1	0	1
3	0	0	1	0

Code Example

# Adjacency Matrix Representation in Python

class Graph:
    def __init__(self, num_vertices):
        self.V = num_vertices
        self.graph = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]

    def add_edge(self, u, v):
        self.graph[u][v] = 1
        self.graph[v][u] = 1  # For undirected graph

    def print_graph(self):
        for row in self.graph:
            print(" ".join(map(str, row)))

# Example usage
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)

g.print_graph()

Advantages and Disadvantages

Advantages	Disadvantages
Simple and easy to implement	Requires O(V^2) space
Efficient to check if an edge exists	Inefficient for sparse graphs
Suitable for dense graphs	Adding/removing edges is O(1)

Adjacency List

Definition

An adjacency list is an array of lists. The array size is equal to the number of vertices. Each element of the array is a list that contains the vertices adjacent to the corresponding vertex.

Structure

Undirected Graph: Each list contains all vertices connected to the vertex.
Directed Graph: Each list contains all vertices that the vertex has edges to.
Weighted Graph: Each list contains pairs (vertex, weight).

Example

Consider the same undirected graph with 4 vertices (0, 1, 2, 3) and edges (0-1, 0-2, 1-2, 2-3):

0: [1, 2]
1: [0, 2]
2: [0, 1, 3]
3: [2]

Code Example

# Adjacency List Representation in Python

class Graph:
    def __init__(self, num_vertices):
        self.V = num_vertices
        self.graph = [[] for _ in range(num_vertices)]

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)  # For undirected graph

    def print_graph(self):
        for i in range(self.V):
            print(f"{i}: {self.graph[i]}")

# Example usage
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)

g.print_graph()

Advantages and Disadvantages

Advantages	Disadvantages
Requires less space for sparse graphs	More complex to implement
Efficient to iterate over all edges	Checking if an edge exists is O(V)
Suitable for sparse graphs	Adding/removing edges is O(1)

Comparison

Feature	Adjacency Matrix	Adjacency List
Space Complexity	O(V^2)	O(V + E)
Edge Existence Check	O(1)	O(V)
Iterating Neighbors	O(V)	O(E)
Adding Edge	O(1)	O(1)
Removing Edge	O(1)	O(E)

Conclusion

Understanding the different ways to represent graphs is fundamental for selecting the appropriate data structure based on the specific requirements of the problem at hand. Adjacency matrices are simple and efficient for dense graphs, while adjacency lists are more space-efficient and suitable for sparse graphs. Each representation has its own set of trade-offs, and the choice depends on the operations that need to be optimized.

In the next section, we will explore graph search algorithms, which are essential for traversing and exploring graphs efficiently.

Graph Representation

Introduction

Adjacency Matrix

Definition

Structure

Example

Code Example

Advantages and Disadvantages

Adjacency List

Definition

Structure

Example

Code Example

Advantages and Disadvantages

Comparison

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Trees

Module 6: Graphs

Module 7: Conclusions and Additional Resources