Problem Statement : Social Network Analysis Using Graph Representation

Objective:

You are given a dataset representing a social network. Each person is a node, and each connection between two people is an edge. Your task is to analyze the network using different graph representations and traversal techniques.

Instructions:

$1.$ Graph Construction:

o Construct the graph using the given dataset.

o Represent the graph using:

$$ Edge List

$$ Adjacency List

$$ Adjacency Matrix

$2.$ Graph Properties:

o Calculate the degree of each vertex.

o Determine if the graph is connected or disconnected.

o Identify any isolated vertices $($vertices with no edges$).$

$3.$ Graph Traversal:

o Implement Breadth$-$First Search $($BFS$)$ starting from a specified node.

o Implement Depth$-$First Search $($DFS$)$ starting from the same node.

o Record the order in which nodes are visited for both BFS and DFS$.$

$4.$ DFS with Timestamps:

o Implement DFS with timestamps. Record the discovery and finish time for each node.

o Identify the start and finish times for each node and list them.

Deliverables:

$$ Submit the code for graph representation and traversal.

$$ Provide a report explaining the results of BFS and DFS$,$ including the order of traversal and timestamp information.

$$ Analyze and compare the space complexity of each graph representation method used.

Data Set:

Assume the dataset is in the form of a list of connections between people. Each connection can be represented as $($person$1,$ person$2).$

connections $=[(\text{'}$A$\text{'},\text{'}$B$\text{'}),(\text{'}$A$\text{'},\text{'}$C$\text{'}),(\text{'}$B$\text{'},\text{'}$D$\text{'}),(\text{'}$C$\text{'},\text{'}$D$\text{'}),(\text{'}$D$\text{'},\text{'}$E$\text{'}),(\text{'}$F$\text{'},\text{'}$F$\text{'})]$

connections $=[(1,2),(1,3),(2,5),(3,5),(3,6),(4,2),(5,4),(6,6)]$