Parris Studios

UPDATE Dec 16th, 2008-

So I discovered that this works in many cases; however, there is a case that breaks this test. An example of where it breaks is when there is are 6 nodes. in which 3 are connected without a cycle and 3 are connected in a cycle within themselves. These 2 sets of 3 are not connected in anyway but in one graph. I feel like the below will work, but first one must search for connected components. Once connected components are found running the code below will detect if there is a cycle within each. This could potentially work for directed graphs too; however, for directed graphs you can detect strongly connected components (or run Depth First Search). If a strongly connected component exists then you have a cycle. Sounds about right to me! Sorry for the non-posting lately, I have been busy with finals!

——————————————————-

So I need to hear opinions on this. I think this short algorithm could work to find a cycle in an undirected graph. I have seen various methods, but all are somewhat weak. I can’t think of any cases to break this. Let me know!

/**
* Compares the number of edges(E) with the number of verticies(V).
* if (E)>(V)-1 then a cycle exists. If a vertex is not connected at all
* it will not be considered.
* @return true if and only if cycle exists, else false
*/
public boolean cycleExists(){
int v = getNumberOfVerticies();

//remove 1 from v every time a vertex is found without any edges

for (int i=0; i
{
if (allVerticies.get(i).connectedEdges.size()==0)
v--;
}
if (getNumberOfEdges() > v-1)
return true;
else
return false;
}