Graphs

Graphs are a non-linear data structure composed of nodes and edges. The edges connect nodes/vertices together to represent the complex structure between elements. For example, it can picture the relation between friends or the distance between locations

Graph Representations

In algorithm questions for graphs you are usually given two different represenations:

1. A list of edges, usually in the form of [(n1, n2), (n2, n3)].
2. A 2D matrix where the cells are nodes and each node can travel to its adjacent cell (node)

Graph search algorithms:

• Depth First Search, Breadth First Search
• Topological Sort, Dijkstra's Algorithm
• [[#Union Find]]

When processing a graph using DFS/BFS that contains cycles, it is important to keep track of the visited nodes.

Types of Graphs

• Undirected graphs - edges do not have a specified direction, the connection between two nodes is bidirectional
• Directed graphs - edges have a single defined direction
• Weighted graphs - edges have a "weight" or a "cost" to them

Adjacency List

If you are given a list of edges, you need to transform this into an adjacency list. This is usually done using a Hash Map with a node as the key and the value being a list of the edges it is connected to.

adjList = {i: [] for i in range(numVertices)}
for u, v in edges:
	adjList[u].append(v)
	adjList[v].append(u) # -> only for undirected edges

visit = set()
def dfs(node)
	if node in visit:
		return False
	visit.add(crs)
	for neighbour in adjList[node]:
		dfs(neighbour)	

For the above, you have to think about the base cases and how to process the dfs part for each specific problem.

Union Find

Union find is a data structure that manages a collection of disjoint sets.

It has two primary functions:

1. Union: join two sets together
2. Find: finds the parent of the element

n = len(problem) # provide the length of number of nodes here
par = [i for i in range(n)] # let each node be its own parent
rank = [1] * n # the rank (depth of node)
  
def union(a1, a2):
	p1, p2 = find(a1), find(a2)
	if p1 == p2:
		return False
	
	# on union, attach to the root node with higher rank
	# increase rank appropriately
	if rank[p1] > rank[p2]:
		par[p2] = p1
		rank[p1] += rank[p2]
	else:
		par[p1] = p2
		rank[p2] += rank[p1]
	return True

def find(a1):
	p = par[a1]
	while p != par[p]:
		# path compression, make p point to graindparent 
		par[p] = par[par[p]] 
		p = par[p]
	return p