¿Qué es el algoritmo húngaro?
El algoritmo húngaro se basa en la idea de suficiencia. prueba en el teorema de Hall, y sus pasos básicos son los siguientes:
1. Cualquier coincidencia inicial m;
2. Si X está saturado, finalice; de lo contrario, continúe con el paso 3; /p>
3. Encuentre un vértice no saturado x0 en X como v1 ← {x0}, v2←φ;
4 Si T(V1) = V2, se detendrá porque no puede coincidir. , de lo contrario, elija un punto y∈T(v 1)\ V2;
5. Si y está saturado, vaya a 6; de lo contrario, haga una ruta creciente p desde x0 → y, M←M? E(P), pase a 2;
6. Debido a que Y está saturado, hay una arista (Y, z) en M, que es v 1←v 1 ∨{ z }, v2←v2. ∨{ Y }, turno 4;
Deje que la matriz suba [1...n] - marca los puntos en la parte superior del gráfico bipartito.
Abajo[1...n] - marca los puntos en la parte inferior del gráfico bipartito.
Mapa[1..n, 1..n] - Representa la relación entre puntos en las mitades superior e inferior de un gráfico bipartito.
Verdadero - conectado, falso - no conectado.
Más de 1 [1...n] y más de 2 [1...n] marcan los puntos de cobertura superior e inferior.
Uso [1..n, 1..n] - indica si el borde está cubierto.
Primero, procese los datos leídos. Para el borde (x, y), el punto inicial entra en la configuración y el punto final entra en la configuración. Marque el elemento correspondiente en el mapa como verdadero.
1. Encuentra un punto descubierto en arriba.
2. Partiendo del punto descubierto, busque una ruta factible, es decir, una ruta que comience desde el borde delgado y termine en el borde delgado, con rutas gruesas y delgadas escalonadas.
3. Si lo encuentra, modifique los elementos de over1 y over2 y utilice los puntos correspondientes a la ruta. Repita el paso 1.
4. Cuente el número total de bordes cubiertos en uso. El número total n menos el número total es la solución al problema.