CS502 Assignment 3 Solution
#1
CS502 Design and Analysis of Algorithms
Assignment 3 Solution - Spring 2017

Question. 1  Consider the following Directed Acyclic Graph.
[Image: dvLRV2c.jpg]

Run BFS on this graph by taking node ‘1’ as source node and list the vertices in order while running BFS.
 
Note: Write a list of vertices only, no need to show the intermediate steps.

Answer: 1, 3, 4, 8

Question. 2
 
Two directed graphs are given below Graph (A) & Graph (B), You are required to answer the following questions
1.      Is “Graph (A)” a connected graph? State Yes / No with valid reason
2.      Is “Graph (B)” contains a Hamiltonian cycle? State Yes / No with valid reason
 
 [Image: w3zvPmJ.png][Image: yAxKbmk.png]

                        Graph (A)                                                                                Graph (B)


Answer:

  1. No, because 1 is not connected with 5 directly and also 5 is not connected with 3 directly.
  2. Yes, 1, 2, 3, 4, 1 creates a Hamiltonian cycle.
  


Possibly Related Threads…
Thread Author Replies Views Last Post
  CS502 Assignment 1 Solution Fall 2019 Ayra Suleman 0 521 11-11-2019, 02:04 AM
Last Post: Ayra Suleman
  CS502 Assignment 3 Solution Spring 2019 Ayra Suleman 0 264 07-20-2019, 02:49 PM
Last Post: Ayra Suleman
  CS502 Assignment2 Solution Spring 2019 Mishi Khan 0 417 05-27-2019, 02:09 AM
Last Post: Mishi Khan
  CS502 Assignment Solution Spring 2019 Mishi Khan 0 313 05-14-2019, 09:56 PM
Last Post: Mishi Khan
  CS502 Assignment Solution Spring 2019 Mishi Khan 0 419 05-14-2019, 12:30 AM
Last Post: Mishi Khan
  CS502 GDB Idea Solution Mishi Khan 0 870 02-08-2019, 01:38 AM
Last Post: Mishi Khan
  CS502 Assignment Solution Mishi Khan 0 905 02-04-2019, 07:04 PM
Last Post: Mishi Khan
  CS502 GDB Solution 2017 Pakistani 1 3,380 08-07-2018, 06:31 PM
Last Post: Zaeem Hassan
  CS502 Assignment 1 Solution Fall 2017 Pakistani 0 2,369 11-16-2017, 11:53 AM
Last Post: Pakistani
Lightbulb Need CS502 Assignment no 1 solution Adorable Pakhtoon 3 3,355 11-17-2016, 04:21 PM
Last Post: Rubaisha(Moody Girl)



Users browsing this thread:
1 Guest(s)