How to find length of cycle in undirected graph?
1 -------2-------3
| | | | 4-------5
Here nodes 2,3,4 and 5 form cycle, so length of cycle is 4. Plz provide an algorithm to find length of cycle. I am unable to reach a solution for it.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
How to find length of cycle in undirected graph?
1 -------2-------3
| | | | 4-------5
Here nodes 2,3,4 and 5 form cycle, so length of cycle is 4. Plz provide an algorithm to find length of cycle. I am unable to reach a solution for it.
Название |
---|
which cycle the minimum cycle the maximum cycle which of them (the second is np because hamiltonian cycle is np)
I want length of just a cycle being formed. Like in above eg 2,3,4 and 5 form cycle. 1 does not form part of cycle. However, diagram is not clear but I suppose u would guess it. So plz help in finding length of the cycle.
If you need a length of any of the cycles you can use DFS. You can also use BFS but in my opinion with DFS its easier and faster to write. If you are not familiar with BFS and DFS look at:
http://en.wikipedia.org/wiki/Breadth-first_search http://en.wikipedia.org/wiki/Depth-first_search
How can one find length of cycle using DFS. We can check if there is a cycle or not usinfg DFS but not the entire length like in above eg. Plz elaborate how can one find length of cycle using DFS. A proper code would be helpful.
Ok.
I wrote a code about how to find those cycles. (link). My idea is simply to maintain a "used" array where I save the length from the "start" to the current vertex "u". If there is an adj. vertex "v" such that it is ancestor of "u" then there is a cycle and its length is the length to "u-v".