Matrix

• Essentially a 2D array
• Can be used to represent a graph
• Common
• Each item is a node
• Index represents row and col [row, col]

matrix = [[0, 0, 0, 0],
		  [0, 0, 0, 0],
		  [0, 0, 0, 0],
		  [0, 0, 0, 0]]

Adjacency Matrix

• Dimensions represent a node
• Usually a square

adjMatrix = [[0, 0, 0, 0],
		  [1, 0, 0, 0],
		  [0, 0, 0, 0],
		  [0, 0, 0, 0]]

• adjMatrix[v1][v2] = 1 means an edge exists from v1 to v2
• adjMatrix[v2][v1] = 1 means an edge exists from v2 to v1
• Index represents v1 and v2
• Usually represents directed graphs
• Space complexity $O(V^2)$

Adjacency List

• Common

class GraphNode:
	def __init__(self, val):
		self.val = val
		self.neighbors = []

• Space complexity $O(V)$
• Can be stored as a hashmap

adjList = {"A": [], "B": []}

Topological Sorting

• Sequence of each node in a graph
• Valid topological ordering is:
  • every edge has to be directed
  • every source node comes before destination node
  • first element is guaranteed to be the first
  • last element is guaranteed to be the last
• Only works for (DAG)
  • directed
  • acyclical
  • graph
• Works on non connected graphs
• Lot of possible valid orderings
• Can be done via DFS and BFS
• Regular DFS will not work because we need to make sure that we have added all incoming nodes before we add the current node
  • One way to fix it is to reverse the graph and then do a post order traversal
  • Another way: Run Post order DFS and reverse the result at the end

visited = set()  # Regular visit hashset
path = set()  # To check if a node is in the current DFS path (used for cycle detection)
topological_order = []  # Stack to store the topological order

def topologicalSortDFS(node):
    # Cycle detected
    if node in path:
        return True
    
    if node in visited:
        return False
    
    visited.add(node)
    path.add(node)  # Add the node to the current path
    
    for neighbor in adjacencyList[node]:
        if topologicalSortDFS(neighbor):  # If cycle is detected in recursive call
            return True
    
    path.remove(node)  # Remove the node from the current path after processing
    topological_order.append(node)  # Add the node to topological order in postorder
    
    return False  # No cycle found for this path

topological_order.reverse() # needed

Union Find

• The algorithm to find the number of connected / disjoint graphs
• Also used for cycle detection
• Usually DFS can achieve the same thing but sometimes you need to specifically use Union Find
• Forest of Trees
• Path compression or Union by rank will make $O(N)$ to $O(logn)$
  • If both are done then on average it can be simplified to $O(1)$
• Total union-find on a graph can be reduced to $O(E)$

class UnionFind:
    def __init__(self, n):
        self.nodesParent = list(range(n))
        self.ranking = [0] * n

    def find(self, node):
        """
        Uses path compression to make future queries faster.
        Time: O(α(N)), where α(N) is the inverse Ackermann function.
        """
        if self.nodesParent[node] != node:
            self.nodesParent[node] = self.find(self.nodesParent[node])
        return self.nodesParent[node]

    def union(self, node1, node2):
        """
        Uses union by rank to merge sets efficiently.
        Time: O(α(N)), where α(N) is the inverse Ackermann function.
        """
        parentOfNode1, parentOfNode2 = self.find(node1), self.find(node2)

        if parentOfNode1 == parentOfNode2:
            return False

        if self.ranking[parentOfNode1] > self.ranking[parentOfNode2]:
            self.nodesParent[parentOfNode2] = parentOfNode1
        elif self.ranking[parentOfNode1] < self.ranking[parentOfNode2]:
            self.nodesParent[parentOfNode1] = parentOfNode2
        else:
            self.nodesParent[parentOfNode1] = parentOfNode2
            self.ranking[parentOfNode2] += 1

        return True

Dijkstra's

• Useful to find shortest find
• BFS is good but it does not work when you have a weighted graph
• Used with a Min Heap and maintains the smallest cost for each node
• Time complexity $E(logV)$

def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
  edges = collections.defaultdict(list)
  for src, dest, weight in times:
    edges[src].append((dest, weight))

  minHeap = [(0, k)]
  visit = set()
  t = 0
  while minHeap:
    w1, n1 = heapq.heappop(minHeap)
    if n1 in visit:
      continue
    visit.add(n1)
    t = w1

    for n2, w2 in edges[n1]:
      if n2 not in visit:
        heapq.heappush(minHeap, (w1 + w2, n2))
  return t if len(visit) == n else -1

Prim's (Minimum Spanning Tree)

• Undirected graph
• Used to find minimum spanning tree
  • Creating a tree such that the cost is minimized
  • No cycles
  • Connect everything
  • Minimize the cost
• If we have N nodes then we would need N-1 edges if we do not have a cycle
  • if V == E then there is a cycle
• Multiple valid solutions can be present for a minimum spanning tree
• Almost the same as Dijkstra's
• We can start at any nodes
• Built with visited and minHeap

def minCostConnectPoints(self, points: List[List[int]]) -> int:
        adj = defaultdict(list)

        for i in range(len(points)):
            for j in range(len(points)):
                if i == j:
                    continue
                
                iPoint = points[i]
                jPoint = points[j]
                distance = abs(iPoint[0] - jPoint[0]) + abs(iPoint[1] - jPoint[1])

                adj[(iPoint[0], iPoint[1])].append((distance, jPoint[0], jPoint[1]))
                adj[(jPoint[0], jPoint[1])].append((distance, iPoint[0], iPoint[1]))
        
        minimumCost = 0
        minheap = [(0, points[0][0], points[0][1])]
        visited = set()

        while minheap:
            distance, x, y = heapq.heappop(minheap)

            if (x, y) in visited:
                continue
            
            visited.add((x, y))
            # here you can add the current node to the tree
            # and thats your minimum spanning tree
            minimumCost += distance 

            for neighborDistance, neighborX, neighborY in adj[(x, y)]:
                if (neighborX, neighborY) not in visited:
                    heapq.heappush(minheap, (neighborDistance, neighborX, neighborY))

        return minimumCost

Kruskal's

• Uses Union Find algorithm
• Add the next minimum edge that does not create a cycle

def minimumSpanningTree(edges, n):
	minHeap = []
	for n1, n2, weight in edges:
		heapq.heappush(minHeap, [weight, n1, n2])
	mst = []
	while len(mst) < n - 1:
		_, n1, n2 = heapq.heappop(minHeap)
		if not union(n1, n2):
			continue
		mst.append((n1, n2))
	return mst

Bellman Ford

• Can be useful when Dijkstra will not work because we have another restriction like at most k stops
• Bellman Ford allows to search for something within K stops
• Time: $O(E\ast V)$
  • We loop over the whole graph K times if there are restrictions
• Can deal with negative weights
• Searches level by level
• Iterating over each edge does not change the complexity much but makes the code much readable

def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
	cost = [float("inf")] * n
	cost[src] = 0

	for _ in range(k + 1):
		temp = cost.copy()

		for frm, to, price in flights:
			if cost[frm] == float("inf"):
				continue
			if cost[frm] + price < temp[to]:
				temp[to] = cost[frm] + price
		cost = temp
	
	return -1 if cost[dst] == float("inf") else cost[dst]