Skip to content

Fleury Eulerian ​

fleuryEulerian(graph) retorna um caminho que usa cada aresta exatamente uma vez, escolhendo arestas que não são pontes enquanto houver alternativas. Aceita uma lista não direcionada ou Graph<N, W> e retorna ausência quando o caminho não existe.

AssinaturaRetornoComplexidade
fleuryEulerian(graph: usize[][])usize[]?O(E(V + E))
fleuryEulerian(graph: Graph<N, W>)usize[]?O(E(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 { fleuryEulerian } from "tyrus:algorithm";

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

Resultado para estudo ​

fleuryEulerianInfo retorna o caminho junto com métricas de exame de arestas e escolhas de pontes. Importe explicitamente as interfaces base e especializada.

tyrus
interface FleuryEulerianInfo {
    path: usize[]?;
    usedEdgeCount: usize;
    examinedEdgeCount: usize;
    isCircuit: bool;
    bridgeCheckCount: usize;
    avoidedBridgeChoiceCount: usize;
}
tyrus
import { EulerianInfo, FleuryEulerianInfo, fleuryEulerianInfo } from "tyrus:algorithm";
const graph: usize[][] = [[3, 1, 2], [0, 2], [1, 0], [0]];
const info: FleuryEulerianInfo = fleuryEulerianInfo(graph);
print(info.path ?? []); // [0, 1, 2, 0, 3]
print(info.usedEdgeCount); // 4
print(info.examinedEdgeCount); // 5
print(info.isCircuit); // false
print(info.bridgeCheckCount); // 2
print(info.avoidedBridgeChoiceCount); // 1