DSA — Graphs

What is a Graph?

A non-linear data structure consisting of vertices and edges.

class Graph:
    def __init__(self):
        self.adj_list = {}
    
    def add_vertex(self, vertex):
        if vertex not in self.adj_list:
            self.adj_list[vertex] = []
    
    def add_edge(self, v1, v2):
        self.adj_list[v1].append(v2)
        self.adj_list[v2].append(v1)

Graph Types

Type	Description
Directed	Edges have direction
Undirected	Edges are bidirectional
Weighted	Edges have weights
Cyclic	Contains cycles
Acyclic	No cycles

Representation

# Adjacency List
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}

# Adjacency Matrix
matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 0],
    [0, 1, 0, 0]
]

Mini Practice

1. Implement a graph
2. Add vertices and edges
3. Display adjacency list
4. Check if edge exists

Up Next

Continue with Graph Traversal — traversing graphs.