Log In Sign Up
Day 19

Day 19: Graph Representations

19/60 Days

Graph Representations #

Welcome to Day 19 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive deeper into various ways of representing graphs in code, exploring their pros and cons, and discussing when to use each representation.

Overview of Graph Representations #

There are several ways to represent a graph in computer memory. The choice of representation depends on the type of graph and the algorithms you plan to use. The most common representations are:

  1. Adjacency Matrix
  2. Adjacency List
  3. Edge List
  4. Incidence Matrix

Let’s explore each of these in detail.

1. Adjacency Matrix #

An adjacency matrix is a 2D array of size V x V where V is the number of vertices in the graph. The entry matrix[i][j] is 1 (or the edge weight for weighted graphs) if there is an edge from vertex i to vertex j, and 0 otherwise.

Implementation: #

 1class GraphMatrix:
 2    def __init__(self, num_vertices, directed=False):
 3        self.num_vertices = num_vertices
 4        self.directed = directed
 5        self.matrix = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]
 6
 7    def add_edge(self, v1, v2, weight=1):
 8        self.matrix[v1][v2 …