Posts Tagged ‘algorithm’
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; }