hired you to design an algorithm that will be able to print the
connection between the writer and viewer of any posts on the
network. For example, given the following graph where every vertex
represents a person and every edge represents friendship between
two individuals, if person 0 writes a post and if that post is
visible to person 5 then your algorithm should print that person 5
or the viewer of the post is friend of person 1 and person 1 is
friend of the writer of the post i.e. person 0.
- Consider That The Social Network Giant Facebook Has Hired You To Design An Algorithm That Will Be Able To Print The Conn 1 (160.69 KiB) Viewed 23 times
solve the above problem.
(b) Simulate your algorithm (program) from part (a) line
by line to show the connection between the writer of the post,
person 0, and the viewer of the post, person
5.
(c) The algorithm (program) that you have written in
part (a) uses a certain algorithm design technique to explore all
the vertices of the social network. What is the name of this
algorithm design technique? Explain how this technique works with
an example.
(d) Draw the above graph and write down the order of
exploration of the vertices if a different graph exploration
algorithm is used instead of the one that you have written as
response to part (a).
(e) Can the graph exploration techniques that you have
used in parts (a) and (d) carry out exploration of a graph if it
contains cycle(s) or loop(s)? Explain.
(f) How is a graph represented in a computer? Represent
the above graph using this method.
0 1 5 3 2 4 6