Graphs are powerful data structures used to model relationships between pairs of objects. They consist of nodes (vertices) and connections (edges). Python allows flexible and efficient implementations of both directed and undirected graphs.
📌 Graph Representation (Adjacency List)
python
from collections import defaultdict
class Graph:
def __init__(self, directed=False):
self.graph = defaultdict(list)
self.directed = directed
def add_edge(self, u, v):
self.graph[u].append(v)
if not self.directed:
self.graph[v].append(u)
🔍 Depth-First Search (DFS)
python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=" ")
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
🔄 Breadth-First Search (BFS)
python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
print(node, end=" ")
visited.add(node)
queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)
🛣️ Shortest Path using BFS (Unweighted Graph)
python
def shortest_path(graph, start, end):
visited = set()
queue = deque([(start, [start])])
while queue:
current, path = queue.popleft()
if current == end:
return path
for neighbor in graph[current]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None
🔁 Cycle Detection (Undirected Graph using DFS)
python
def has_cycle(graph):
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True
return False
for vertex in graph:
if vertex not in visited:
if dfs(vertex, None):
return True
return False
🧪 Sample Usage
python
g = Graph(directed=False)
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
for u, v in edges:
g.add_edge(u, v)
print("DFS: ", end="")
dfs(g.graph, 0)
print("\nBFS: ", end="")
bfs(g.graph, 0)
print("\nShortest path from 0 to 3:", shortest_path(g.graph, 0, 3))
print("Cycle detected?" , has_cycle(g.graph))
📝 Summary
OperationDescriptionDFSDepth-first traversal using recursionBFSBreadth-first traversal using a queueShortest PathBFS-based shortest path for unweighted graphsCycle DetectionDFS-based method for undirected graph cycle detection
Graphs are foundational in computer science and widely used in real-world applications like networks, maps, and recommendation systems.