Graphs and Adjacency Representations

Vertices, also called nodes, represent entities, while edges or arcs represent relationships. An undirected edge joins two vertices symmetrically; a directed edge has a source and destination. A weight can represent distance, cost or another quantity whose meaning and units must be stated.

Two towns may have a directed travel link because one route is one-way. A social graph might use directed follows or undirected mutual friendships; neither is automatically correct without the problem’s definitions. A graph may contain cycles, unlike a tree.

An adjacency matrix allocates a row and column for each vertex. A Boolean entry can show whether an edge exists; a weighted version can store costs. For an undirected graph, corresponding entries on either side of the main diagonal match when the same convention is used.

Represent absence explicitly. Zero cannot safely mean no edge if zero-cost edges are permitted. A matrix uses space proportional to V², even when few edges exist, but checking a particular pair’s entry is constant time with indexed storage.

An adjacency list associates each vertex with its neighbours, optionally alongside weights. For an undirected graph, store a connection at both endpoints. Space is proportional to vertices plus stored edges, making lists attractive for sparse graphs.

Finding every neighbour is efficient because only existing connections need be visited. Checking one arbitrary edge may require searching a neighbour list unless a set or another indexed structure is used. A representation comparison should mention the operations the application actually performs, not just that one structure “is faster”.

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.