Welcome to this comprehensive guide on Graph Problems Master List! In this lesson, we'll delve deep into the world of graph algorithms and problems, perfect for both beginners and intermediate learners. Let's get started!
Graphs are data structures used to represent relationships between objects. In the context of programming, we often use graphs to model networks, such as the internet or social media platforms.
A graph is composed of nodes (also known as vertices) and edges that connect these nodes. Each edge represents a relationship between the connected nodes.
There are three primary types of graphs:
Undirected Graph: Edges have no direction, meaning that if there's an edge between nodes A and B, there's also one between B and A.
Directed Graph: Edges have a direction, which means that if there's an edge between nodes A and B, there might not be one between B and A.
Weighted Graph: Each edge has a weight or cost associated with it.
Now that we've covered the basics of graphs, let's explore some common graph problems that you'll encounter when working with data structures and algorithms.
Depth-First Search is an algorithm for traversing or searching tree or graph structures. The algorithm starts at the root (or some arbitrary node of a connected component) and explores as far as possible along each branch before backtracking.
def dfs(node, graph):
# Mark the current node as visited.
graph[node] = True
# Recur for all the vertices adjacent to this vertex.
for i in graph[node]:
if not graph[i]:
dfs(i, graph)
# Example usage
graph = {'A': [ 'B', 'C' ],
'B': [ 'A', 'D', 'E' ],
'C': [ 'A', 'G' ],
'D': [ 'B' ],
'E': [ 'B', 'F' ],
'F': [ 'E' ],
'G': [ 'C' ]}
dfs('A', graph)Breadth-First Search is an algorithm for traversing or searching tree or graph structures. It starts at the tree root (or some arbitrary node of a connected component) and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.
def bfs(source, graph):
# Create a visited list to keep track of nodes we've visited.
visited = [False] * len(graph)
queue = [source]
while queue:
current = queue.pop(0)
# If we haven't visited the current node, mark it as visited and enqueue all its neighbors.
if not visited[current]:
visited[current] = True
for neighbor in graph[current]:
queue.append(neighbor)
# Example usage
graph = {'A': [ 'B', 'C' ],
'B': [ 'A', 'D', 'E' ],
'C': [ 'A', 'G' ],
'D': [ 'B' ],
'E': [ 'B', 'F' ],
'F': [ 'E' ],
'G': [ 'C' ]}
bfs('A', graph)A minimum spanning tree (MST) is a tree that connects all the vertices (nodes) together, without any cycles and with the minimum possible total edge weight.
In this example, we'll use Kruskal's algorithm, which is a popular algorithm for finding the minimum spanning tree of a graph.
def find_set(parent, i):
if parent[i] == i:
return i
return find_set(parent, parent[i])
def union(parent, rank, x, y):
x_root = find_set(parent, x)
y_root = find_set(parent, y)
# Perform union by making root of smaller tree as root of larger one.
if rank[x_root] > rank[y_root]:
parent[x_root] = y_root
elif rank[x_root] < rank[y_root]:
parent[y_root] = x_root
else:
parent[y_root] = x_root
rank[x_root] += 1
# Example graph with edge weights
edges = [(0, 1, 10), (0, 7, 5), (1, 2, 1), (1, 7, 2), (2, 3, 5),
(2, 6, 3), (2, 8, 8), (3, 6, 9), (3, 5, 7), (3, 8, 4),
(5, 6, 4), (6, 7, 2), (6, 8, 6), (7, 8, 1)]
# Initialize parent array and rank array
n = len(edges)
parent = list(range(n))
rank = [0] * n
edges.sort(key=lambda edge: edge[2]) # Sort the edges by weight.
for (x, y, w) in edges:
if find_set(parent, x) != find_set(parent, y):
union(parent, rank, x, y)
# The remaining edges form the minimum spanning tree.
mst_edges = [(x, y) for (x, y, w) in edges if find_set(parent, x) != find_set(parent, y)]What is the main purpose of Depth-First Search (DFS)?
What does Breadth-First Search (BFS) focus on when traversing a graph?
What is the goal of the Minimum Spanning Tree (MST) algorithm?