Herramientas de usuario
algoritmos-oia:grafos-dirigidos:toposort
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Próxima revisión | Revisión previa | ||
|
algoritmos-oia:grafos-dirigidos:toposort [2017/12/10 07:26] sebach creado |
algoritmos-oia:grafos-dirigidos:toposort [2017/12/26 19:14] (actual) sebach ↷ Page moved from algoritmos-oia:toposort to algoritmos-oia:grafos-dirigidos:toposort |
||
|---|---|---|---|
| Línea 3: | Línea 3: | ||
| En este post, trataremos el problema de, dado un grafo dirigido, ubicar todos los nodos en una lista de manera que no exista una arista que vaya desde un nodo que está más atrás en la lista a uno de más adelante. | En este post, trataremos el problema de, dado un grafo dirigido, ubicar todos los nodos en una lista de manera que no exista una arista que vaya desde un nodo que está más atrás en la lista a uno de más adelante. | ||
| Por ejemplo, si tenemos el siguiente grafo: | Por ejemplo, si tenemos el siguiente grafo: | ||
| + | |||
| {{:algoritmos-oia:graph_4_.png?300|}} Un orden posible podría ser $\{1,0,2,4,5,3\}$. | {{:algoritmos-oia:graph_4_.png?300|}} Un orden posible podría ser $\{1,0,2,4,5,3\}$. | ||
| Línea 16: | Línea 17: | ||
| En fin, hay muchas situaciones en las que este ordenamiento es importante, y vamos a ver cómo podemos encontrar un posible ordenamiento. | En fin, hay muchas situaciones en las que este ordenamiento es importante, y vamos a ver cómo podemos encontrar un posible ordenamiento. | ||
| - | En estos casos, la arista $u->v$ indica "$u$ debe ir antes que $v$", y entonces armaremos la lista ordenada de manera de no contradecir a ninguna arista. | + | En estos casos, la arista $u \rightarrow v$ indica "$u$ debe ir antes que $v$", y entonces armaremos la lista ordenada de manera de no contradecir a ninguna arista. |
| ==== Requerimientos ==== | ==== Requerimientos ==== | ||
| Línea 90: | Línea 91: | ||
| [[http://www.spoj.com/problems/TOPOSORT/|Toposort]], simplemente para practicar codear desde cero el algoritmo, sin nada raro. | [[http://www.spoj.com/problems/TOPOSORT/|Toposort]], simplemente para practicar codear desde cero el algoritmo, sin nada raro. | ||
| + | |||
| [[http://codeforces.com/contest/510/problem/C|Que queden ordenados alfabéticamente]] | [[http://codeforces.com/contest/510/problem/C|Que queden ordenados alfabéticamente]] | ||
| + | |||
| [[http://www.spoj.com/problems/RPLA/|Ranking]] | [[http://www.spoj.com/problems/RPLA/|Ranking]] | ||
algoritmos-oia/grafos-dirigidos/toposort.1512890806.txt.gz · Última modificación: 2017/12/10 07:26 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
