Given a map, or tree, of persons; how can you tell if two people are related? IE, do their ancestors trace back? And if so, how far back? Install an implementation in java.
The question reduces to graph traversal. A Person class holds a name, a list of parents, and any other fields the application needs. The tree is built from those objects, each one referring to its parent or parents. A method areRelated takes two Person objects and searches for a path between them.
Either traversal order works. Breadth-first search keeps a queue of nodes still to visit and marks visited nodes so that cycles do not trap the search. Depth-first search uses recursion or an explicit stack, again marking visited nodes. The traversal stops as soon as it reaches the second person. Recording the depth at which each node is reached gives the distance between the two in generations.
A basic implementation:
import java.util.*;
class Person {
String name;
List<Person> parents;
public Person(String name) {
this.name = name;
this.parents = new ArrayList<>();
}
}
public class AncestryChecker {
public boolean areRelated(Person person1, Person person2) {
if (person1 == person2) {
return true; // Same person, so they are related
}
// BFS traversal
Queue<Person> queue = new LinkedList<>();
Set<Person> visited = new HashSet<>();
queue.offer(person1);
visited.add(person1);
while (!queue.isEmpty()) {
Person current = queue.poll();
for (Person parent : current.parents) {
if (!visited.contains(parent)) {
if (parent == person2) {
return true; // Found a path connecting the two individuals
}
queue.offer(parent);
visited.add(parent);
}
}
}
return false; // No path connecting the two individuals
}
public static void main(String[] args) {
// Build the tree structure with Person objects
// Example usage
Person john = new Person("John");
Person jane = new Person("Jane");
Person alice = new Person("Alice");
Person bob = new Person("Bob");
Person charlie = new Person("Charlie");
john.parents.add(alice);
john.parents.add(bob);
jane.parents.add(alice);
jane.parents.add(bob);
charlie.parents.add(john);
charlie.parents.add(jane);
AncestryChecker checker = new AncestryChecker();
boolean related = checker.areRelated(alice, charlie);
System.out.println("Are Alice and Charlie related? " + related);
}
}
This is a starting point rather than a finished implementation. A larger or less regular tree structure may need changes to it.
Explain further how the algorithm traverses the map, and also how it can track how closely related two people are.
The code above performs a breadth-first traversal. In order:
person1) and mark it visited.current) and iterate over its parents list. Any parent not yet visited is marked and enqueued, and a depth can be recorded at the same time. If person2 turns up during this step, a path exists between the two, and the traversal returns true.person2, return false.BFS examines every node at one level before any node at the next. The first time it reaches the target, it has reached it along a shortest path, which corresponds to the closest degree of relatedness.
Tracking that degree means storing a level on each person during the traversal. The Person class gains a level field, set as each parent is enqueued, and the generation gap is the difference between the two levels. The version below returns that gap instead of a boolean:
class Person {
String name;
List<Person> parents;
int level;
public Person(String name) {
this.name = name;
this.parents = new ArrayList<>();
this.level = 0;
}
}
public class AncestryChecker {
public int areRelated(Person person1, Person person2) {
if (person1 == person2) {
return 0; // Same person, so generation gap is 0
}
Queue<Person> queue = new LinkedList<>();
Set<Person> visited = new HashSet<>();
queue.offer(person1);
visited.add(person1);
while (!queue.isEmpty()) {
Person current = queue.poll();
for (Person parent : current.parents) {
if (!visited.contains(parent)) {
parent.level = current.level + 1;
if (parent == person2) {
return parent.level - person1.level; // Generation gap
}
queue.offer(parent);
visited.add(parent);
}
}
}
return -1; // No path connecting the two individuals
}
// ... Rest of the code remains the same ...
}
areRelated now returns the number of generations between person1 and person2. A return value of -1 means no path connects them.
What are some data structures that are necessary to solve this problem?
Four structures carry most of the work:
Person class or node, holding the name, the parent references, and any other relevant information.Two more show up depending on the implementation. A stack is needed if depth-first search is written iteratively rather than recursively. Ordinary variables hold intermediate results such as the depth of each person during traversal, or the computed generation gap.
How do you ensure you have found the shortest path?
Breadth-first search guarantees it. BFS visits all the neighbours of a node before moving on to the next level of nodes, and the queue hands nodes back in the order they were discovered. Because the search proceeds level by level out from the source, any shorter path would already have been explored at an earlier level. So the first time the target node is reached, it is reached along a shortest path, and the number of generations separating the two individuals is the minimum.