O que são gráficos em ciência da computação e como eles são usados pra? Em termos leigos, de preferência.
Li a definição na Wikipedia :
Em ciência da computação, um gráfico é um tipo de dado abstrato que se destina a implementar os conceitos de gráfico e hipergrafo da matemática.
Uma estrutura de dados de gráfico consiste em uma estrutura finita (e possivelmente mutável ) conjunto de pares ordenados, chamados de arestas ou arcos, de certas entidades chamadas de nós ou vértices. Como na matemática, diz-se que uma aresta (x, y) aponta ou vai de x para y. Os nós podem fazer parte da estrutura do gráfico , ou podem ser entidades externas representadas por índices inteiros ou referências.
mas estou procurando uma definição menos formal e mais fácil de entender.
Comentários
- Você quer dizer gráficos da estrutura de dados?
- Sim, desculpe. Gráficos conforme descrito aqui en.wikipedia.org/wiki/Graph_(abstract_data_type) , apenas eu ‘ estou procurando uma definição menos formal e mais fácil de entender.
- @ Justin984 Links da Wikipedia com parênteses (e há tantos deles) não ‘ não funcionam, os parênteses não ‘ t funcionam bem com o formato Markdown para links. Agora, para referência futura, acrescente quaisquer esclarecimentos à sua pergunta na própria pergunta, não nos comentários, eles não são ‘ tão visíveis e ‘ s fácil perdê-los. Eu ‘ editarei seu comentário acima na pergunta …
- @ Justin984 Observe também que Ciência da computação Stack Exchange pode ser um pouco mais apropriado para questões como esta do que para programadores. Não ‘ não me entenda mal, a pergunta está perfeitamente no assunto aqui e obteve ótimas respostas, mas não ‘ faria mal se você conferiu uma comunidade que ‘ é um pouco mais focada nos conceitos básicos da ciência da computação do que nós (não ‘ poste a mesma pergunta em entretanto, se você postar no site errado, podemos movê-lo para o certo automaticamente).
Resposta
O exemplo de um leigo perfeito pode ser o Facebook . A rede de você, seus amigos e seus amigos etc, são coletivamente chamados de gráfico social .
Neste “gráfico” as pessoas são consideradas nós do gráfico e
bordas são links de amizade .
No Facebook, amigo é uma relação bidirecional (A é amigo de B => B é amigo de A), então o gráfico é um Gráfico não direcionado . Uma rede como o Google+ ou Twitter seria considerada um Gráfico direcionado , pois a direção do relacionamento tem um significado aqui.
Todos esses gráficos são chamados de gráficos cíclicos , pois os relacionamentos entre os nós podem formar ciclos . Uma Árvore Familiar , por outro lado, é um tipo especial de gráfico que, entre outras coisas, é Acíclico uma vez que não pode haver ciclos no relacionamento da árvore genealógica. (É tecnicamente chamado de Gráfico acíclico dirigido (DAG) , pois é dirigido e acíclico)
Isso deve abranger todo o jargão básico envolvendo gráficos, então agora você deve ser capaz de acompanhar o resto do material em campo.
Comentários
- Não posso ‘ acreditar que não ‘ ocorreu-me que ‘ é chamado de API de gráfico do Facebook. Bom exemplo!
- Árvore genealógica não cíclica? Não deveria ‘ ser, mas infelizmente é …
- @MarjanVenema, a árvore genealógica é cíclico ? (É ‘ um gráfico direcionado, então a direção é importante para determinar os ciclos e, presumivelmente, as relações das etapas don ‘ não conta realmente.)
- @dbaupp: Não desejo entrar em detalhes aqui, então ‘ mencionarei apenas um palavra: incesto.
- @MarjanVenema, você ‘ está perdendo o meu ponto.Um ciclo em um gráfico direcionado é um padrão como
A -> B -> C -> A(ou seja, um círculo de setas), o incesto apenas forneceA -> B -> CeA -> D -> C(ou seja, um diamante). Um ciclo em uma árvore genealógica precisa de viagem no tempo.
Resposta
Os gráficos são um dos conceitos matemáticos mais importantes usado em ciência da computação.
Você já viu gráficos muitas vezes. Imagine que você está pegando um avião de uma cidade para outra. Você inevitavelmente encontrará uma bela revista da companhia aérea no assento bolso na sua frente. Perto do final da revista, você quase sempre pode encontrar um mapa que retrata as cidades atendidas por aquela companhia aérea representadas como círculos, com os voos que conectam essas cidades representadas como linhas curvas. Isso é um gráfico! As cidades, representadas como círculos, são os nós deste gráfico e os voos, representados como linhas curvas, são as arestas. Os gráficos são apenas coisas com nós e arestas que conectam os nós.
Você pode embelezar esses gráficos simples de várias maneiras. Você não quer ver apenas um monte de círculos e linhas quando está olhando para o mapa. Essas cidades têm nomes. Rotular essas cidades resulta em um gráfico rotulado. (Você também pode rotule as arestas, por exemplo, vôo 1234.) A ciência da computação freqüentemente associa os dados aos nós, às vezes com as arestas, mas isso é apenas uma extensão do rótulo. Ainda é um gráfico rotulado. Outro enfeite resulta se você puder voar diretamente da cidade A para a cidade B, mas não da cidade B para a cidade A. Uma maneira óbvia de retratar isso é colocar uma seta na linha que conecta as cidades para representar essa relação unilateral. Agora você tem um gráfico direcionado.
Listas vinculadas, árvores, diagramas de transição de estado e muitas outras estruturas de dados da ciência da computação são exemplos de gráficos. É um método muito poderoso conceito.
Comentários
- Eu ‘ d estendo esse exemplo para observar que todos entidades descritas em seu exemplo podem ser representadas como vértices em um gráfico (cidade, plano, revista, mapa, etc), o mapa em si sendo apenas um único vértice.
Resposta
Uma pergunta melhor seria “Para que não são usados gráficos?”. A Ciência da Computação é, em muitos aspectos, o estudo de Grafos.
Um gráfico, em termos leigos, é uma coleção de objetos abstratos arbitrários chamados “nós” ou “vértices” que representam pontos de conexão. Eles são então conectados por meio de “caminhos” ou “bordas”. O tipo de dados abstratos “Gráfico” é uma implementação do “Gráfico” matemático. Basicamente, você tem nós e bordas como campos e várias operações que pode realizar neles. pode, por exemplo, adicionar um novo nó à coleção do gráfico (pode ser uma lista ou um array ou alguma outra estrutura dependendo do idioma). Você pode então vincular esse nó aos nós existentes. As operações também incluiriam atravessar o gráfico, verificar se dois nós compartilham uma aresta (estão conectados), recuperando valores de nós ou arestas e a exclusão de nós ou arestas do gráfico.
Quanto à utilização vai, os gráficos são usados em todo o lugar. A rede faz uso particularmente pesado deles, mas eles são encontrados em Inteligência Artificial, Mineração de Dados, Desenvolvimento de Jogos, Geoinformática e uma série de outras disciplinas. Na Ciência da Computação formal, eles veem ainda mais uso, nomeadamente como uma forma de representar o estado.
Efetivamente, qualquer coisa que você possa representar como um conjunto de conexões pode ser representado como um gráfico e implementado por meio desse ADT em alguns formulário.
Aqui está um gráfico de exemplo que fiz:
Resposta
Um gráfico é apenas uma coleção de objetos conectados por linhas chamadas vértices.
O termo “gráfico” é uma abstração e generalização de muitos estruturas de dados usadas no desenvolvimento de software. Listas vinculadas, árvores binárias e AST “s são todos gráficos.
Basicamente, qualquer coleção de objetos que tem ponteiros que associam os objetos uns aos outros é um gráfico. Depois de ter um gráfico, você pode aplicar os princípios da teoria dos gráficos a ele, para resolver certos problemas .