A graph is like a network of connections, made up of points called vertices that are joined together by lines called edges. Each vertex can connect to any other vertex in the network, which makes graphs versatile for real-world problems like mapping roads between cities or showing friendships on social media. Unlike trees where connections flow in one direction from parent to child, graphs can have connections going any way between their vertices.

Graphs allow us to modify and analyze connections in our network. Common tasks include connecting points with new edges, removing connections, and finding paths between different locations. The efficiency of these operations depends on how we store the graph and what algorithms we use.

Some graph algorithms use a special mathematical concept called the Inverse Ackermann function, shown as α(n). Don't worry too much about the math behind it - what's important is that this function grows so slowly that when we say an algorithm runs in O(α(n)) time, it means it's practically as fast as an instant operation.

Think of a graph like a map where vertices are locations edges are the roads connecting them. Each vertex (or location) can store information, and it keeps track of all other vertices it's directly connected to - these are called adjacent vertices. Just like you can follow roads to get from one place to another, you can follow edges to create a path through the graph.

# Definition for a graph node (vertex) 
class Node:
    def __init__(self, val: int = 0, neighbors: List[int] = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

Sometimes, following a path might lead you back to where you started - this is called a cycle. In a social network, for example, this would be like starting at one friend, going through their connections, and eventually coming back to the original friend through a chain of mutual friendships.

Adjacency lists are a way to represent graphs, like a contact list in your phone, where each person (vertex) has their own list of friends (adjacent vertices). We build it with a hashmap, where the key is the person's name and the value is their list of friends. This makes it easy to find all of someone's connections just by looking them up in the list.

# Building an adjacency list for directed graph (one-way edge)
def directedGraph(edges: List[List[int]]) -> Dict[int, List[int]]:
    hashmap = defaultdict(list)
    for source, destination in edges:
        hashmap[source].append(destination)
    return hashmap

# Building an adjacency list for undirected graph (two-way edge)
def undirectedGraph(edges: List[List[int]]) -> Dict[int, List[int]]:
    hashmap = defaultdict(list)
    for source, destination in edges:
        hashmap[source].append(destination)
        hashmap[destination].append(source)
    return hashmap

To build this list, we start with a list of edges - like having a list of source and destination vertices. Each pair tells us that two vertices are connected, just like how you might build your social network by adding one friendship at a time. This makes it easy to organize all connections and quickly find someone's friends just by looking them up in the list.

A matrix is a two-dimensional array where each cell exists in a grid of rows and columns. Think of it like a chess board where each square has its own coordinates. We describe a matrix's size using two numbers: m for the number of rows and n for the number of columns, written as m × n.

# Example 4 x 5 matrix (4 rows, 5 columns)
matrix = [
    [1,  2,  3,  4,  5 ], # Row 0
    [6,  7,  8,  9,  10], # Row 1
    [11, 12, 13, 14, 15], # Row 2
    [16, 17, 18, 19, 20]  # Row 3
]

# Extracting the number of rows and columns
ROWS, COLS = len(matrix), len(matrix[0])
print(f"The matrix has {ROWS} rows and {COLS} columns")

Matrices are perfect for solving problems about spaces and connections, like finding the shortest path through a maze or tracking how something spreads across a grid. Each cell can hold different types of information - in a maze problem, cells might represent walls, open paths, or visited locations . We can move through the matrix by changing our row and column position, typically going in four directions to reach neighboring cells.

An adjacency matrix is like a giant checklist showing who's connected to whom in your network. Imagine a spreadsheet where both rows and columns list all the people (vertices), and we put a 1 in cells where two people are friends and 0 where they're not. Since every vertex needs a row and column to show all possible connections, this creates a square grid.

Adjacency matrices are like using an entire phone book to store just a few phone numbers - they waste a lot of space. Most cells contain zeros because in real networks, each vertex is only connected to a few others. Instead, it's better to use adjacency lists, which are like having each person keep their own contact list of just their friends, saving both space and time.

Think of graph directionality like different types of relationships. In undirected graphs, connections work both ways - like friendship on Facebook where if you're friends with someone, they're also friends with you. These two-way relationships are shown as simple lines between vertices.

In contrast, directed graphs (or digraphs) have one-way connections - like following someone on Twitter where you can follow them, but they might not follow you back. These one-way relationships are shown as arrows pointing from one vertex to another. The vertex where the arrow starts is called the source, and where it ends is the destination.

This difference in directionality affects how we work with graphs. In undirected graphs, we can travel along any edge in either direction , but in directed graphs, we can only follow the arrows in their specified direction. This is important when finding paths or checking if vertices are connected - just because you can reach vertex B from vertex A doesn't mean you can get back to A from B in a directed graph.

Think of weighted graphs like a map where each road (edge) has additional information attached to it. Just like how roads have distances, speed limits, or toll costs, weighted graphs assign values to their connections. These weights could represent anything measurable, like miles between cities, minutes to travel, or dollars to spend.

# Building an adjacency list for directed weighted graph (one-way edge)
def directedGraph(edges: List[List[int]]) -> Dict[int, List[int]]:
    hashmap = defaultdict(list)
    for source, destination, weight in edges:
        hashmap[source].append((destination, weight))
    return hashmap

# Building an adjacency list for undirected weighted graph (two-way edge)
def undirectedGraph(edges: List[List[int]]) -> Dict[int, List[int]]:
    hashmap = defaultdict(list)
    for source, destination, weight in edges:
        hashmap[source].append((destination, weight))
        hashmap[destination].append((source, weight))
    return hashmap

Weighted graphs help solve real-world problems like finding the shortest route between two locations or building the cheapest network of connections. The weights can be any number - even negative in some special cases- and they completely change how we approach the problem. Instead of just finding any path between two points, we now need to consider the total weight of the path to find the optimal route.

A cycle in a graph is like a circular path where you can start at any point and follow the connections until you return to where you started. Think of it like visiting different friends' houses and eventually returning to the first friend's house. These cycles are important because they often represent patterns or dependencies in our graph.

Cycles behave differently in directed and undirected graphs. In undirected graphs, cycles are easier to detect because we can move in any direction. In directed graphs, cycles are trickier because we must follow the direction of the arrows. We often detect cycles in directed graphs using topological sorting, which fails if there's a cycle because you can't create a valid ordering when nodes depend on each other in a loop.

class Graph:
    def hasCycle(self, nodes: int, edges: List[List[int]]) -> bool:
        # Base case: If there are no edges, return False - no cycles
        if not edges:
            return False
        
        # Create an adjacency list for directed graph
        hashmap = defaultdict(list)
        for source, destination in edges:
            hashmap[source].append(destination)

        # Sets for detecting cycles
        cycle = set()
        visit = set()

        # DFS function to detect cycles
        def dfs(node: int) -> bool:
            if node in cycle:  # Cycle detected
                return True
            if node in visit:  # Node already processed
                return False

            # Mark the node as part of the current path
            cycle.add(node)
            for neighbor in hashmap[node]:
                if dfs(neighbor):  # Cycle found in neighbor
                    return True
            cycle.remove(node)
            visit.add(node)  # Mark as fully processed
            return False
        
        # Run DFS for each node
        for source in range(nodes):
            if dfs(source):
                return True
        return False

One common way to find cycles is using a depth-first search that keeps track of nodes we're currently visiting. If we encounter a node we're already visiting, we've found a cycle because we've circled back to a node on our current path. This is useful for task scheduling, where cycles would create deadlocks, or in dependency management, where circular dependencies need to be avoided.

Graphs are incredibly flexible data structures that can represent complex relationships which is why they are popular in coding interviews. Here are some essential tips and tricks for solving graph-related questions: