Algoritmo para condensar el gráfico:
Paso 1:
Realice dfs normales en el gráfico dado y almacene el número de nodo en una pila de acuerdo con su tiempo de visita. Este dfs es similar a la ordenación topológica. De esta manera, el nodo con el mayor tiempo de finalización estará en la parte superior de la pila.
- ¿De qué sirve el hashing en C?
- ¿Cuál es el mejor y el último algoritmo de última generación para encontrar documentos similares?
- ¿Cómo reduce () tomar la entrada de múltiples map ()?
- ¿Cuál es la relación entre el índice de una matriz y el tamaño de una matriz?
- Java: ¿Cómo podemos verificar si un número es feliz o no mediante el uso de funciones de cadena simples y bucles sin ningún arreglo?
// adjList [] representa la lista de adyacencia del gráfico dado
apilar st;
dfs nulo (ll start, vector adjList [], vector y visitado)
{
visitado [inicio] = verdadero;
for (ll i = 0; i <adjList [start] .size (); i ++)
{
ll vértice = adjList [inicio] [i];
if (visitado [vértice] == falso)
{
dfs (vértice, adjList, n_visited);
}
}
st.push (inicio);
}
Paso 2:
Realice otra operación dfs para un componente fuertemente conectado y almacene los nodos de un componente fuertemente conectado particular en un nuevo vector llamado gr.
// r_adjList: representa la lista de adyacencia del gráfico invertido
// scc_visited -visited vector requerido para dfs
// grupo – representa el componente fuertemente conectado
// gr- este vector guarda los nodos en un componente particular fuertemente conectado
// parent []: guarda el grupo no para el nodo, es decir, guarda el representante de // nodo en un componente fuertemente conectado
ll grupo;
vector gr;
ll padre [MAX_LENGTH] = {0};
voc scc_dfs (ll start, vector r_adjList [], vector & scc_visited)
{
scc_visited [inicio] = verdadero;
para (ll i = 0; i <r_adjList [inicio] .size (); i ++)
{
ll vértice = r_adjList [inicio] [i];
if (scc_visited [vértice] == falso)
{
scc_dfs (vértice, r_adjList, scc_visited);
}
}
gr [grupo] .pb (inicio);
padre [inicio] = grupo;
}
Paso 3:
Esta es la parte principal de reducir el gráfico.
Nuevamente, haga el recorrido dfs, y para cada nodo adyacente u de un nodo particular v, compruebe que si ese nodo u es parte del mismo componente fuertemente conectado que el de v. Es decir, compruebe si u y v pertenecen al mismo fuertemente conectado componente. Si es así, no agregue ningún borde, de lo contrario agregue el borde entre los dos nodos u y v
// visitado [] – es un vector visitado requerido para el recorrido dfs
// adjList_new []: guarda la nueva lista de adyacencia para el gráfico condensado
// adjList [] – antigua lista de adyacencia
void condense_graph_dfs (ll start, vector adjList [], vector adjList_new [], vector y visitado)
{
visitado [inicio] = verdadero;
for (ll i = 0; i <adjList [start] .size (); i ++)
{
ll vértice = adjList [inicio] [i];
ll p_start = padre [inicio];
ll p_vertex = padre [vértice];
if (p_start == p_vertex)
{
continuar;
}
más
{
adjList_new [p_start] .pb (p_vertex);
}
if (visitado [vértice] == falso)
condense_graph_dfs (vértice, adjList, adjList_new, visitado);
}
}
Después de realizar condense_graph_dfs, obtiene la nueva lista de adyacencia para el gráfico condensado donde los nodos son el grupo no asignado durante la operación dfs del componente fuertemente conectado. Espero que esto deje en claro reducir los componentes fuertemente conectados en nodos únicos en el gráfico.
