Skip to content

edmondsBlossom ​

edmondsBlossom(graph) calcula um emparelhamento máximo em um grafo não direcionado geral, inclusive com ciclos ímpares. Aceita uma lista de adjacência ou Graph<N, W>.

AssinaturaRetornoComplexidade
edmondsBlossom(graph: usize[][])[usize, usize][]O(V³)
edmondsBlossom(graph: Graph<N, W>)[usize, usize][]O(V³)

O resultado contém pares disjuntos de vértices emparelhados. A ordem dos pares não é garantida.

Exemplo ​

tyrus
import { edmondsBlossom } from "tyrus:algorithm";

const matching: [usize, usize][] = edmondsBlossom([[1], [0], [3], [2]]);
print(matching.length); // 2

Resultado para estudo ​

tyrus
interface EdmondsBlossomInfo {
    pairs: [usize, usize][];
    cardinality: usize;
    examinedEdgeCount: usize;
    blossomContractionCount: usize;
    augmentingPathSearchCount: usize;
    augmentationCount: usize;
}
tyrus
import { EdmondsBlossomInfo, MatchingInfo, edmondsBlossomInfo } from "tyrus:algorithm";
const graph: usize[][] = [[1], [0], [3], [2]];
const info: EdmondsBlossomInfo = edmondsBlossomInfo(graph);
print(info.pairs); // [[0, 1], [2, 3]]
print(info.cardinality); // 2
print(info.examinedEdgeCount); // 4
print(info.blossomContractionCount); // 0
print(info.augmentingPathSearchCount); // 4
print(info.augmentationCount); // 2