Graph lab

Learning Objective(s)

1. Be able to represent a graph
2. Be able to implement a breadth first search of a graph
3. Be able to identify difference disconnected subcomponents of a graph
4. Develop quality data on your own

Overview of the problem

You are studying the spread of an idea. You are to tell how long it takes to get an idea from one person to another. However, if there is no way to get an idea from one person to another, you are to output how many different isolated communities there are. Communication is allowed to go both ways between any two people.

Specifics

• Input layout
  • first line → the number of different people in the data (n)
  • next n lines → one name per line
  • next line → the two people who need to communicate: such as: bob sue
  • all remaining lines: each line represents a way for person x to talk directly to person y, such as: tom larry
• Output:
  • either: There are "x" away from each other. (If they can talk directly to each other, then they are 1 away)
  • or: There are five different isolated communities in this data
• Assumptions:
  • There are at most 1000 people involved
• Testing. A good testing plan is important to this lab
  • Be sure to include simple data, regular data, large data, error data.

Design components

• Be sure to include any supporting data structures you use

Optional improvements

• Also implement it so that the talking is uni-directional.
• Also allow for cost of talking to be variable based on how much a person likes the other. (A smaller number means a greater like). Find the shortest/quickest way to send the message. Display the path.