DSA Graph
Wednesday, June 18, 2025 8:05 PM
Unweighted Graph Traversal:
1. BFS: Starts by visiting an arbitrary node, relax its neighbors, visit the next layer of layer
of neighbors and release its neighbors.
a. Time Complexity O(V+E), Traversing to every node through every edge.
b. Space Complexity O(V), For the Visited Array
c. Procedures and Code:
Exercism Page 1
Ordering - Traversal: From the Root, Go from left to right of each layer (The visited
list) to the specified Node. e.g. 0 - 9 - 7 - 11 - 10 - 8 - 6 - 3 - 1.
Shortest - s.t path: The path from root to the node. Backtrack from the specify node
to the root is also used, use the edgeTo in the table. e.g. 0 - 9 - 10 - 1
2. DFS (Pre-order): Start from the node, release the neighbors. Visit the one with the
highest priority/order. Continue, if you reach a leaf or the node is already visited, back
track then visit the next one in the order.
a. Time Complexity: O (V + E)
b. Space Complexity: O (V)
c. Procedure and Code:
Exercism Page 2
Recursive Tree: (Note that this example dont a have specific priority.
Code:
# Global or class scope variables
n = number of nodes in the graph
g = adjacency list representing graph
visited = [False, ..., False] # size n
function dfs(at):
if visited[at]: return
Exercism Page 3
if visited[at]: return
visited[at] = True
neighbours = graph[at]
for next in neighbours:
dfs(next)
# Start DFS at node zero
start_node = 0
dfs(start_node)
Ordering - Traversal: 0 -9 - 8 - 7 - 10 - 11 - 3 - 2 - 4 - 5 - 6 - 1
Weighted Graph Traversal:
1. Dijkstra's Algorithm: Starts at a source node, always visits the closest unvisited node
(Use Min Heap), and then for each neighbor, it sums up the path cost to itself plus the
direct road cost to that neighbor. If this new total is cheaper than the neighbor's currently
known cost, it updates it, and repeats this process.
a. Time Complexity:
• Total Runtime: O((∣V∣ln(∣V∣) + ∣E∣)ln(∣V∣))
○ This is composed of:
▪ O(∣V∣ln(∣V∣)) for the ∣V∣ times we extract the closest vertex from the
priority queue (each extraction takes O(ln(∣V∣)) time from a queue of size
up to ∣V∣).
▪ O(∣E∣ln(∣V∣)) for processing all ∣E∣ edges, where each edge's relaxation
might involve an O(ln(∣V∣)) priority queue update.
○ Initial setup also contributes Θ(∣V∣) time, which is absorbed by the dominant
terms.
b. Space Complexity: O(V) to O(E+V), primarily influenced by the data structures used
for the priority queue and storing graph information.
c. Code and Procedure:
Exercism Page 4
Exercism Page 5
Code:
function shortest_path(graph, source, destination):
distances = map from node to infinity
distances[source] = 0
explored = empty set
heap = empty priority queue
push (0, source) into heap
while heap is not empty:
(current_distance, node) = extract_min from heap
if node is in explored:
continue
add node to explored
for each (connected_node, edge_weight) in graph[node]:
if connected_node is in explored:
continue
if distances[node] + edge_weight < distances[connected_node]:
distances[connected_node] = distances[node] + edge_weight
push (distances[connected_node], connected_node) into heap
return distances[destination]
d. Disadvantage:
• Cannot handle negative edge weights: Produces incorrect results.
• Does not detect negative cycles: Fails where infinite shortening of paths is possible.
• "Blind search": Explores all directions, inefficient for single-target paths in large
graphs (unlike A*).
• Can be slow for very large graphs: Even with optimizations, constant factors and log
terms add up.
• Not for all-pairs shortest paths: Designed for single-source only.
2. A-Star Method: Starts at a source node, and unlike Dijkstra's which always visits the
Exercism Page 6
2. A-Star Method: Starts at a source node, and unlike Dijkstra's which always visits the
closest unvisited node (Min Heap), A* always visits the unvisited node with the lowest
estimated total cost (f(A)). This total cost f(A) is calculated as the sum of its path cost
from the source (W(s,A)) plus an estimated cost (heuristic, h(A,dest)) to the destination.
Then, for each neighbor, it sums up the actual path cost to itself plus the direct road cost
to that neighbor, and if this new total is cheaper than the neighbor's currently known
cost, it updates it, and repeats this process, prioritizing nodes that seem promising for
reaching the destination quickly.
a. Time Complexity: Depends on the Heuristic, normally O(V+E).
b. Space Complexity: O(V), worst case for priority queue.
c. Code and Procedure:
function A_STAR(start, goal, heuristic):
Exercism Page 7
function A_STAR(start, goal, heuristic):
g_score[start] = 0
f_score[start] = heuristic(start, goal)
[Link]((f_score[start], start)) // (estimated_total_cost, node)
prev_node = {} // To reconstruct path
while PQ is not empty:
current_f, u = [Link]()
if u == goal:
return reconstruct_path(prev_node, u)
for each neighbor v of u:
tentative_g = g_score[u] + cost(u, v)
if tentative_g < g_score[v]:
g_score[v] = tentative_g
f_score[v] = g_score[v] + heuristic(v, goal)
prev_node[v] = u
[Link]((f_score[v], v))
return "No Path"
SUMMARIZE:
Minimum Spanning Tree:
1. Prim Optimized: Starts at an arbitrary node and always selects the unvisited node that can
be connected to the growing Minimum Spanning Tree (MST) with the cheapest edge
(using a Min Heap). Then, for each neighbor of the newly added node, it checks if the
Exercism Page 8
(using a Min Heap). Then, for each neighbor of the newly added node, it checks if the
direct edge cost to that neighbor is cheaper than its currently recorded minimum
connection cost to the MST. If a cheaper connection is found, it updates the neighbor's
connection cost and its parent in the MST, repeating this process until all nodes are part
of the MST.
2. Time Complexity:
3. Space Complexity:
4. Code and Procedures:
Exercism Page 9
Exercism Page 10
function PRIMS_MST(graph, start_vertex):
key = {vertex: infinity for vertex in [Link]()} // Min weight edge to MST
parent = {vertex: None for vertex in [Link]()} // Edge for MST construction
in_mst = {vertex: False for vertex in [Link]()} // Or check if in PQ
key[start_vertex] = 0
// Priority queue: (key_value, vertex)
PQ = PriorityQueue()
for v in [Link]():
[Link]((key[v], v))
while not [Link]():
min_key_value, u = [Link]() // Extract vertex with minimum key
in_mst[u] = True // Mark as included in MST
for v, weight in graph.get_neighbors(u): // Iterate through u's neighbors
// If v is not yet in MST and edge (u,v) is cheaper than current key[v]
if not in_mst[v] and weight < key[v]:
key[v] = weight
parent[v] = u
[Link]((key[v], v)) // Update priority (or re-insert with new priority)
return parent // parent array implicitly defines the MST edges
5. Kruskal Optimized: finds an MST by sorting all graph edges by weight from cheapest to
most expensive. Initially, every vertex is considered its own separate component. It then
iterates through the sorted edges. For each edge, it uses a Union-Find data structure to
determine if its two endpoints are already connected within the partial MST being built. If
the endpoints are not yet connected (i.e., they belong to different, disjoint components),
the edge is added to the MST, and their respective components are merged. This process
continues until all vertices are connected, forming the MST.
a. Time Complexity: O(|E| log |V|) or O(|E| log |E|)
b. Space Complexity: O(V + E)
c. Code and Procedure:
Exercism Page 11
c. Code and Procedure:
Exercism Page 12
Exercism Page 13
function KRUSKALS_MST(graph):
MST_edges = set()
all_edges = graph.get_all_edges() // Get all edges with their weights: [(u, v,
weight), ...]
all_edges.sort(key=lambda edge: edge[2]) // Sort edges by weight
// Initialize Disjoint Set Union (DSU)
parent = {v: v for v in [Link]()} // Each vertex is its own parent initially
rank = {v: 0 for v in [Link]()} // For union by rank optimization
function find(i): // Finds the representative (root) of the set containing i
if parent[i] == i:
return i
parent[i] = find(parent[i]) // Path compression
return parent[i]
function union(i, j): // Merges the sets containing i and j
root_i = find(i)
root_j = find(j)
if root_i != root_j:
// Union by rank
if rank[root_i] < rank[root_j]:
parent[root_i] = root_j
elif rank[root_i] > rank[root_j]:
parent[root_j] = root_i
else:
parent[root_j] = root_i
rank[root_i] += 1
return True // Union successful
return False // Already in the same set (cycle)
Exercism Page 14
for u, v, weight in all_edges:
if union(u, v): // Try to union u and v's sets
MST_edges.add((u, v, weight))
if len(MST_edges) == len([Link]()) - 1: // Optimization: MST has V-1 edges
break
return MST_edges
Exercism Page 15