Comparaison de la représentation graphique d'objet à la liste de contiguïté et aux représentations matricielles

Question

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 son article sur les Graphes, 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.

Answer 1

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 commly utilisé pour l'orienté objet implémentations, car il est plus lisible et pratique pour objet orienté vers les utilisateurs ;).

la 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

C'est commly 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>>. Similaires utilisés peuvent être l' 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 à la fantaisie des images ;)

Answer 2

Les objets et les pointeurs sont essentiellement identiques à la liste de contiguïté, du moins dans le but de comparer des algorithmes utilisant 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, s'il est plus facile de travailler avec les pointeurs nommés.

Answer 3

L'avantage de la représentation de l'objet ( liste d'incidence ) est que deux sommets adjacents partagent la même instance du bord. Cela facilite la manipulation avec des données de bord non orientées (longueur, coût, flux ou même direction). Cependant, il utilise plus de mémoire pour les pointeurs.