Cuestionar la forma en que se imparten las gráficas

Question

Soy de Argentina, pero yo creo que todo el mundo que haya tomar una clase know estructuras de datos lo que es una gráfica. Si lo hace, es posible que sepa qué tipo de implementaciones son "común" o "estandar". Puede ser implementado a través de una lista o una matriz. Incluso Wikipedia dice esto. Así como Mark Allen Weiss, Bruno Preiss y Luis Joyanes Aguilar.

Lo es. Nadie ha pensar que esto no es una buena manera de hacerlo? La forma más recomendada es a través de una lista. Pero consideró que los vértices pueden tener sólo una arista entre ellos, no creo que una lista es la interfaz bueno hacer esto. Es decir, si el vértice V1 está conectado con vértice V2, entonces sólo hay uno y sólo uno de los bordes.

¿No te parece que sería un conjunto en lugar de una lista?

Class Vertex{
    private Set edges;
    private Object data;

    /** Methods**/
}

Sólo quiero saber algunas opiniones, ¿qué te parece?

Gracias !!

Editar Además, si pensamos que la gráfica no puede tener elementos repetidos, un HashSet sería una opción buena para reducir al mínimo las operaciones de búsqueda del vértice en la inserción.

Answer 1

Tienes razón en señalar que las adyacencias de un vértice se modelan con mayor precisión por un conjunto (o en el caso de un multigrafo, un conjunto múltiple). Entonces, por qué estructuras de datos libros escriben sobre matrices y listas enlazadas en su lugar? Se me ocurren tres razones:

1. La idea de que los lenguajes de programación deben incluir conjuntos como un tipo de datos primitivo es bastante reciente. escritores más antiguos no hubieran considerado el uso de ella, y los escritores modernos tienden a seguir las tradiciones del campo.

2. Uno de los propósitos de un curso de estructuras de datos es permitirle a pensar en la representación de los datos en un nivel bajo (hormigón), así como en un nivel alto (resumen). Un conjunto es un tipo de datos abstracto que (a diferencia de las listas y matrices vinculadas) no tiene una aplicación obvia de bajo nivel: algunos conjuntos están mejor representados como listas enlazadas, algunos como tablas hash, algunos como matrices, y así sucesivamente. Por lo que es natural para una estructura de datos supuesto para saltar sobre la representación de alto nivel de los conjuntos a su ejecución bajo nivel, lo que hay que saber acerca de todos modos con el fin de analizar el comportamiento de los algoritmos que los utilizan.

3. Es importante no ser dogmático acerca de cómo representar tipos de datos, ya que los algoritmos se pueden expresar de manera más eficiente el uso de representaciones particulares. Ejemplo 1. Para contar los caminos de longitud n entre cada par de vértices en un gráfico, representan el gráfico por su matriz de adyacencia y elevar la matriz a la potencia n . Si insiste en que representa las adyacencias de un vértice como un conjunto de aristas, entonces se perderá este algoritmo (que se puede paralelizar usando técnicas estándar). Ejemplo 2. Knuth de " baile Enlaces " algoritmo para el problema de cobertura exacta representa conjuntos de columnas usando lista doblemente enlazada, por lo que los enlaces de los elementos eliminados se pueden reutilizar para dar marcha atrás eficiente.

Answer 2

En un tiempo relativamente mayor C / C ++ nivel de programador, cómo se implementa un gráfico / red depende muy fuertemente de lo que las operaciones se realizan en él. Al ser una persona O a mí mismo, probablemente estoy predispuesto en mi respuesta / ejemplo. Algunos de los algoritmos más eficientes que se pueden implementar en los gráficos / redes son algoritmos en tiempo polinómico. La mayoría, si no todos, los algoritmos de tiempo polinomial se me ocurre (problema del camino más corto, problema de transporte, un problema de flujo máximo de Dijkstra, etc.) son casos especiales del costo mínimo de flujo (FCM) problema. Computacionalmente, una de las maneras más eficaces de resolver un problema de MCF es a través del algoritmo de red simple (que en sí mismo es una especialización del algoritmo simplex para resolver un problema de programación lineal general).

En la red simplex-algoritmo, un árbol de expansión (sobre el conjunto de nodos) necesita ser representado de manera eficiente. Para representar un árbol de expansión en un gráfico, una variedad de estructuras de datos se puede utilizar. Estos incluyen los siguientes nodo de longitud

predecessor[], thread[] and depth[] arrays.

En las implementaciones más eficientes de la red simplex algoritmos que me he encontrado, éstos no están representados como matrices, sino una especie de bloque creado de forma dinámica a través de la memoria

calloc(number_of_nodes, sizeof(struct vertex));

No estoy seguro (a una relativamente menor Nivel) interno al compilador qué / cómo se implementa esta asignación de memoria -. Si se trata de una lista / set / mapa

Así que, en resumen, el mejor forma de implementar un gráfico es altamente dependiente de las operaciones a realizar en él.

algoritmo de red simple y las estructuras de datos necesarios para aplicar eficazmente el mismo se pueden encontrar en este libro .

Answer 3

En su forma más abstracta, un conjunto tiene un predicado para probar si un elemento se encuentra dentro del conjunto. También puede apoyar a los operadores que proporcionan la unión y la intersección. La diferencia no es computable necesario.

En su forma más abstracta, una lista soportes de iteración, sub-lista, y la anexión.

La mayoría de los algoritmos sobre grafos que requieren para iterar sobre los bordes, por lo que se prefiere una estructura que soporta iteración. La mayoría de los algoritmos no intentan añadir el mismo borde en dos ocasiones, por lo que no se requiere la eliminación de duplicados.

Por supuesto, la mayoría de los juegos en las bibliotecas son conjuntos finitos, extensionales que también apoyan la iteración, por lo que podría usarlas, aunque todavía tendría el costo de la comprobación de duplicados.

Algunos sistemas basados ??en gráficos hacen uso conjuntos como el mecanismo subyacente, sino que se trata de infinitas gráficos en lugar de los conjuntos finitos, donde intensionales llegar a ser útil.