Actualmente estoy siguientes Steve Yegge del asesoramiento en la preparación de una técnica de programación de la entrevista: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

En su sección sobre los Gráficos, afirma:

Hay tres formas básicas de
representar un gráfico en la memoria (objetos
y punteros, la matriz de adyacencia y
de la lista), y que usted debe conocer
a sí mismo con cada representación y
sus pros y sus contras.

Los pros y los contras de la matriz de adyacencia y la lista de representaciones se describen en CLRS, pero no he sido capaz de encontrar un recurso que compara estas a un objeto de la representación.

Con sólo pensar en ella, puedo deducir algunos de esto por mí mismo, pero me gustaría asegurarse de que no me perdí de algo importante. Si alguien puede describir de esta manera exhaustiva, o me apunte a un recurso que no es así, me sería de gran aprecio.

InformationsquelleAutor jbeard4 | 2011-05-04

4 Comentarios

  1. 90

    objetos y punteros

    Estos son sólo los de base datastructures como hammar dijo en la otra respuesta, en Java que representaría este con clases como en las aristas y los vértices. Por ejemplo, una arista conecta dos vértices y puede ser dirigido o no dirigido y puede contener un peso. Un vértice puede tener un ID, nombre, etc. Sobre todo dos de ellos tienen propiedades adicionales. Así que usted puede construir su gráfica con ellos como

    Vertex a = new Vertex(1);
    Vertex b = new Vertex(2);
    Edge edge = new Edge(a,b, 30); //init an edge between ab and be with weight 30  
    

    Este enfoque se utiliza comúnmente para el orientado a objetos, implementaciones, ya que es más legible y conveniente para el objeto orientado a los usuarios ;).

    matriz

    Una matriz es una simple matriz de 2 dimensiones. Asumiendo que usted tiene vértice ID que puede ser representada como una matriz int como este:

    int[][] adjacencyMatrix = new int[SIZE][SIZE]; //SIZE is the number of vertices in our graph
    adjacencyMatrix[0][1] = 30; //sets the weight of a vertex 0 that is adjacent to vertex 1
    

    Esto es comúnmente usado para densa gráficos donde el índice de acceso es necesario. Se puede representar de la onu/dirigido y ponderado de la estructura con esto.

    lista de adyacencia

    Esto es sólo una simple discbased mezcla, por lo general implementar esta usando un HashMap<Vertex, List<Vertex>>. Similar que se utiliza puede ser el HashMultimap en la Guayaba.

    Este enfoque es genial, porque usted tiene O(1) (amortizado) vértice de búsqueda y me devuelve una lista de todos los vértices adyacentes a este particular vértices que yo exigía.

    ArrayList<Vertex> list = new ArrayList<>();
    list.add(new Vertex(2));
    list.add(new Vertex(3));
    map.put(new Vertex(1), list); //vertex 1 is adjacent to 2 and 3
    

    Este se utiliza para representar escasa gráficos, si usted está solicitando a Google, usted debe saber que el webgraph es escasa. Usted puede tratar con ellos de una forma más escalable mediante una BigTable.

    Ah, y por CIERTO, aquí es un muy buen resumen de este post con lujo de fotos 😉

    • Este enfoque es genial, porque usted tiene O(1) el vértice de búsqueda esta complejidad es un poco mal, en particular es O(1+alfa) donde alfa = número de ranuras en el hash mapa / número de vértices. Por lo tanto propongo que se utilice matriz en lugar de hash mapa
    • es O(1) amortizado. Su complejidad de cálculo está fuertemente la implementación dependend. Ver el javadoc de HashMap (docs.oracle.com/javase/7/docs/api/java/util/HashMap.html) dice: This implementation provides constant-time performance for the basic operations = O(1) amortizado.
    • O(1) y O(1) amortizado son diferentes complejidades, ¿no? Por supuesto que estamos hablando aquí acerca de hash mapa de la implementación de la matriz de listas (no lista de listas, por ejemplo) y O(1+alfa) es correcta la complejidad de la operación
    • Creo que aquí todo el mundo sabe que la matriz de acceso es más rápido que cualquier HashTable de uso. Así que no hay necesidad de ser quisquilloso gira con una pequeña constante alfa sobrecarga que puede ser descuidado.
    • Por favor, no me malinterpreten, no me ofendo bonita respuesta, pero tengo la sensación de que su respuesta puede ser mejorado, así que ¿por qué no hablar de ello aquí 🙂
    • He añadido la amortizado nota en la respuesta. Gracias.
    • No se puede, básicamente, pensar de cada objeto complejo como un tipo de grafo dirigido? Si usted quiere, decir, serializar algo, básicamente, utilizando el gráfico de recorrido de los algoritmos, derecho?
    • El enlace a DZone en la última frase tiene algunos muy «interesante» tiempo de complejidad de la gráfica de las operaciones en una lista de adyacencia. Probablemente voy a añadir una nota que estas complejidades completo dependerá de cómo la lista de adyacencia es implementado y no debe ser tomado en su valor nominal.
    • Me parece que su descripción y hammar la descripción de los Objetos y los Punteros’ son bastante diferentes. Se está creando una nueva Edge objeto, mientras que hammar es mantener a los punteros a los vecinos dando nombres explícitos. Pero usted está diciendo que «Estos son sólo los de base datastructures como hammar dijo en la otra respuesta». Haría de esto un poco más claro?

  2. 7

    Objetos y punteros es todo lo mismo que la lista de adyacencia, al menos para el propósito de la comparación de los algoritmos que utilizan estas representaciones.

    Comparar

    struct Node {
        Node *neighbours[];
    };
    

    con

    struct Node {
        Node *left;
        Node *right;
    };
    

    Usted puede construir fácilmente la lista de vecinos sobre la marcha en el último caso, si es más fácil de trabajar que el nombre de punteros.

  3. 4

    Ventaja de la representación del objeto (la incidencia de la lista) es que dos vértices adyacentes comparten la misma instancia de la orilla. Esto hace que sea fácil de manipular con grafo borde de datos (tiempo, costo, flujo o incluso la dirección). Sin embargo, se utiliza la memoria adicional para los punteros.

  4. 1

    Otro buen recurso: Khan Academy – «Representación De Gráficos»

    Además de la lista de adyacencia y de la matriz de adyacencia, que la lista de «borde de las listas», como un 3er tipo de representación gráfica. Un borde lista podría ser interpretado como una lista de «borde de los objetos», como los de Thomas «los objetos y los punteros» respuesta.

    Ventaja: podemos almacenar más información sobre el borde (mencionado por Michal)

    Desventaja: Es muy lento estructura de datos para trabajar con:

    • Búsqueda de una ventaja: O(log e)
    • Quitar un borde: O(e)
    • Encontrar todos los nodos adyacentes a un nodo en concreto: O(e)
    • Determinar si existe un camino entre dos nodos: O(e^2)

    e = número de aristas

Dejar respuesta

Please enter your comment!
Please enter your name here