A following weighted graph contains 6 vertices and 10 edges 70 E 30 20 80 10...

 

Transcribed Image Text:

A following weighted graph contains 6 vertices and 10 edges 70 E 30 20 80 10 50 20 30 60 a) Does this graph contain an Euler circuit or/and Euler path? Why? (8 marks) b) What is the sequence of visited node in BFS, and DFS if both algorithms start from node A? (8 marks) c) Draw the minimum spanning tree of this graph (4 marks). d) Use the Dijkstra's algorithm to determine the shortest paths from city (A) to all other cities (6 marks). Determine the shortest path and cost from node A to node D (2 marks). [Hint: implement the algorithm step by step to show which node will be added in sequence] e) Determine the shortest paths between all pairs of nodes. (12 marks) A following weighted graph contains 6 vertices and 10 edges 70 E 30 20 80 10 50 20 30 60 a) Does this graph contain an Euler circuit or/and Euler path? Why? (8 marks) b) What is the sequence of visited node in BFS, and DFS if both algorithms start from node A? (8 marks) c) Draw the minimum spanning tree of this graph (4 marks). d) Use the Dijkstra's algorithm to determine the shortest paths from city (A) to all other cities (6 marks). Determine the shortest path and cost from node A to node D (2 marks). [Hint: implement the algorithm step by step to show which node will be added in sequence] e) Determine the shortest paths between all pairs of nodes. (12 marks)