Master advanced graph operations including adjacency matrix, adjacency list, and various graph representations.
class GraphMatrix:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.matrix = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]
def add_edge(self, source, destination, weight=1):
# For directed graph
self.matrix[source][destination] = weight
# For undirected graph, uncomment the line below
# self.matrix[destination][source] = weight
def remove_edge(self, source, destination):
self.matrix[source][destination] = 0
# For undirected graph, uncomment the line below
# self.matrix[destination][source] = 0
def has_edge(self, source, destination):
return self.matrix[source][destination] != 0
def get_neighbors(self, vertex):
neighbors = []
for i in range(self.num_vertices):
if self.matrix[vertex][i] != 0:
neighbors.append(i)
return neighbors
class GraphList:
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, source, destination, weight=1):
if source not in self.adjacency_list:
self.add_vertex(source)
if destination not in self.adjacency_list:
self.add_vertex(destination)
# For weighted graph, store dicts with node and weight
self.adjacency_list[source].append({'node': destination, 'weight': weight})
# For undirected graph, uncomment the line below
# self.adjacency_list[destination].append({'node': source, 'weight': weight})
def remove_edge(self, source, destination):
if source in self.adjacency_list:
self.adjacency_list[source] = [edge for edge in self.adjacency_list[source] if edge['node'] != destination]
# For undirected graph, uncomment the block below
# if destination in self.adjacency_list:
# self.adjacency_list[destination] = [edge for edge in self.adjacency_list[destination] if edge['node'] != source]
def get_neighbors(self, vertex):
return [edge['node'] for edge in self.adjacency_list.get(vertex, [])]
| Operation | Adjacency Matrix | Adjacency List |
|---|---|---|
| Add Edge | O(1) | O(1) |
| Remove Edge | O(1) | O(E) |
| Check Edge | O(1) | O(E) |
| Get All Edges | O(V²) | O(V+E) |
Implement a function that converts an adjacency matrix to an adjacency list representation.
# Input adjacency matrix
matrix = [
[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
]
# Expected output adjacency list
adjacency_list = {
'0': [1, 3],
'1': [0, 2],
'2': [1, 3],
'3': [0, 2]
}
def matrix_to_list(matrix):
adj_list = {}
for i, row in enumerate(matrix):
adj_list[str(i)] = [j for j, val in enumerate(row) if val != 0]
return adj_list
print(matrix_to_list(matrix))
Implement a function that returns all vertices reachable from a given vertex in a directed graph.
Implement a function that calculates the density of a graph (ratio of actual edges to maximum possible edges).
For a directed graph with V vertices:
Density = Number of Edges / (V * (V-1))
For an undirected graph:
Density = (2 * Number of Edges) / (V * (V-1))
Note: Previously, this course referenced the CodeSignal Arcade for practice, which is no longer available. The LeetCode problems below follow the same principles and are excellent for practicing graph representations and algorithms.