Question

Implement a Breadth-First Search of the people in the network who are reachable from person id 3980. You can implement BFS with a queue and the pseudocode is given in CLRS. Print out the distance (number of connections) from person 3980 to every person who is reachable from 3980 via edge traversals. Note that not all people in this network may be reachable via edge traversals from user id 3980, so users that are not accessible can be ignored in BFS.

Answer 1

Check the explanation

Step-by-step explanation:

import java.io.File;

import java.io.FileNotFoundException;

import java.util.LinkedList;

import java.util.Scanner;

import static org.junit.Assert.assertEquals;

/**

* CS146 Assignment 3 Node class This class is used for undirected graphs

* represented as adjacency lists The areFriends() method checks if two people

* are friends by checking if an edge exists between the two

*

*/

public class NetworkAdjList {

// Initialize array with max number of vertices taken from SNAP

static int max_num_vertices = 88234;

static LinkedList<Integer>[] adjacencyList = new LinkedList[max_num_vertices];

public static void createAdjacencyList() {

// Initialize array elements

for (int j = 0; j < max_num_vertices; j++) {

adjacencyList[j] = new LinkedList<Integer>();

}

// Get file path of the 3980.edges file

String filePath = "C:\\Users\\shahd\\Documents\\CS146\\Assignment 3\\Question 3\\Question3\\src\\a3\\3980.edges";

File f = new File(filePath);

// Use Scanner to read edges from the file and put it into adjacency list

int a;

int b;

try {

Scanner fileIn = new Scanner(f);

while (fileIn.hasNext()) {

a = fileIn.nextInt();

b = fileIn.nextInt();

adjacencyList[a].add(b);

adjacencyList[b].add(a); // We need to add the edges both ways

}

} catch (FileNotFoundException e) {

e.printStackTrace();

}

}

public static boolean areFriends(int A, int B) {

// If the adjacency list contains (A, B) edge, then return true, else false

if (adjacencyList[A].contains(B)) {

return true;

} else {

return false;

}

}

private static void bfsHelper(boolean visited[], int currentNode, int dis, int sourceNode) {

dis++;

if(!visited[currentNode]) {

visited[currentNode] = true;

for(int neighbor: adjacencyList[currentNode]) {

System.out.println(neighbor + " is at a distance of " + dis + " from " + sourceNode);

bfsHelper(visited, neighbor, dis++, sourceNode);

}

}

}

public static void BFStraversal(int start) {

boolean visited[] = new boolean[max_num_vertices];

bfsHelper(visited, start, 0, start);

}

public static void main(String[] args) {

/**

* These test cases assume the file 3980.edges was used

*/

createAdjacencyList();

System.out.println("Testing...");

assertEquals(areFriends(4038, 4014), true);

System.out.println("1 of 7");

System.out.println("Testing...");

assertEquals(areFriends(3982, 4037), true);

System.out.println("2 of 7");

System.out.println("Testing...");

assertEquals(areFriends(4030, 4017), true);

System.out.println("3 of 7");

System.out.println("Testing...");

assertEquals(areFriends(4030, 1), false);

System.out.println("4 of 7");

System.out.println("Testing...");

assertEquals(areFriends(1, 4030), false);

System.out.println("5 of 7");

System.out.println("Testing...");

assertEquals(areFriends(4003, 3980), true);

System.out.println("6 of 7");

System.out.println("Testing...");

assertEquals(areFriends(3985, 4038), false);

System.out.println("7 of 7");

System.out.println("Success!");

}

}

**************************************************