Graph from Adjacency List + BFS

Adjacency List (directed weighted, weight in brackets)

• A → B(10), C(3)
• B → C(1), D(5)
• C → B(4), D(8), E(2)
• D → E(7)
• E → D(9)

(i) Graph Drawing (description)

Vertices A-E.
Edges: A→B (10), A→C (3), B→C (1), B→D (5), C→B (4), C→D (8), C→E (2), D→E (7), E→D (9). It's directed; no edge into A. Strongly connected component {B,C,D,E} partially.

If sketched: A at top, arrows to B (right) and C (middle); B to C (down-left, 1) and D; C to B (up), to D (right), to E (down); D⟷E bidirectional with weights 7/9.

(ii) BFS Algorithm (as in Q92)

BFS(G, s):
  for v in V: visited[v]=false, dist[v]=∞
  Q=queue(); visited[s]=true; dist[s]=0; enqueue(s)
  order=[]
  while Q not empty:
    u=dequeue()
    order.append(u)
    for v in Adj[u] (in list order):
      if not visited[v]:
        visited[v]=true; dist[v]=dist[u]+1; parent[v]=u; enqueue(v)

Time $O(V+E)$, space $O(V)$. BFS ignores weights (treats as unweighted for traversal order); for weighted shortest paths use Dijkstra.

(iii) BFS Traversal Starting A (assuming adjacency order as listed)

• Init Q=[A], visited {A}, order []
• Dequeue A → order [A]; neighbors B,C not visited → enqueue B,C → Q=[B,C]
• Dequeue B → order [A,B]; neighbors C (already visited), D not visited → enqueue D → Q=[C,D]
• Dequeue C → order [A,B,C]; neighbors B already, D already, E not visited → enqueue E → Q=[D,E]
• Dequeue D → order [A,B,C,D]; neighbor E already visited (via C) → Q=[E]
• Dequeue E → order [A,B,C,D,E]; neighbor D already visited → Q=[] done.

BFS order: A → B → C → D → E
Distances (edges): dist[A]=0, dist[B]=1, dist[C]=1, dist[D]=2 (via B), dist[E]=2 (via C).

Parent tree: parent[B]=A, parent[C]=A, parent[D]=B, parent[E]=C.

If adjacency order C before B, order would be A,C,B,E,D etc but standard given order yields A,B,C,D,E. BFS levels: L0 {A}, L1 {B,C}, L2 {D,E}.