# Adjacency List (most common)
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C', 'E'],
'E': ['D']
}
# Adjacency Matrix
nodes = ['A', 'B', 'C', 'D', 'E']
matrix = [[0]*5 for _ in range(5)]
edges = [('A','B'), ('A','C'), ('B','D'), ('C','D'), ('D','E')]
for u, v in edges:
i, j = nodes.index(u), nodes.index(v)
matrix[i][j] = matrix[j][i] = 1from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
print(bfs(graph, 'A')) # ['A', 'B', 'C', 'D', 'E']def dfs(graph, start):
visited = set()
result = []
def _dfs(node):
visited.add(node)
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
_dfs(neighbor)
_dfs(start)
return result
print(dfs(graph, 'A')) # ['A', 'B', 'D', 'C', 'E'] (order varies)def shortest_path(graph, start, end):
queue = deque([(start, [start])])
visited = {start}
while queue:
node, path = queue.popleft()
if node == end:
return path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None
print(shortest_path(graph, 'A', 'E')) # ['A', 'B', 'D', 'E'] or ['A', 'C', 'D', 'E']import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
heap = [(0, start)]
while heap:
dist, node = heapq.heappop(heap)
if dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return distances
# Weighted graph: {node: [(neighbor, weight), ...]}
weighted = {
'A': [('B', 1), ('C', 4)],
'B': [('C', 2), ('D', 5)],
'C': [('D', 1)],
'D': []
}
print(dijkstra(weighted, 'A'))
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}def topological_sort(graph):
in_degree = {node: 0 for node in graph}
for node in graph:
for neighbor in graph[node]:
in_degree[neighbor] += 1
queue = deque([n for n in in_degree if in_degree[n] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return result if len(result) == len(graph) else None
# DAG
DAG = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['D'],
'D': []
}
print(topological_sort(DAG)) # ['A', 'B', 'C', 'D'] or ['A', 'C', 'B', 'D']def has_cycle(graph):
visited = set()
rec_stack = set()
def _dfs(node):
visited.add(node)
rec_stack.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if _dfs(neighbor):
return True
elif neighbor in rec_stack:
return True
rec_stack.remove(node)
return False
for node in graph:
if node not in visited:
if _dfs(node):
return True
return FalseImplement: 1) `bfs(graph, start)` returning traversal list. 2) `dfs(graph, start)` returning traversal list. 3) `shortest_path(graph, start, end)` returning path list. 4) `dijkstra(graph, start)` returning distance dict (weighted graph with (neighbor, weight) tuples). 5) `topological_sort(graph)` for a DAG. 6) `has_cycle(graph)` for directed graphs. Create example graphs for each and demonstrate.