Skip to content
Hello Python

Build Graph Representations

Practice ExerciseIntermediateMediumAdjacency ListAdjacency MatrixGraph

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement build_graph_representations(node_count, edges). Nodes are 0..node_count-1 and edges are undirected [u, v] pairs. Ignore duplicate edges, preserve self-loops once, sort every neighbor list, and return [adjacency_list, adjacency_matrix].

Starter code

def build_graph_representations(node_count, edges):
    pass
Test cases

path-graph

{
  "args": [
    3,
    [
      [
        0,
        1
      ],
      [
        1,
        2
      ]
    ]
  ]
}

Expected: [[[1],[0,2],[1]],[[0,1,0],[1,0,1],[0,1,0]]]

duplicates-loop

{
  "args": [
    2,
    [
      [
        0,
        1
      ],
      [
        1,
        0
      ],
      [
        1,
        1
      ]
    ]
  ]
}

Expected: [[[1],[0,1]],[[0,1],[1,1]]]

Wizard outline
  1. Step 1: Allocate graph shapes

    Create one empty neighbor set and one zero matrix row for every node. Allocating by node count preserves isolated nodes even when the edge list is empty.

  2. Step 2: Write one undirected edge

    Add each endpoint to the other neighbor set and mirror both matrix cells. One edge isolates the symmetry rule shared by adjacency lists and matrices.

  3. Step 3: Accumulate a path of edges

    Process every edge without replacing neighbor state from earlier iterations. A path confirms that one node can accumulate multiple neighbors across commands.

  4. Step 4: Normalize duplicates and self-loops

    Rely on sets and binary matrix cells so duplicates collapse and a self-loop appears once. Idempotent storage completes the contract for reversed duplicates and self-loops.

Footguns and prerequisites
  • Adding only u to v accidentally creates a directed representation.
  • A self-loop should not be appended twice when mirroring an undirected edge.
  • trees and graphs
Reviewed references
Recommended approach and implementation

Accumulate canonical neighbors in per-node sets while writing symmetric matrix cells, then sort each set for deterministic output.

Why it works: For every input edge both endpoints receive each other and both matrix directions become one. Set insertion removes duplicates and preserves a self-loop once, so the returned structures encode exactly the same undirected graph.

def build_graph_representations(node_count, edges):
    adjacency = [set() for _ in range(node_count)]
    matrix = [[0 for _ in range(node_count)] for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].add(right)
        adjacency[right].add(left)
        matrix[left][right] = 1
        matrix[right][left] = 1
    return [[sorted(neighbors) for neighbors in adjacency], matrix]