Lo que estoy buscando es una lista completa de algoritmos de cruce de gráficos, con breves descripciones de su propósito, como un punto de partida para investigarlos. Hasta ahora yo sepa:Nombres de Algoritmos de Cruce Gráfico
¿Cuáles son algunos otros bien conocidos queridos? Proporcione una breve descripción de cada algoritmo para cada una de sus respuestas.
los datos conocidos así son:
flujo de red algoritmo
Unos pocos fuera de la parte superior de mi cabeza:
primero en profundidad y en amplitud recorridos, realmente sólo dos maneras diferentes de tocar todos los nodos.
El algoritmo Floyd-Warshall encuentra las rutas más cortas entre cualquier par de puntos, en tiempo (gran-theta) (v^3).
El algoritmo de Prim es una alternativa a Kruskal para MST.
También hay algoritmos para encontrar componentes totalmente conectados, que son grupos de nodos donde puede obtener desde cualquier miembro del componente hasta cualquier otro miembro. Esto solo es importante para "gráficos dirigidos", donde puede atravesar un borde solo en una dirección.
Personalmente, creo que la mejor extensión de la teoría de grafos (no exactamente relacionada con su pregunta, pero si está interesado en aprender más sobre gráficos en general, sin duda vale la pena) son los conceptos de "redes de flujo": http://en.wikipedia.org/wiki/Flow_network. Es una forma de calcular, por ejemplo, la cantidad de electricidad que se puede distribuir sobre las casas con una variedad de necesidades y requisitos de energía, y una variedad de estaciones de energía.
Su comentario es útil y perspicaz. Gracias por tomarse el tiempo y acepté la respuesta. –
El nombre correcto para "componentes totalmente conectados" es * componentes fuertemente conectados *. –
algoritmos de grafos
todos los algoritmos en un solo lugar
Diccionario de algoritmos y estructuras de datos:
Diccionario: http://xlinux.nist.gov/dads/
Por términos TIPO: http://xlinux.nist.gov/dads/termsType.html
Lista de todas las implementaciones en diff. idiomas: http://xlinux.nist.gov/dads/termsImpl.html
Dijkstra's no encuentra el Árbol de expansión mínimo. – KingNestor
Vaya, reverencié los dos en mi lista. Fijo. –
No estoy seguro de por qué esta pregunta fue downvoted, es una pregunta relacionada con la programación legítima, y no es un duplicado. –