Weighted Graphs

In unweighted graph, the adjacency list only stores neighbors, not edge values (weights). If your graph has weighted edges, you need to store that data too.

1️⃣ Representing Weighted Graphs

a) Adjacency List with Weights

Instead of storing just neighbors, store pairs (neighbor, weight):

graph = { 0: [(1, 5), (2, 3)], # edge 0→1 weight=5, 0→2 weight=3 1: [(0, 5), (3, 2)], 2: [(0, 3), (3, 7)], 3: [(1, 2), (2, 7)] }

Each node points to a list of tuples: (neighbor, edge_weight)

b) Adjacency Matrix with Weights

graph = [ [0, 5, 3, 0], [5, 0, 0, 2], [3, 0, 0, 7], [0, 2, 7, 0] ]

graph[i][j] = weight of edge from i to j

0 or inf means no edge.

2️⃣ BFS with Weighted Graph

BFS usually ignores weights (used for unweighted shortest path)

But you can access edge weights while traversing:

from collections import deque

def bfs_weighted(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
   
    while queue:
        node = queue.popleft()
        print(f"Visiting node {node}")
       
        for neighbor, weight in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                print(f"Edge {node}->{neighbor} with weight {weight}")
                queue.append(neighbor)

bfs_weighted(graph, 0)

3️⃣ DFS with Weighted Graph

DFS also works the same, just include weight info if needed:

def dfs_weighted(graph, node, visited=None):
    if visited is None:
        visited = set()
   
    visited.add(node)
    print(f"Visiting node {node}")
   
    for neighbor, weight in graph[node]:
        if neighbor not in visited:
            print(f"Edge {node}->{neighbor} with weight {weight}")
            dfs_weighted(graph, neighbor, visited)

dfs_weighted(graph, 0)

4️⃣ Key Notes

Aspect BFS / DFS

Weighted edges Can be stored in adjacency list or matrix Traversal order BFS ignores weights (level order), DFS ignores weights (depth-first) Shortest path Use Dijkstra (BFS-like) for weighted graphs Data structure Tuple (neighbor, weight) or matrix cell graph[i][j]

✅ Summary

Unweighted graphs → store only neighbors.

Weighted graphs → store (neighbor, weight) pairs in adjacency list or edge weights in matrix.

BFS/DFS can traverse weighted graphs, but they don’t automatically use weights; for weighted shortest paths, algorithms like Dijkstra or Bellman-Ford are needed.