1. Depth-First Search

☔️ Time complexity

O(V + E)

• V: number of vertices
• E: number of edges

🎀 Usage

• count connected components
• determine connectivity
• find bridges/articulation points

🪐 Description

DFS goes through the graph depth-first without regard for which edge it takes next until it cannot go any furhter. When it can't go any further, it backtracks and continues.

🌻 Process

1. Start at node 0
2. Arbitrarily pick one of the connected nodes as next node (ex) node 9
3. Repeat step 2 until revisit a visited node or a dead end
4. When revisiting a visited node or visiting a dead end, backtrack to the initial node of the cycle
5. Back to step 2

🪵 Pseudocode

n = number of nodes in graph
g = adjacency list representing graph
visited = [false] * n # all false since none of the nodes is visited

function dfs(at): 
	if visited[at]: return # check if node is already visited
    visited[at] = true # if not visited, set to true
    
    # dfs for all neighboring nodes
    neighbors = graph[at]
    for next in neighbors:
    	dfs(next)

# Start DFS at node zero
start_node = 0
dfs(start_node)

🤸🏼 Finding connected components

Connected components: sometimes a graph is split into multiple copmonents

1. Make sure all nodes are labeled from [0, n) where n is the number of nodes
   2

2. Start DFS at every node except if the node is visited
   Mark all reachable nodes as being part of the same component (same id label)

Pseudocode

n = number of nodes in the graph 
g = adjaceny list representing graph 
count = 0 # tracks number of connected components
components = empty integer array of size n # integer array that holds the integer value of which component a node belongs to
visited = [false] * n # all false since none of the nodes is visited

function findComponents():
	for i in range(n):
    	if not visited[i]: # check if node is visited & simply skip if already visited (no backtracking)
        	count ++
            dfs(i) # execute dfs for every unvisited node
	return (count, components)

function dfs(at):
	visited[at] = true
    components[at] = count
    for next in g[at]:
    	if !visited[next]:
        	dfs(next)

2. Breadth First Search

🧇 Time complexity

O(V + E)

• V: number of vertices in graph
• E: number of edges in graph

🛴 Usage

• find shortest path on unweighted graphs

🇰🇷 Description

1. Starts at some arbitrary node
2. Explores the neighbor nodes, before moving to the next level neighbors

💌 Using a queue

Use a queue data structure to track which node to visit next.
Upon reaching a new node the algorithm adds it to the queue to visit it later

1. Keep a queue of starter node and add the starter node's all neighbors to the queue

2. Move onto next node in queue and add the node's all neighbors to the queue

3. If next node is already in the queue, skip it

4. Repeat until we run out of nodes

🐣 Pseudocode

n = number of nodes in the graph
g = adjacency list representing unweighted graph

# s = start node, e = end node, 0 <= e, s, < n
# returns the shortest path of nodes from s to e
function bfs(s, e):
	prev = solve(s)
    return reconstructPath(s, e, prev)

function solve(s): 
	# initialize queue data structure
    q = queue data structure
    q.enqueue(s)
    
    visited = [false]*n 
    visited[s] = true
    
    prev = [null]*n
    while !q.isEmpty():
    	node = q.dequeue()
        neighbors = g.get(node)
        
        for next in neighbors:
        	if !visited[next]:
            	q.enqueue(next)
                visited[next] = true
                prev[next] = node
	return prev

function reconstructPath(s, e, prev):
	
    # Reconstruct path going backwards from e
    path = []
    for (at = e; at != null, at = prev[at]):
    	path.add(at)
    
    path.reverse() # necessary because we reconstructed path backwards
    
    # if s and e are connected, return the path
    if path[0] == s:
    	return path
    return []
    

---

https://www.youtube.com/watch?v=7fujbpJ0LB4&t=261s