edmondsBlossom
edmondsBlossom(graph) calcula un emparejamiento máximo en un grafo no dirigido general, incluidos los ciclos impares. Acepta una lista de adyacencia o Graph<N, W>.
| Firma | Retorno | Complejidad |
|---|---|---|
edmondsBlossom(graph: usize[][]) | [usize, usize][] | O(V³) |
edmondsBlossom(graph: Graph<N, W>) | [usize, usize][] | O(V³) |
El resultado contiene pares disjuntos de vértices emparejados. El orden de los pares no está garantizado.
Ejemplo
tyrus
import { edmondsBlossom } from "tyrus:algorithm";
const matching: [usize, usize][] = edmondsBlossom([[1], [0], [3], [2]]);
print(matching.length); // 2Resultado para estudio
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