|
3 | added 28 characters in body | ||
|
Can anyone give me a hint for an algorithm to find a simple cycle of length 4 (4 edges and 4 vertices that is) in an undirected graph, given as an adjacency list? It needs to use $O(v^3)$ operations (v is the number of vertices) and I'm pretty sure that it can be done with some kind of BFS or DFS. The algorithm only has to show that there is such a cycle, not where it is. |
||||
|
|
2 | added 13 characters in body | ||
|
Can anyone give me a hint for an algorithm to find a simple cycle of length 4 (4 edges and 4 vertices that is) in an undirected graph? It needs to use $O(v^3)$ operations (v is the number of vertices) and I'm pretty sure that it can be done with some kind of BFS or DFS. The algorithm only has to show that there is such a cycle, not where it is. |
||||
|
|
1 |
|
||
Cycle of length 4 in an undirected graphCan anyone give me a hint for an algorithm to find a simple cycle of length 4 (4 edges and 4 vertices that is) in an undirected graph? It needs to use $O(v^3)$ operations (v is the number of vertices) and I'm pretty sure that it can be done with BFS or DFS. The algorithm only has to show that there is such a cycle, not where it is.
|
||||
