Discover the power of graphs - one of the most versatile and widely used data structures in computer science. Learn about different graph representations and fundamental traversal techniques.
A graph is a data structure consisting of vertices (nodes) and edges that connect these vertices. Graphs are highly versatile and can represent many real-world relationships and networks.
An adjacency list is one of the most common ways to represent a graph. It uses an array or object where each vertex is associated with a list of its adjacent vertices (neighbors).
class Graph:
def __init__(self):
self.adjacency_list = {}
def add_vertex(self, vertex):
if vertex not in self.adjacency_list:
self.adjacency_list[vertex] = []
def add_edge(self, vertex1, vertex2):
# For undirected graph
self.adjacency_list[vertex1].append(vertex2)
self.adjacency_list[vertex2].append(vertex1)
def remove_edge(self, vertex1, vertex2):
self.adjacency_list[vertex1] = [v for v in self.adjacency_list[vertex1] if v != vertex2]
self.adjacency_list[vertex2] = [v for v in self.adjacency_list[vertex2] if v != vertex1]
def remove_vertex(self, vertex):
while self.adjacency_list[vertex]:
adjacent_vertex = self.adjacency_list[vertex].pop()
self.remove_edge(vertex, adjacent_vertex)
del self.adjacency_list[vertex]
An adjacency matrix is a 2D array where rows and columns represent vertices. The value at matrix[i][j] indicates if there is an edge from vertex i to vertex j.
class GraphMatrix:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
# Initialize matrix with zeros
self.matrix = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]
# Add edge for undirected graph
def add_edge(self, v1, v2):
# Set values to 1 to indicate an edge
self.matrix[v1][v2] = 1
self.matrix[v2][v1] = 1 # Remove this line for directed graph
# Add edge with weight
def add_weighted_edge(self, v1, v2, weight):
self.matrix[v1][v2] = weight
self.matrix[v2][v1] = weight # Remove this line for directed graph
# Remove edge
def remove_edge(self, v1, v2):
self.matrix[v1][v2] = 0
self.matrix[v2][v1] = 0 # Remove this line for directed graph
# Check if there is an edge between vertices
def has_edge(self, v1, v2):
return self.matrix[v1][v2] != 0
# Get all adjacent vertices of a vertex
def get_adjacent_vertices(self, v):
adjacent = []
for i in range(self.num_vertices):
if self.matrix[v][i] != 0:
adjacent.append(i)
return adjacent
Depth-First Traversal is an algorithm used to explore nodes and edges of a graph. It starts at a source node and explores as far as possible along each branch before backtracking.
class Graph:
# ... previous methods ...
def depth_first_traversal(self, start):
result =
visited = {}
# Helper function to perform recursive DFT
def dfs(vertex):
if not vertex:
return None
# Mark as visited and add to result
visited[vertex] = True
result.append(vertex)
# Visit all neighbors
for neighbor in self.adjacency_list[vertex]:
if neighbor not in visited:
dfs(neighbor)
# Start traversal
dfs(start)
return result
# Iterative implementation using stack
def depth_first_iterative(self, start):
stack = [start]
result =
visited = {start: True}
while stack:
current_vertex = stack.pop()
result.append(current_vertex)
for neighbor in self.adjacency_list[current_vertex]:
if neighbor not in visited:
visited[neighbor] = True
stack.append(neighbor)
return result
class Graph:
def __init__(self):
self.adjacency_list = {}
def add_vertex(self, vertex):
if vertex not in self.adjacency_list:
self.adjacency_list[vertex] = []
def add_edge(self, vertex1, vertex2):
self.adjacency_list[vertex1].append(vertex2)
self.adjacency_list[vertex2].append(vertex1)
def remove_edge(self, vertex1, vertex2):
self.adjacency_list[vertex1] = [v for v in self.adjacency_list[vertex1] if v != vertex2]
self.adjacency_list[vertex2] = [v for v in self.adjacency_list[vertex2] if v != vertex1]
def remove_vertex(self, vertex):
while self.adjacency_list[vertex]:
adjacent_vertex = self.adjacency_list[vertex].pop()
self.remove_edge(vertex, adjacent_vertex)
del self.adjacency_list[vertex]
class Graph:
# ... previous methods ...
def depth_first_traversal(self, start):
result =
visited = {}
adjacency_list = self.adjacency_list
def dfs(vertex):
if not vertex:
return None
visited[vertex] = True
result.append(vertex)
for neighbor in adjacency_list[vertex]:
if neighbor not in visited:
dfs(neighbor)
dfs(start)
return result
# Create a new graph
graph = Graph()
# Add vertices
graph.add_vertex("A")
graph.add_vertex("B")
graph.add_vertex("C")
graph.add_vertex("D")
# Add edges
graph.add_edge("A", "B")
graph.add_edge("A", "C")
graph.add_edge("B", "D")
graph.add_edge("C", "D")
# Perform DFS starting from vertexA
print(graph.depth_first_traversal("A"))
# Output: ["A", "B", "D", "C"]
Implement a graph class that supports both directed and undirected graphs using adjacency lists.
Implement a method to find if a path exists between two vertices using depth-first search.
Write a method to find all connected components in an undirected graph.
The following LeetCode collections are excellent resources for practicing graph problems and preparing for technical interviews.
Note: Previously, this course referenced the CodeSignal Arcade, which is no longer available. The LeetCode problems above follow the same principles and are an excellent alternative for practicing graph algorithms and preparing for technical interviews.