KIT205: Data Structures and Algorithms- IT Assignment

Internal code- MAS626

IT Assignment

Questions- You find that the topological sort can take a long time for some graphs, and you would also like to be able to detect cycles. So you decide to test whether a depth first search based topological sort gives better performance. For this part of the assignment, you will implement DFS for the input graph, and use the post-order numbering of the DFS spanning tree to determine if there are any cycles. If there are no cycles, you should then use the post-order numbering to calculate a topological sort and calculate and print the new state of the graph as for part A. Otherwise, the program should print an error message: “this graph contains at least one cycle”. There is however, a slight complication. The procedure for DFS described in lectures assumes a single known starting vertex. That is not the case for this data, where in general we will have many “input” neurons. In this situation, we usually build a DFS forest by repeated application of the algorithm. For this assignment, two solutions to this problem will be allowed: 1. Implement an algorithm that builds a DFS spanning forest. You will find examples of this approach online. 2. Use the previously calculated in-degrees to identify “input” neurons (the ones with in-degree 0). Then (conceptually) add a new vertex to the graph with edges to each of these inputs. Make this new vertex the starting point for your DFS. The first approach has the advantage that it is the standard way to deal with this problem,so you will find more help online. The second approach has the advantage that it matches what was discuss in lectures more closely and may be a little simpler to understand.