Find cyclic dependency

Question

Possible Duplicate:
Finding all cycles in graph

I have a task I've been wrapping my brain around and still have a trouble inplementing it. Here it goes: There is a class:

public class Package {
private String name;
public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

private List<Package> dependencies;

public List<Package> getDependencies() {
    return dependencies;
}

public void setDependencies(List<Package> dependencies) {
    this.dependencies = dependencies;
}

public Package(String name){
    this.name = name;
    this.dependencies = new ArrayList<Package>();
}
  //any bunch of methods here))
}

And there is another one:

public class Project {
private String name;
private List<Package> packages = new ArrayList<Package>();

public boolean hasCyclic(){
    //**//implementation should be here
}

}

I need to find whether a list of packages in a project has a cyclic dependency or not. For example A->B->C->B - found, return true or A->C->Z->A - found, return true. First thing that comes to mind is to get all packages' names, sort them and find duplicates. But somewhere, deep in my brain, something tells me it is not the most optimal solution. Can you guys help me out here? Thank you so much in advance.

Solution 1

This is basically a "Detect Cycles in a Directed Graph" problem.

I can't beat this answer already posted in SO that explains how to solve this problem.

Solution 2

There is a cycle <==> The DFS forest (from any starting point) has a back branch.

Linear running time. Simple implementation.

Solution 3

Think of the project's dependencies as a tree, and then simply do a depth-first traversal of the tree, keeping track of the package name when you visit each node. If you encounter a duplicate name before the traversal reaches the furthest level it can, then you have a cyclic dependency.