La question de la façon graphiques sont enseignées

Question

Je suis de l'Argentine, mais je pense que tout le monde qui a jamais prendre un savoir classe Structures de données ce qu'un graphique est. Si vous le faites, vous savez peut-être ce genre de mises en œuvre sont « communs » ou « standar ». Il peut être mis en œuvre par le biais d'une liste ou un tableau. Même Wikipedia dit cela. Ainsi que Mark Allen Weiss, Bruno Preiss et Luis Aguilar Joyanes.

La chose est. Personne n'a jamais pensé que ce n'est pas une bonne façon de le faire? La façon la plus recommandée est par une liste. Mais considéré que les sommets peuvent avoir un seul bord entre eux, je ne pense pas qu'une liste est la bonne interface pour le faire. Je veux dire, si le Vertex V1 est relié à Vertex V2, alors il n'y a qu'un seul et un seul bord.

Ne pensez-vous que ce serait un ensemble au lieu d'une liste?

Class Vertex{
    private Set edges;
    private Object data;

    /** Methods**/
}

Je veux juste savoir quelques opinions, que pensez-vous?

Merci !!

Edit: , Si l'on pense aussi que le graphique ne peut pas avoir des éléments répétés, un HashSet serait un bon choix pour minimiser la recherche du sommet dans l'insertion.

Answer 1

Vous avez raison de souligner que les contiguïtés pour un sommet sont plus modélisés avec précision par un ensemble (ou dans le cas d'un multigraphe, un multiset). Alors, pourquoi les structures de données des livres écrivent sur les tableaux et les listes chaînées au lieu? Je peux penser à trois raisons:

1. L'idée que les langages de programmation doivent inclure des ensembles comme un type de données primitive est assez récente. écrivains plus âgés auraient pas pensé à utiliser, et les écrivains modernes ont tendance à suivre les traditions du champ.

2. L'un des objectifs d'une structure de données est bien sûr pour vous permettre de réfléchir à la représentation des données à un niveau bas niveau (béton), ainsi qu'à un haut (résumé). Un ensemble est un type abstrait qui (contrairement à des listes chaînées et tableaux) ne dispose pas d'une mise en œuvre à faible niveau évident: certains jeux sont mieux représentés sous forme de listes liées, certains comme les tables de hachage, certains sous forme de tableaux, et ainsi de suite. Il est donc bien sûr naturel pour une structure de données pour sauter sur la représentation de haut niveau des ensembles à leur mise en œuvre à faible niveau, que vous devez savoir sur toute façon, afin d'analyser le comportement des algorithmes qui les utilisent.

3. Il est important de ne pas être dogmatique sur la façon de représenter les types de données, parce que les algorithmes peuvent être plus efficacement exprimées à l'aide des représentations particulières. Exemple 1. Pour compter les chemins de longueur n entre chaque paire de sommets dans un graphe, représentent le graphique par sa matrice de contiguïté et augmenter la matrice à la puissance n . Si vous insistez pour représenter les contiguïtés d'un sommet comme un ensemble d'arêtes, alors vous raterez cet algorithme (qui peut être parallélisé en utilisant des techniques standard). Exemple 2. algorithme « Liens Dancing » de Knuth pour le problème de la couverture exacte représente ensembles de colonnes en utilisant listes doublement chaînées, de sorte que les liens d'éléments supprimés peuvent être réutilisés pour retours en arrière efficace.

Answer 2

A relativement supérieur niveau de programmeur de C / C, comment un graphique / réseau est mis en œuvre dépend très fortement de ce que les opérations sont effectuées à ce sujet. Être une personne OU moi-même, je suis sans doute biaisé dans ma réponse / exemple. Certains des algorithmes les plus efficaces qui peuvent être mises en œuvre sur les graphes / réseaux sont algorithmes polynomiaux. La plupart, sinon tous, algorithmes polynomiaux je peux penser (le plus court chemin de problème de Dijkstra, problème de transport, problème max-débit, etc.) sont des cas particuliers du problème minimum coût-débit (MCF). Informatiquement, l'un des moyens les plus efficaces de résoudre un problème MCF est par l'algorithme de réseau simplex (ce qui en soi est une spécialisation de l'algorithme simplex pour résoudre un programme linéaire général).

Dans le réseau simplex algorithme, un arbre Spanning (sur l'ensemble des nœuds) doit être efficacement représentée. Pour représenter un arbre couvrant dans un graphique, une variété de structures de données peuvent être utilisées. Ceux-ci comprennent le noeud suivant de longueur

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

Dans les implémentations les plus efficaces d'algorithmes simplex-réseau que je suis venu à travers, ceux-ci ne sont pas représentés sous forme de tableaux, mais une sorte de bloc créé dynamiquement de la mémoire via

calloc(number_of_nodes, sizeof(struct vertex));

Je ne suis pas sûr (à un niveau relativement bas niveau) interne au compilateur quoi / comment cette allocation de mémoire est mis en œuvre -. Que ce soit une liste / jeu /

Donc, en résumé, le meilleurs façon de mettre en œuvre un graphique est très dépendant des opérations à effectuer sur elle.

algorithme de réseau et les structures de données nécessaires pour mettre en œuvre efficacement les mêmes se trouvent dans ce livre .

Answer 3

A la plus abstraite, un ensemble a un prédicat pour vérifier si un élément est dans l'ensemble. Il peut également soutenir les opérateurs qui fournissent l'union et de l'intersection. La différence est pas calculable nécessaire.

A la plus abstraite, un soutien de la liste itération, sous-liste, et append.

La plupart des algorithmes sur les graphes vous obligent à itérer sur les bords, donc une structure qui supporte l'itération est préférée. La plupart des algorithmes ne tentent pas d'ajouter le même bord deux fois, suppression des doublons n'est pas nécessaire.

Bien sûr, la plupart des jeux dans les bibliothèques sont finies, ensembles extensifs qui prennent en charge l'itération, de sorte que vous pouvez les utiliser, mais vous aussi auriez encore le coût de la vérification des doublons.

Certains systèmes à base de graphiques font ensembles d'utiliser comme mécanisme sous-jacent, mais ils traitent avec des graphes infinis plutôt que des finis, où les ensembles intensionnelles deviennent utiles.