Skip to content

Hierholzer Eulerian ​

hierholzerEulerian(graph) constrói um caminho que usa cada aresta exatamente uma vez, unindo ciclos fechados. Aceita uma lista não direcionada ou Graph<N, W> e retorna ausência quando o caminho não existe.

AssinaturaRetornoComplexidade
hierholzerEulerian(graph: usize[][])usize[]?O(V + E)
hierholzerEulerian(graph: Graph<N, W>)usize[]?O(V + E)

A lista deve representar um grafo não direcionado com entradas simétricas. Um caminho bem-sucedido tem E + 1 vértices.

Exemplo ​

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

const path: usize[]? = hierholzerEulerian([[1, 2], [0, 2], [0, 1]]);
if (path) {
    print(path.length); // 4
}

Resultado para estudo ​

hierholzerEulerianInfo retorna o caminho junto com métricas de arestas e operações da pilha. Importe explicitamente as interfaces base e 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