Question

Question 1.) Given a directed negative weights Graph what is the most efficient algorithm to detect a cycle. What is the most efficient method to detect a cycle? Question 2.)Let A= student id last digit % 4 and add 1. For example mine student id is 7. So 7%4=3 and add 1 -->A=4 Run DFS starting at node a, and breaking ties alphabetically(in this case numerically as nodes have numbers where 1 goes before 2). Please label just back edges. 3 1 2 6 2 8 3 5 4 3

Answer 1

Solution:

(1)

Explanation:

=>"Bellman Ford" algorithm is used to detect cycle in a directed graph with negative edge.

=>Bellman Ford algorithm is based upon dynamic programming.

=>Bellman Ford algorithm is used as a single source shortest path algorithm as Dijkstra algorithm but in case of negative weight edges Dijkstra algorithm fails sometimes when there is negative weight cycle exist in the graph but Bellman Ford algorithm always gives correct result no matter edges are positve weight edges or negative weight edges.

=>Bellman Ford checks every node with n-1 iteration in total that is the reason it can detect cycle in the graph.

Most efficient method to detect a cycle:

=>To detect a cycle msot efficiently method is linked list by maintaining two pointers such that first pointer will traverse all the nodes one by one and other pointer will traverse alternate nodes/vertex, when these pointers will point to the same node/vertex then we can say that there is a cycle exists in the graph.

In have explained each and every part of the first question only according to "HOMEWORKLIB RULES when mulitple questions are given then only first question needs to be answered" with the help of statements attached to it.