¿Qué son los gráficos, en informática, y para qué se utilizan? En términos laicos preferiblemente.
He leído la definición en Wikipedia :
En informática, un gráfico es un tipo de datos abstractos destinado a implementar los conceptos de gráfico e hipergrafía de las matemáticas.
Una estructura de datos gráficos consta de un conjunto finito (y posiblemente mutable) de pares ordenados, llamados aristas o arcos, de ciertas entidades llamadas nodos o vértices. Como en matemáticas, se dice que una arista (x, y) apunta o va de x a y. Los nodos pueden ser parte de la estructura del gráfico, o pueden ser entidades externas representadas por índices enteros o referencias.
pero estoy buscando una definición menos formal, más fácil de entender.
computer-science
graph
CondiciónRacer
fuente
fuente
Respuestas:
Un ejemplo laico perfecto podría ser Facebook . Su red, sus amigos y sus amigos, etc., se conocen colectivamente como el gráfico social .
En este "gráfico", las personas se consideran nodos del gráfico y los bordes son enlaces de amistad .
En Facebook, el amigo es una relación bidireccional (A es el amigo de B => B es el amigo de A), por lo que el gráfico es un gráfico no dirigido . Una red como Google+ o Twitter se consideraría un Gráfico Dirigido ya que la dirección de la relación tiene significado aquí.
Todos estos gráficos se denominan gráficos cíclicos , ya que las relaciones entre los nodos pueden formar ciclos. Un árbol genealógico , por otro lado, es un tipo especial de gráfico que, entre otras cosas, es acíclico ya que no puede haber ciclos en la relación del árbol genealógico. (Técnicamente se llama Gráfico Acíclico Dirigido (DAG) ya que es dirigido y acíclico)
Esto debería cubrir toda la jerga básica que involucra gráficos, por lo que ahora debería poder seguir el resto del material en el campo.
fuente
A -> B -> C -> A
(es decir, un círculo de flechas), el incesto solo daA -> B -> C
yA -> D -> C
(es decir, un diamante). Un ciclo en un árbol genealógico necesita viajar en el tiempo.Los gráficos son uno de los conceptos matemáticos más importantes utilizados en informática.
Has visto gráficos muchas veces. Imagine que está tomando un vuelo en avión de una ciudad a otra. Inevitablemente, encontrará una bonita revista brillante de la aerolínea en el bolsillo del asiento frente a usted. Cerca de la parte posterior de esa revista, casi siempre puede encontrar un mapa que representa las ciudades atendidas por esa aerolínea representadas como círculos, con los vuelos que conectan esas ciudades representadas como líneas curvas. Eso es un gráfico! Las ciudades, representadas como círculos, son los nodos de este gráfico y los vuelos, representados como líneas curvas, son los bordes. Los gráficos son simplemente cosas con nodos y aristas que conectan los nodos.
Puede embellecer esos gráficos simples de varias maneras. No desea ver solo un montón de círculos y líneas cuando mira ese mapa. Esas ciudades tienen nombres. Etiquetar esas ciudades da como resultado un gráfico etiquetado. (También puede etiquetar los bordes, por ejemplo, el vuelo 1234.) La informática a menudo asocia datos con los nodos, a veces con los bordes, pero eso es solo una extensión de la etiqueta. Todavía es un gráfico etiquetado. Otro adorno resulta si puede volar directamente de la ciudad A a la ciudad B, pero no de la ciudad B a la ciudad A. Una forma obvia de retratar esto es colocar una flecha en la línea que conecta las ciudades para representar esta relación unidireccional. Ahora tienes un gráfico dirigido.
Las listas enlazadas, los árboles, los diagramas de transición de estado y muchas otras estructuras de datos informáticos son ejemplos de gráficos. Es un concepto muy poderoso.
fuente
Una mejor pregunta sería "¿Para qué no se utilizan los gráficos?". La informática es, en muchos aspectos, el estudio de los gráficos.
Un gráfico, en términos simples, es una colección de objetos abstractos arbitrarios llamados "nodos" o "vértices" que representan puntos de conexión. Luego se conectan a través de "caminos" o "bordes". El tipo de datos abstracto "Graph" es una implementación del matemático "Graph". Entonces, básicamente, tiene nodos y bordes como sus campos y varias operaciones que puede realizar en ellos. Puede, por ejemplo, agregar un nuevo nodo a la colección del gráfico (esto podría ser una lista o una matriz o alguna otra estructura dependiendo del idioma). Entonces podría vincular ese nodo a los nodos existentes. Las operaciones también incluirían atravesar el gráfico, verificar si dos nodos comparten un borde (están conectados), recuperar valores de nodos o bordes y la eliminación de nodos o bordes del gráfico.
En cuanto a la utilización, los gráficos se utilizan en todo el lugar. Las redes las utilizan especialmente, pero se encuentran en Inteligencia Artificial, Minería de Datos, Desarrollo de Juegos, Geoinformática y una gran cantidad de otras disciplinas. En informática formal, ven aún más uso, es decir, como una forma de representar el estado.
Efectivamente, cualquier cosa que pueda representar como un conjunto de conexiones puede representarse como un gráfico e implementarse a través de ese ADT de alguna forma.
Aquí hay un gráfico de ejemplo que hice:
fuente
Un gráfico es solo una colección de objetos conectados entre sí por líneas llamadas vértices.
El término "gráfico" es una abstracción y generalización de muchas estructuras de datos utilizadas en el desarrollo de software. Las listas enlazadas, los árboles binarios y los AST son todos gráficos.
Básicamente, cualquier colección de objetos que tiene punteros que asocian los objetos entre sí es un gráfico. Una vez que tenga un gráfico, puede aplicarle los principios de la teoría de gráficos para resolver ciertos problemas .
fuente