How to build a graph of people where node connections are determined by name and age?

I was given the following question (please don't mind the programming language semantics, it's a language-agnostic question):

Given a list of Persons, and two arbitrary Persons out of that list, we need to find the minimum nth-degree relationship between them.

Here are the definitions of Person and a "relationship":

-
A Person is defined as having 2 properties: Name and Age:

class Person
{
    public string Name { get; set; }
    public int Age { get; set; }
}

-
A relationship between two Persons is defined as follows:

• Two Persons are considered to be in a 1st-degree relationship if they have either the same name or the same age.

• Two Persons are considered to be in a nth-degree relationship if they have n people of 1st-degree connecting them.

Example input:

Given the following list of Persons:

persons = [{ Name = "John", Age = 60 }, { Name = "John", Age = 50 }, { Name = "Ted", Age = 50 }]

Then:

• The two Johns have a 1st degree relationship (because they have the same name).

• The second John and Ted have a 1st degree relationship (because they have the same age).

• Hence, the first John and Ted have a 2nd degree relationship (because the second John connects them).

Now, I understand that it's a simple Dijkstra's algorithm question, but what I don't know is how should we build the graph of Persons?

I'm looking for an algorithm, but preferably code, that can build the graph in a time complexity which is better than $O(|V|^2)$.

If you think this question can be solved without building a graph (e.g., using BFS as mentioned in the comments), please let me know how can this be done, but I still want to know how to build the graph.

I assume you want to build the graph of all people, with edges between each pair of people at degree 1. Once you have this graph, it is straightforward to calculate the distance ("degree") between any two people using standard algorithms.

It's easy to build that graph in adjacency list format; or to store it implicitly and generate the adjacency lists on demand.

Store a hash table that maps from name to a list of all people with that name; and another hash table that maps from age to a list of all people with that age. Now, given one person, you can use the hash tables to quickly find all other people who have a first-degree relationship with that person, i.e., who are adjacent in the graph. This lets you build an adjacency list representation of the graph in $O(|V|+|E|)$ time, i.e., linear time rather than quadratic time.

Then, once you have this graph, you can compute distances using BFS in this graph. Note that you can construct the graph on-the-fly as you execute the BFS algorithm; you don't need to build the entire graph in advance.

Footnote: I'm treating hash table lookups as $O(1)$ time. This is a reasonable modelling assumption for practical work. For theoretical work, you can ensure that lookups take $O(1)$ expected time if you use an appropriate hash function, which is nearly as good for most practical purposes.

StackExchange Computer Science Q#130619, answer score: 4