Que sont les graphiques, en informatique, et à quoi servent-ils pour? En termes simples de préférence.
Jai lu la définition sur Wikipedia :
En informatique, un graphe est un type de données abstrait qui est destiné à implémenter les concepts de graphe et dhypergraph à partir des mathématiques.
Une structure de données de graphe se compose dun fini (et éventuellement mutable ) ensemble de paires ordonnées, appelées arcs ou arcs, de certaines entités appelées nœuds ou sommets. Comme en mathématiques, on dit quune arête (x, y) pointe ou va de x à y. Les nœuds peuvent faire partie de la structure du graphe , ou peuvent être des entités externes représentées par des indices entiers ou des références.
mais je « recherche une définition moins formelle et plus facile à comprendre.
Commentaires
- Voulez-vous dire graphiquement la structure des données?
- Oui, désolé. Graphiques tels que décrits ici en.wikipedia.org/wiki/Graph_(abstract_data_type) , seul moi ‘ recherche une définition moins formelle, plus facile à comprendre.
- @ Justin984 Liens Wikipédia avec parenthèses (et il y en a tellement) don ‘ t fonctionnent, les parenthèses ne fonctionnent pas ‘ t fonctionne bien avec le format Markdown pour les liens. Maintenant, pour référence future, veuillez ajouter des clarifications à votre question dans la question elle-même, pas dans les commentaires, elles ne sont ‘ que visibles et ‘ s facile de les manquer. Je ‘ modifierai votre commentaire ci-dessus dans la question …
- @ Justin984 Notez également que Informatique Stack Exchange pourrait être un peu plus approprié pour des questions comme celle-ci que pour les programmeurs. ‘ ne vous méprenez pas, la question est parfaitement sur le sujet ici, et elle a obtenu dexcellentes réponses, mais cela ne ‘ pas mal si vous avez vérifié une communauté qui ‘ est un peu plus concentrée sur les concepts informatiques de base que nous (ne ‘ publier la même question dans si vous le publiez sur le mauvais site, nous pouvons le déplacer automatiquement vers le bon).
Réponse
Un exemple parfait pour un profane peut être Facebook . Le réseau de vous, vos amis et leurs amis, etc. sont collectivement appelés graphe social .
Dans ce « graphique », les personnes sont considérées comme nœuds du graphe et le
les bords sont des liens damitié .
Dans Facebook, ami est une relation bidirectionnelle (A est lami de B => B est lami de A) donc le graphique est un Graphique non dirigé . Un réseau comme Google+ ou Twitter serait considéré comme un Graphique dirigé car la direction de la relation a ici un sens.
Tous ces graphiques sont appelés graphiques cycliques , car les relations entre les nœuds peuvent former des cycles . Un Arbre généalogique , en revanche, est un type particulier de graphique qui, entre autres, est Acyclique car il ne peut pas y avoir de cycles dans la relation de larbre généalogique. (Il est techniquement appelé un Graphe acyclique dirigé (DAG) car il est à la fois dirigé et acyclique)
Cela devrait couvrir tout le jargon de base impliquant des graphiques, donc maintenant vous devriez être en mesure de suivre le reste du matériel sur le terrain.
Commentaires
- Est-ce que ‘ ne peut pas le croire ‘ t me vient à lesprit quil ‘ sappelle lAPI du graphique facebook. Bon exemple!
- Larbre généalogique nest pas cyclique? Cela ne devrait ‘ t être, mais malheureusement …
- @MarjanVenema, larbre généalogique est cyclique ? (Il ‘ est un graphe orienté, donc la direction est importante pour déterminer les cycles, et probablement les relations détape don ‘ t vraiment compter.)
- @dbaupp: Je nai aucune envie dentrer dans les détails ici, donc je ‘ je nen mentionnerai quun mot: inceste.
- @MarjanVenema, vous ‘ manquez mon point.Un cycle dans un graphe orienté est un modèle comme
A -> B -> C -> A(cest-à-dire un cercle de flèches), linceste donne simplementA -> B -> CetA -> D -> C(cest-à-dire un diamant). Un cycle dans un arbre généalogique nécessite un voyage dans le temps.
Réponse
Les graphiques sont lun des concepts mathématiques les plus importants utilisé en informatique.
Vous avez vu des graphiques plusieurs fois. Imaginez que vous prenez un vol en avion dune ville à une autre. Vous trouverez inévitablement un joli magazine sur papier glacé de la compagnie aérienne sur le siège poche devant vous. À larrière de ce magazine, vous pouvez presque toujours trouver une carte qui représente les villes desservies par cette compagnie aérienne représentées sous forme de cercles, les vols qui relient ces villes étant représentés par des lignes courbes. Cest « un graphe! Les villes, représentées par des cercles, sont les nœuds de ce graphe et les vols, représentés par des lignes courbes, sont les arêtes. Les graphes sont juste des choses avec des nœuds et des arêtes qui connectent des nœuds.
Vous pouvez embellir ces graphiques simples de différentes manières. Vous ne voulez pas voir juste un tas de cercles et de lignes lorsque vous regardez cette carte. Ces villes ont des noms. Létiquetage de ces villes donne un graphique étiqueté. (Vous pouvez également étiqueter les bords, par exemple, le vol 1234.) Linformatique associe souvent des données aux nœuds, parfois aux arêtes, mais ce nest quune extension de létiquette. Cest toujours un graphique étiqueté. Un autre embellissement se produit si vous pouvez voler directement de la ville A à la ville B, mais pas de la ville B à la ville A. Une façon évidente de le représenter est de mettre une flèche sur la ligne qui relie les villes. pour illustrer cette relation unidirectionnelle. Vous avez maintenant un graphe orienté.
Les listes liées, les arbres, les diagrammes de transition détat et de nombreuses autres structures de données informatiques sont tous des exemples de graphes. Cest un outil très puissant concept.
Commentaires
- Je ‘ d étendre cet exemple pour noter que tous les entités décrites dans votre exemple pourraient être représentées sous forme de sommets dans un graphe (ville, avion, magazine, carte, etc.), la carte elle-même nétant quun seul sommet.
Réponse
Une meilleure question serait « A quoi ne servent-ils » pas les graphiques? « . Linformatique est, à bien des égards, létude des graphes.
Un graphe, en termes simples, est une collection dobjets abstraits arbitraires appelés «nœuds» ou «sommets» qui représentent des points de connexion. Ils sont ensuite connectés via des « chemins » ou des « arêtes ». Le type de données abstrait « Graph » est une implémentation du « graphique » mathématique. Donc, fondamentalement, vous avez des nœuds et des arêtes comme champs et diverses opérations que vous pouvez effectuer sur eux. Vous peut, par exemple, ajouter un nouveau nœud à la collection du graphe (cela pourrait être une liste ou un tableau ou une autre structure selon la langue). Vous pouvez ensuite lier ce nœud aux nœuds existants. Les opérations consisteraient également à parcourir le graphe, à vérifier si deux nœuds partagent une arête (sont connectés), à récupérer des valeurs à partir de nœuds ou darêtes, et la suppression de nœuds ou darêtes du graphe.
En ce qui concerne lutilisation va, les graphiques sont utilisés partout. Le réseautage en fait un usage particulièrement intensif, mais on les trouve dans lintelligence artificielle, lexploration de données, le développement de jeux, la géoinformatique et une foule dautres disciplines. Dans linformatique formelle, ils voient encore plus dutilisation, à savoir comme moyen de représenter un état.
En fait, tout ce que vous pouvez représenter comme un ensemble de connexions peut être représenté sous forme de graphique et implémenté via cet ADT dans certains form.
Voici un exemple de graphique que jai réalisé:
Réponse
Un graphe est juste une collection dobjets reliés entre eux par des lignes appelées sommets.
Le terme « graphe » est une abstraction et une généralisation de plusieurs structures de données utilisées dans le développement de logiciels. Les listes liées, les arbres binaires et les AST « sont tous des graphiques.
En gros, toute collection dobjets qui a des pointeurs qui associent les objets les uns aux autres est un graphique. Une fois que vous avez un graphique, vous pouvez lui appliquer les principes de la théorie des graphes , pour résoudre certains problèmes .