[SOLVED] Comp 3270 programming assignment 2 – graph traversal algorithms

Imagine you are given a dataset that represents a social network, where
individuals are nodes in the graph, and their connections or friendships are
represented as edges in an edge list.Your task is to analyze this social
network to extract valuable insights. The dataset is in the form of an edge
list. A visualization of the graph is shown below to help you.Input:
An edge list file where each line represents a friendship connection between
two individuals, e.g., “N_0, N_1.”Output:
A report with a table such as the one below that documents the length of the
shortest path between two individuals (or vertices) in this graph and the time
taken to find the path between the two nodes.You must explore all pairs
indicated in the table and complete the table below for each of the following
algorithms. You should not include an entry if there are no paths between the
two nodes. Use the graph above to identify if the nodes have paths
connecting them.Node 1 Node 2 BFS DFS
Distance Time (ms) Distance Time (ms)
N_0 N_1
N_0 N_2
N_0 N_3
N_0 N_4
N_0 N_5
N_0 N_6
N_0 N_7
N_0 N_8
N_0 N_9
N_0 N_10
N_0 N_11
N_0 N_12
N_0 N_13
N_0 N_14
N_0 N_15
N_0 N_16
N_0 N_17
N_0 N_18
N_0 N_19
N_0 N_20
N_0 N_21
N_0 N_22
N_0 N_23
N_0 N_24You must explore the following algorithms. Breadth First Search (BFS) and
Depth-First Search (DFS). For each of the node pairs in the table, you must
run BFS/DFS with the start node as Node 1 and terminate the algorithm
when Node 2 is reached. For example, to find the distance between N_0 and
N_1, the start node is N_0. The algorithm terminates when N_1 is visited or
“explored” by the algorithm. The distance is the total number of nodes visited
by the algorithm before reaching the target vertex.Your report should also have a brief description of the data structure that you
will use to represent the graph and a short justification.The goal of this assignment is to analyze how long it takes for BFS and DFS
to reach nodes at different depths. Based on your experiments above, briefly
answer the following questions with an example:
1. Suppose you want to find a path between nodes at a shallow depth to
your start node. Would you use BFS or DFS?2. Suppose that the end node is at a very large depth from the start node.
Would you use BFS or DFS?