Hierholzer Eulerian
hierholzerEulerian(graph) construye un camino que usa cada arista exactamente una vez uniendo ciclos cerrados. Acepta una lista no dirigida o Graph<N, W> y devuelve ausencia si no existe.
| Firma | Retorno | Complejidad |
|---|---|---|
hierholzerEulerian(graph: usize[][]) | usize[]? | O(V + E) |
hierholzerEulerian(graph: Graph<N, W>) | usize[]? | O(V + E) |
La lista debe representar un grafo no dirigido con entradas simétricas. Un camino válido tiene E + 1 vértices.
Ejemplo
tyrus
import { hierholzerEulerian } from "tyrus:algorithm";
const path: usize[]? = hierholzerEulerian([[1, 2], [0, 2], [0, 1]]);
if (path) {
print(path.length); // 4
}Resultado para estudio
hierholzerEulerianInfo devuelve el camino junto con métricas de aristas y operaciones de pila. Importe explícitamente las interfaces base y especializada.
tyrus
interface HierholzerEulerianInfo {
path: usize[]?;
usedEdgeCount: usize;
examinedEdgeCount: usize;
isCircuit: bool;
stackPushCount: usize;
stackPopCount: usize;
joinedCycleCount: usize;
}tyrus
import { EulerianInfo, HierholzerEulerianInfo, hierholzerEulerianInfo } from "tyrus:algorithm";
const graph: usize[][] = [[1, 2], [0, 2], [0, 1]];
const info: HierholzerEulerianInfo = hierholzerEulerianInfo(graph);
print(info.path ?? []); // [0, 2, 1, 0]
print(info.usedEdgeCount); // 3
print(info.examinedEdgeCount); // 6
print(info.isCircuit); // true
print(info.stackPushCount); // 7
print(info.stackPopCount); // 7
print(info.joinedCycleCount); // 1