hadron43 / coursera-dsa

It contains my solutions to all Assignments on Coursera

coursera-dsa

It contains my solutions to all Assignments on Coursera.

This repository is open for all kind of suggestions.

Contributors: Harsh Kumar

#Please add your name here while committing

coursera-dsa's Issues

Checking if a given directed Graph is a DAG

I implemented this problem in Java. (GraphAlgorithms/week2.../1_.../Acyclic.java)
https://github.com/hadron43/coursera-dsa/blob/master/GraphAlgorithms/week2_decomposition2/1_acyclicity/Acyclicity.java

You can view the problem state on: https://github.com/hadron43/coursera-dsa/blob/master/GraphAlgorithms/week2_decomposition2/decomposition2.pdf Page 5

I kept an ArrayList to keep track of the elements in the current call frame stack. I recursively call the explore method on the neighbors of the element. If the element is repeated in the same call frame, that means given graph has a cycle, and thus it is not a DAG.

I am looking for a better implementation rather than passing a copy of all visited elements in each recursive call.

Any help will be appreciated.