Oct 17, 2024
Graphs are a fundamental data structure used to model pairwise relations between objects. They consist of vertices (or nodes) and edges (or arcs) that connect pairs of vertices. Graphs can be directed or undirected, weighted or unweighted, and can have cycles or be acyclic.
Types of Graph Representation
Adjacency Matrix:
- A 2D array where the element at row
iand columnjindicates the presence of an edge between vertexiand vertexj. - Suitable for dense graphs.
- Example:
# Adjacency Matrix Representation
graph = [
[0, 1, 0, 0],
[1, 0, 1, 1],
[0, 1, 0, 1],
[0, 1, 1, 0]
]
Weighted Adjacency Matrix:
- A 2D array where the element at row
iand columnjindicates the weight of the edge between vertexiand vertexj. A value of0orNonecan indicate no edge. - Example:
# Weighted Adjacency Matrix Representation
graph = [
[0, 2, 0, 0],
[2, 0, 3, 1],
[0, 3, 0, 4],
[0, 1, 4, 0]
]
Adjacency List:
- An array of lists. The index represents the vertex, and each element in the list represents the vertices adjacent to it.
- Suitable for sparse graphs.
- Example:
# Adjacency List Representation
graph = {
0: [1],
1: [0, 2, 3],
2: [1, 3],
3: [1, 2]
}
Weighted Adjacency List:
- An array of lists where each list contains tuples. The index represents the vertex, and each tuple in the list represents an adjacent vertex and the weight of the edge connecting them.
- Suitable for sparse graphs with weighted edges.
- Example:
# Weighted Adjacency List Representation
graph = {
0: [(1, 2)],
1: [(0, 2), (2, 3), (3, 1)],
2: [(1, 3), (3, 4)],
3: [(1, 1), (2, 4)]
}
Edge List:
- A list of all edges in the graph, where each edge is represented as a pair of vertices.
- Useful for algorithms that require edge-centric operations.
- Example:
# Edge List Representation
edges = [
(0, 1),
(1, 2),
(1, 3),
(2, 3)
]
Weighted Edge List:
- A list of all edges in the graph, where each edge is represented as a tuple containing two vertices and the weight of the edge.
- Useful for algorithms that require edge-centric operations with weights, such as Kruskal's algorithm for finding the Minimum Spanning Tree.
- Example:
# Weighted Edge List Representation
edges = [
(0, 1, 2),
(1, 2, 3),
(1, 3, 1),
(2, 3, 4)
]
Pros and Cons of Different Graph Representations
Adjacency Matrix
- Pros:
- Simple and easy to implement.
- Efficient for dense graphs where the number of edges is close to the maximum number of edges.
- Constant time complexity O(1) for checking the existence of an edge between two vertices.
- Cons:
- Requires O(V^2) space, which can be inefficient for large, sparse graphs.
- Iterating over all edges takes O(V^2) time, which is inefficient for sparse graphs.
Adjacency List
- Pros:
- More space-efficient for sparse graphs, requiring O(V + E) space.
- Faster iteration over all edges, taking O(V + E) time.
- Cons:
- Checking the existence of a specific edge can take O(V) time in the worst case.
- Slightly more complex to implement compared to an adjacency matrix.
Edge List
- Pros:
- Very space-efficient for storing edges, especially in sparse graphs.
- Simple to implement and understand.
- Useful for algorithms that are edge-centric, such as Kruskal's algorithm.
- Cons:
- Checking the existence of an edge can be slow, requiring O(E) time.
- Not efficient for algorithms that require quick access to all neighbors of a vertex.
Each representation has its own strengths and weaknesses, and the choice of which to use depends on the specific requirements of the problem at hand, such as the density of the graph and the types of operations that need to be performed.
Coding Interview Questions
In the questions below we assume that the graph is represented as an adjacency list. Example:
graph = {
0: [1],
1: [0, 2, 3],
2: [1, 3],
3: [1, 2]
}
Graph Traversal:
- Problem: Implement Depth-First Search (DFS) and Breadth-First Search (BFS) for a given graph.
- Solution: assuming the graph is represented an adjacency list
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in graph[start]:
if next not in visited:
dfs(graph, next, visited)
return visited
def bfs(graph, start):
visited = set()
queue = [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(set(graph[vertex]) - visited)
return visited
Cycle Detection for Directional Graph:
- Problem: Determine if a cycle exists in a given directional graph. In a directional graph, we can travel from A to B does not mean we can travel from B to A.
- Main Idea: Use depth-first search (DFS) to detect cycles by tracking visited nodes and recursion stack.
- Solution: assuming the graph is a uni-directional graph represented as an adjacency list
def has_cycle(graph):
def visit(vertex, visited, rec_stack):
visited.add(vertex)
rec_stack.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
if visit(neighbor, visited, rec_stack):
return True
elif neighbor in rec_stack:
return True
rec_stack.remove(vertex)
return False
visited = set()
rec_stack = set()
for node in graph:
if node not in visited:
if visit(node, visited, rec_stack):
return True
return False
Cycle Detection for Bidirectional Graph:
-
Explanation: In a bidirectional graph, each edge is a two-way connection, meaning if there is an edge from node A to node B, there is also an edge from node B to node A. Detecting cycles in such graphs requires careful handling to avoid counting the bidirectional nature of edges as cycles. The approach involves using DFS while keeping track of the parent node to ensure that we do not revisit the immediate predecessor node, which would otherwise falsely indicate a cycle.
-
Solution: assuming the graph is a bidirectional graph represented as an adjacency list
def has_cycle_bidirectional(graph):
def visit(vertex, visited, parent):
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
if visit(neighbor, visited, vertex):
return True
elif parent is not None and neighbor != parent:
return True
return False
visited = set()
for node in graph:
if node not in visited:
if visit(node, visited, None):
return True
return False
This solution uses a DFS approach similar to the unidirectional graph but includes an additional parent parameter to track the node from which we arrived at the current node. This prevents the algorithm from mistakenly identifying the bidirectional nature of edges as cycles.
Shortest Path for Unweighted Graph:
- Problem: Find the shortest path between two nodes in an unweighted graph.
- Main Idea of Solution: The solution uses a breadth-first search (BFS) approach to explore all possible paths from the start node. It systematically checks each path until it finds the shortest path to the goal node.
- Solution:
from collections import deque
def shortest_path(graph, start, goal):
queue = deque([(start, [start])])
while queue:
(vertex, path) = queue.popleft()
for next in graph[vertex] - set(path):
if next == goal:
return path + [next]
else:
queue.append((next, path + [next]))
return None
Shortest Path for Weighted Graph:
-
Problem: Find the shortest path between two nodes in a weighted graph.
-
Main Idea of Solution: The solution uses Dijkstra's algorithm, which is a well-known algorithm for finding the shortest paths between nodes in a graph with non-negative edge weights. The algorithm maintains a priority queue to explore the nodes in the order of their current shortest distance from the start node. It updates the shortest path to each node as it explores the graph.
-
Solution: The solution below assumes that the graph is stored in a weighted adjacency list.
import heapq
def dijkstra(graph, start, goal):
# Priority queue to store (distance, vertex) tuples
queue = [(0, start)]
# Dictionary to store the shortest path to each node
distances = {start: 0}
# Dictionary to store the path taken to reach each node
previous_nodes = {start: None}
while queue:
current_distance, current_vertex = heapq.heappop(queue)
# If we reach the goal, reconstruct the path
if current_vertex == goal:
path = []
while current_vertex is not None:
path.append(current_vertex)
current_vertex = previous_nodes[current_vertex]
return path[::-1]
# Explore neighbors
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
# If a shorter path to the neighbor is found
if neighbor not in distances or distance < distances[neighbor]:
distances[neighbor] = distance
previous_nodes[neighbor] = current_vertex
heapq.heappush(queue, (distance, neighbor))
return None
This solution uses Dijkstra's algorithm to efficiently find the shortest path in a weighted graph. It leverages a priority queue to always expand the least costly node first, ensuring that the shortest path is found. The algorithm also keeps track of the path taken to reconstruct the shortest path once the goal node is reached.
Ming Dao School uses 1-1 coaching and group events to help high-tech professionals grow their careers and handle career transitions.
If you like to join our upcoming mock system design interview events or other coaching programs, please contact us on LinkedIn.