Struct UndirectedGraph 

pub struct UndirectedGraph {
    pub n: usize,
    pub adj: Vec<HashSet<usize>>,
}

An undirected simple graph (represented as adjacency sets for simplicity).

Fields

n: usize

Number of vertices.

adj: Vec<HashSet<usize>>

Adjacency sets: adj[u] = set of neighbors

Implementations

impl UndirectedGraph

pub fn new(n: usize) -> Self

Create with n vertices.

pub fn add_edge(&mut self, u: usize, v: usize)

Add undirected edge.

pub fn bfs(&self, s: usize) -> Vec<usize>

BFS from source s.

pub fn is_connected(&self) -> bool

Is the graph connected?

pub fn num_components(&self) -> usize

Number of connected components.

pub fn bipartite_coloring(&self) -> Option<Vec<usize>>

Is the graph bipartite? Returns Some(coloring) or None.

pub fn is_bipartite(&self) -> bool

Is the graph bipartite?

pub fn all_degrees_even(&self) -> bool

Check if all vertex degrees are even (necessary for Eulerian circuit).

pub fn has_eulerian_circuit(&self) -> bool

Check if graph has an Eulerian circuit (connected + all even degrees).

pub fn greedy_coloring(&self) -> (usize, Vec<usize>)

Greedy graph coloring (returns number of colors used and coloring).

pub fn is_proper_coloring(&self, coloring: &[usize]) -> bool

Check if a given coloring is proper.

pub fn degree(&self, u: usize) -> usize

Degree of vertex u.

pub fn edge_count(&self) -> usize

Number of edges.

pub fn spanning_tree(&self) -> Vec<(usize, usize)>

Minimum spanning tree (Prim’s algorithm, unweighted → any spanning tree). Returns edges of the spanning tree.

pub fn complete(n: usize) -> Self

Create complete graph K_n.

pub fn path(n: usize) -> Self

Create path graph P_n (0-1-2-…-n-1).

pub fn cycle(n: usize) -> Self

Create cycle graph C_n.

pub fn complete_bipartite(m: usize, n: usize) -> Self

Create complete bipartite graph K_{m,n}.

Trait Implementations

impl Clone for UndirectedGraph

fn clone(&self) -> UndirectedGraph

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for UndirectedGraph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for UndirectedGraph

fn default() -> UndirectedGraph

Returns the “default value” for a type.