ADT approprié pour les graphiques

Question

Quelles sont les structures de données appropriées pour les graphiques?

Je suppose que la réponse varie selon le type de graphique?

dans tous les cas, des recommandations?

Answer 1

Voyant que vous voulez un résumé type de données, je ne mentionnerai rien à propos de l'implémentation.

Un graphe G = <V, E> est un ensemble de sommets V, et un ensemble d'arêtes E où chaque élément de E est un tuple e = <v1, v2> et v1 et v2 sont en V.

Ce qui suit peut ressembler à Java, mais je suis vraiment penser à une langue suffisamment expressive:

interface Graph { 
    Set getVertices(); 
    Set getEdges(); 
    void addVertex(Object v); 
    void addEdge(Object v1, Object v2); 
    void removeVrtex(Object v); 
    void removeEdge(Object v1, Object v2); 
} 

Je pense que c'est le strict minimum. Je n'ai pas spécifié ce qui est retourné par getEdges; Si la langue a un type de n-uplet natif, il en existe un ensemble. Dans la pratique, vous voulez ajouter des méthodes supplémentaires telles que:

int getDegree(Object v); 
void contractEdge(Object v1, Object v2); 
boolean isIsthmus(Object v1, Object v2); /* does removal of this edge increase the number of components? */ 
int numComponents(); 
boolean isConnected(); /* return numComponents() <= 1 */ 
boolean isCycle(Set path); /* path is a set of edges. */ 

etc.

L'extension à d'digraphs est laissé en exercice :-).

Answer 2

Lorsque le graphique est clairsemé, un Map<Vertex, List<Vertex>> (1) fera l'affaire. Si c'est dense, un tableau 2D peut également être utilisé (2).

Voir:

(1) http://en.wikipedia.org/wiki/Adjacency_list

(2) http://en.wikipedia.org/wiki/Adjacency_matrix

Answer 3

Deux des structures les plus courantes pour les graphes stockage sont adjacency lists et adjacency matrices. Ce que vous devez utiliser dépend généralement de ce que vous avez l'intention de faire avec le graphique (car l'un peut fournir des temps de manipulation/accès plus optimaux que l'autre pour un algorithme donné), et de la densité ou de la densité du graphique. plus compacts pour les graphes épars, les matrices ont moins de surdébit relatif, plus le graphe est dense).