aplicación clasificación topológica mediante el programa C ++

aplicación

topológica tipo : Aquí, vamos a poner en práctica topológica especie mediante el programa C ++ .

Planteamiento del problema:

Dado un gráfico de n vértices, usted tiene que ordenar topológicamente ese gráfico.

Ejemplo:

de entrada:

Si hay gráfico ser como el siguiente:

Topological sort implementation using C++ program - 4

salida: A & rarr; B & rarr; C & rarr; D & rarr; E & rarr; F & rarr; G

topológica tipo

Es una técnica en la que cada nodo se produce después de que el padre del nodo.

Aquí, nodo A y nodo B son dos nodos que no tienen padres. Así Un viene primero y luego D nodo viene sino para imprimir F necesitamos D y E tanto los nodos de modo que no es posible. Luego viene nodo B y nodo C también disponible y luego E , F y G venir.

Algoritmo:

Para resolver este problema se sigue este proceso:

  1. Tomamos dos pilas y un conjunto. Utilizamos el conjunto para marcar los nodos.
  2. Empezamos con cualquiera de los vértices y empujarla dentro de la pila y se marca (inserto en el conjunto).
  3. Tomamos el elemento superior y el registro class sus vértices adyacentes no visitados si es que existe después empuje en la pila y si no, entonces todo se visitan los nodos, por tanto, que el pop que el nodo de la pila y lo coloca en la otra pila.
  4. Repetimos el paso 3 hasta que visitamos todos los nodos.

implementación en C ++:

#include <bits/stdc++.h>
using namespace std;
void addedge(list<int>* ls, int x, int y)
{
ls[x].push_back(y);
}
string topological_sort(list<int>* ls, int k)
{
char arr[k];
stack<int> s;
set<int> st;
int ind = k - 1;
for (int i = k - 1; i >= 0; i--) {
if (st.find(i) == st.end()) {
s.push(i);
st.insert(i);
//check all the non visited nodes
while (!s.empty()) {
int p = s.top();
list<int>::iterator it;
int temp = 0;
//check its adjacent non visited nodes
for (it = ls[p].begin(); it != ls[p].end(); it++) {
if (st.find(*it) == st.end()) {
st.insert(*it);
s.push(*it);
temp = 1;
}
}
//if all adjaceny nodes are visited then pop that element from stack
if (temp == 0) {
char ch = (char)(p + 'A');
arr[ind] = ch;
ind--;
s.pop();
}
}
}
}
return arr;
}
int main()
{
int k = 7;
list<int> ls[k];
addedge(ls, 0, 2);
addedge(ls, 0, 3);
addedge(ls, 1, 2);
addedge(ls, 1, 4);
addedge(ls, 4, 5);
addedge(ls, 3, 5);
addedge(ls, 5, 6);
cout << topological_sort(ls, 7) << endl;
return 0;
}

salida

ABCDEFG


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *