The Problem
In this problem we will explore graphs and problems that are relatable to the 6 degrees of separation problem, which claims that everyone in the world is connected by 6 people or less. We will investigate different networks to see the minimum distance between some starting node, s, and all other nodes in the graph. We will be using real-life data sets to test your code.
We are given a starting node s for some undirected graph G with nn nodes. The graph is formatted as an adjacency list, meaning that for each node, u, we can access all of u’s neighbors. The goal is to output all n nodes in G along with each node u’s minimum distance from ss.
Input
The input file is given with the first line as the starting node and the remainder of the file is an adjacency list for graph G (we assume that the set of vertices is {0,1,…,n−1}{0,1,…,n−1}). The
adjacency list assumes that the current node is the index of the line under consideration. For instance line 0 of the input file (not including the starting node) has the list of all nodes adjacent to node 0.
Note:
Both the input and output parsers in each of the three languages are already written for you.
Note that you have to work with the input data structures provided (which will come pre-loaded
with the data from an input file).
Reviews
There are no reviews yet.