La comparaison de l'objet de représentation du graphe d'adjacence de la liste et de la matrice des représentations

Je suis en train de Steve Yegge de conseils sur la préparation d'une programmation technique d'entrevue: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

Dans sa section sur les Graphiques, il déclare:

Il existe trois méthodes de base pour
représenter le graphe dans la mémoire (des objets
et des pointeurs, de la matrice, et la contiguïté
liste), et vous devriez vous familiariser
vous-même à chaque représentation et
ses avantages et inconvénients.

Les avantages et les inconvénients de la matrice et de la contiguïté liste des représentations sont décrites en CLRS, mais je n'ai pas été en mesure de trouver une ressource que de les comparer à un objet de représentation.

Rien qu'en pensant à elle, je peux déduire quelques de moi-même, mais je voudrais m'assurer que je n'ai pas manqué quelque chose d'important. Si quelqu'un pouvait le décrire de manière exhaustive, ou me diriger vers une ressource qui agit de la sorte, je vous en serais très reconnaissante.

InformationsquelleAutor jbeard4 | 2011-05-04
  1. 89

    des objets et des pointeurs

    Ce sont juste des structures de données de base comme hammar a dit dans l'autre réponse, en Java vous représenter ce avec des classes comme les arêtes et les sommets. Par exemple une arête relie deux sommets et peut être orienté ou non orienté, et il peut contenir un poids. Un sommet peut avoir un ID, nom, etc. Surtout deux d'entre eux ont des propriétés supplémentaires. De sorte que vous pouvez construire votre graphique avec eux comme

    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

    Cette approche est couramment utilisé pour l'orienté objet implémentations, car il est plus lisible et pratique pour objet orienté vers les utilisateurs ;).

    matrice

    Une matrice est juste un simple 2 dimensions tableau. En supposant que vous avez des ID de sommet qui peut être représenté comme un tableau int comme ceci:

    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

    Ceci est couramment utilisé pour les dense graphiques où l'indice d'accès est nécessaire. Vous pouvez représenter des nations unies/mise en scène et pondérée de la structure.

    liste d'adjacence

    C'est juste une simple discbased mix, j'ai l'habitude de mettre en œuvre ce à l'aide d'un HashMap<Vertex, List<Vertex>>. Similaire utilisé peut être le HashMultimap dans la Goyave.

    Cette approche est cool, parce que vous avez O(1) (amorti) vertex de recherche et il me renvoie une liste de tous les sommets adjacents à ce vertex j'ai demandé. 

    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

    Ce est utilisé pour représenter les graphes éparses, si vous demandez à Google, vous devez savoir que le webgraph est clairsemée. Vous pouvez répondre dans les plus de manière évolutive à l'aide d'un BigTable.

    Oh et BTW, ici est un très bon résumé de ce post avec de jolis photos 😉

    • Cette approche est cool, parce que vous avez O(1) vertex de recherche cette complexité est légèrement faux, en particulier, il est O(1+alpha) où alpha = nombre de logements du hash map / nombre de sommets. Par conséquent, je propose d'utiliser de tableau au lieu de hachage carte
    • il est O(1) amorti. Votre la complexité de calcul est fortement mise en œuvre dependend. Voir la javadoc de HashMap (docs.oracle.com/javase/7/docs/api/java/util/HashMap.html), il est dit: This implementation provides constant-time performance for the basic operations = O(1) amorti.
    • O(1) et O(1) amorti sont de différentes complexités, n'est-ce pas? Bien sûr, nous parlons ici de hachage de la carte de mise en œuvre en tant que tableau de listes (pas de liste de listes, par exemple) et O(1+alpha) est correct complexité de l'opération GET
    • Je pense que tout le monde ici sait que la matrice de l'accès est plus rapide que tout HashTable d'utilisation. Donc pas besoin de pinailler balader avec une petite constante alpha frais généraux qui peuvent être négligés.
    • S'il vous plaît ne vous méprenez pas, je ne pas vous offenser belle réponse, mais j'ai le sentiment que votre réponse peut être amélioré, alors pourquoi ne pas en parler ici 🙂
    • J'ai ajouté l'amorti remarque dans la réponse. Merci.
    • Ne pouvez-vous pas fondamentalement pense chaque objet complexe comme une sorte de graphe orienté? Si vous voulez, disons, sérialiser quelque chose, vous êtes essentiellement en utilisant le graphique de la traversée des algorithmes, droit?
    • Le lien pour DZone dans la dernière phrase a quelques très "intéressant" le temps de la complexité de graphique des opérations sur une liste d'adjacence. Je serais probablement ajouter une note que ces temps de complexité dépendent complètement comment la liste d'adjacence est mis en œuvre et ne doit pas être pris à la valeur nominale.
    • Je trouve que votre description et hammar la description des Objets et des Pointeurs' sont un peu différentes. Vous êtes à la création d'un nouveau Edge objet, tandis que hammar est de garder les pointeurs pour les voisins de donner des noms explicites. Mais vous dites que "ce sont juste des structures de données de base comme hammar a dit dans l'autre réponse". Voulez-vous faire de cela un peu plus clair?

    InformationsquelleAutor Thomas Jungblut
  2. 7

    Des objets et des pointeurs est essentiellement le même que la contiguïté de la liste, au moins pour fins de comparaison entre les algorithmes qui utilisent ces représentations.

    Comparer

    struct Node {
    Node *neighbours[];
};

    avec

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

    Vous pouvez facilement construire la liste des voisins à la volée dans ce dernier cas, si c'est plus facile à travailler que nommé pointeurs.

    InformationsquelleAutor hammar
  3. 4

    Avantage de la représentation d'objet (l'incidence de la liste) est que deux sommets adjacents partagent la même instance de l'arête. Cela rend plus facile à manipuler avec des non-orienté de données edge (durée, coût, le débit ou même direction). Cependant, il utilise de la mémoire supplémentaire pour les pointeurs.

    InformationsquelleAutor Michal Čizmazia
  4. 1

    Une autre bonne ressource: Khan Academy - "Le Fait De Représenter Des Graphes"

    En plus de liste d'adjacence et de la matrice de contiguïté, on trouve une liste de "bord de listes" comme un 3ème type de représentation graphique. Un bord liste pourrait être interprété comme une liste de "edge objets" comme ceux de Thomas "des objets et des pointeurs" réponse.

    Avantage: On peut stocker plus d'informations sur l'arête (mentionné par Michal)

    Inconvénient: C'est un très lente structure de données pour travailler avec:

    • Recherche d'un bord: O(log e)
    • Supprimer une arête: O(e)
    • Trouver tous les nœuds adjacents à un nœud donné: O(e)
    • De déterminer s'il existe un chemin entre deux nœuds: O(e^2)

    e = nombre d'arêtes

    InformationsquelleAutor Chris Leung