Skip to main content

has_cycle

rust_algorithms::graph

Function has_cycle 

Source 
pub fn has_cycle(g: &Graph) -> bool
Expand description

Grafda sikl bormi?

  • Yo’naltirilmagan grafda: DFS paytida “ota bo’lmagan ko’rilgan qo’shni” topilsa — sikl.

  • Yo’naltirilgan grafda: hozirgi rekursiya yo’lida turgan tugunga qaytsak — sikl (bu “orqaga qaytuvchi qirra” / back edge deyiladi).

  • Time: O(V + E).

§Misol

use rust_algorithms::graph::{Graph, has_cycle};

let mut daraxt = Graph::new_undirected(3);
daraxt.add_unweighted_edge(0, 1);
daraxt.add_unweighted_edge(1, 2);
assert!(!has_cycle(&daraxt));

daraxt.add_unweighted_edge(2, 0); // uchburchak hosil bo'ldi
assert!(has_cycle(&daraxt));