Esercizi

Ciclo in un grafo

• input un grafo $G\mid \forall v\in V(G),\mathrm{deg}(v)\ge 2$
• output un ciclo un grafo (come elenco di vicini)
• complessità $O(n+m)$

#![allow(unused)]
fn main() {
use std::collections::VecDeque;

pub mod practice;
use practice::path;

fn find_cycle(graph: &[Vec<usize>], mut x: usize) -> Vec<usize> {
    let mut cycle = vec![];
    let mut visited = vec![false; graph.len()];

    let mut z = x;
    while !visited[x] {
        cycle.push(x);
        visited[x] = true;

        let next = if graph[x][0] == z { 1 } else { 0 };
        z = x;
        x = graph[x][next];
    }

    cycle.into_iter().skip_while(|&y| y != x).collect()
}

fn does_path_exist(graph: &[Vec<usize>], x: usize, y: usize) -> bool {
}

Cammino da $x$ a $y$

• input un grafo $G$ e $x,y\in V(G)$
• output $x\sim y?$
• complessità $O(n+m)$

#![allow(unused)]
fn main() {
    dfs(graph, x, &mut visited);

    visited[y]
}

fn dfs(graph: &[Vec<usize>], x: usize, visited: &mut Vec<bool>) {
    visited[x] = true;

    for &y in &graph[x] {
}

#![allow(unused)]
fn main() {
            dfs(graph, y, visited)
        }
    }
}

fn dfs_iterative(graph: &[Vec<usize>], x: usize) -> Vec<bool> {
    let mut stack = Vec::from([x]);
    let mut visited = vec![false; graph.len()];
    let mut adjacent = vec![0; graph.len()];

    while let Some(&x) = stack.last() {
        if let Some(&y) = graph[x].get(adjacent[x]) {
            if !visited[y] {
                stack.push(y);
                visited[y] = true;
            }

            adjacent[x] += 1;
        } else {
            stack.pop();
}

#![allow(unused)]
fn main() {
fn path(graph: &Vec<Vec<usize>>, x: usize, y: usize) -> bool {
    dfs_iterative(graph, x)[y]
}
}

Componenti di $G$

• input un grafo $G$
• output l'elenco di archi in avanti, indietro e di attraversamento
• complessità $O(n+m)$

#![allow(unused)]
fn main() {
    }

    visited
}

pub fn find_components(graph: &[Vec<usize>]) -> Vec<usize> {
    let mut components = vec![0; graph.len()];
    let mut component = 1;

    for x in 0..graph.len() {
        if components[x] == 0 {
            dfs_components(graph, x, &mut components, component);
            component += 1;
        }
    }

    components
}

fn dfs_components(graph: &[Vec<usize>], x: usize, components: &mut Vec<usize>, component: usize) {
    components[x] = component;

    for &y in &graph[x] {
        if components[y] == 0 {
            dfs_components(graph, y, components, component)
        }
    }
}
}

Classificazione archi

• input un grafo $G$
• output le componenti di $G$
• complessità $O(n+m)$