Что такое графики в информатике и для чего они используются? С точки зрения мирян желательно.
Я прочитал определение в Википедии :
В информатике граф - это абстрактный тип данных, предназначенный для реализации понятий граф и гиперграф из математики.
Структура данных графа состоит из конечного (и, возможно, изменяемого) набора упорядоченных пар, называемых ребрами или дугами, определенных объектов, называемых узлами или вершинами. Как и в математике, говорят, что ребро (x, y) указывает или переходит от x к y. Узлы могут быть частью структуры графа или могут быть внешними объектами, представленными целочисленными индексами или ссылками.
но я ищу менее формальное, более простое для понимания определение.
computer-science
graph
ConditionRacer
источник
источник
Ответы:
Примером идеального дилетанта может быть Facebook . Сеть из вас, ваших друзей, их друзей и т. Д. Вместе называется социальным графом .
В этом «графе» люди рассматриваются как узлы графа, а ребра - это дружеские связи .
В Facebook друг - это двунаправленное отношение (A - это друг B => B - это друг A), поэтому график - это неориентированный график . Сеть типа Google+ или Twitter будет считаться ориентированным графом, так как направление отношений имеет здесь значение.
Все эти графы называются циклическими графами, поскольку отношения между узлами могут образовывать циклы. Family Tree , с другой стороны, представляет собой особый вид графа , который, помимо всего прочего, является ациклические , так как не может быть циклов в родословной relatioship. (Технически он называется Направленный ациклический граф (DAG), поскольку он направленный и ациклический)
Это должно охватывать весь основной жаргон с графиками, так что теперь вы сможете следить за остальным материалом в поле.
источник
A -> B -> C -> A
(например, круг стрелок), инцест просто даетA -> B -> C
иA -> D -> C
(т. Е. Ромб). Цикл в генеалогическом древе требует путешествий во времени.Графики являются одним из наиболее важных математических понятий, используемых в информатике.
Вы видели графики много раз. Представьте, что вы летите самолетом из одного города в другой. Вы неизбежно найдете хороший глянцевый журнал от авиакомпании в кармане перед вами. В конце этого журнала почти всегда можно найти карту, на которой города, обслуживаемые этой авиакомпанией, изображены в виде кругов, а рейсы, соединяющие эти города, представлены в виде изогнутых линий. Это график! Города, представленные в виде кругов, являются узлами этого графика, а полеты, представленные в виде изогнутых линий, являются краями. Графики - это просто вещи с узлами и ребрами, которые соединяют узлы.
Вы можете приукрасить эти простые графики различными способами. Вы не хотите видеть только кучу кругов и линий, когда смотрите на эту карту. У этих городов есть названия. Маркировка этих городов приводит к помеченному графику. (Вы также можете пометить края, например, рейс 1234.) Информатика часто связывает данные с узлами, иногда с краями, но это всего лишь расширение метки. Это все еще помеченный график. Если вы можете лететь прямо из города A в город B, но не из города B в город A. Это очевидный способ изобразить это - поставить стрелку на линии, соединяющей города, чтобы изобразить эти односторонние отношения. Теперь у вас есть ориентированный граф.
Связанные списки, деревья, диаграммы перехода состояний и множество других структур данных информатики - все это примеры графиков. Это очень мощная концепция.
источник
Лучшим вопросом будет «Для чего не используются графики?». Информатика - это во многом изучение графов.
Граф, с точки зрения непрофессионалов, представляет собой набор произвольных абстрактных объектов, называемых «узлами» или «вершинами», которые представляют точки соединения. Затем они соединяются через «пути» или «ребра». Абстрактный тип данных «График» является реализацией математического «Графа». Таким образом, в основном у вас есть узлы и ребра в качестве полей и различные операции, которые вы можете выполнять над ними. Например, вы можете добавить новый узел в коллекцию графа (это может быть список, массив или какая-то другая структура в зависимости от языка). Затем вы можете связать этот узел с существующими узлами. Операции также будут включать в себя обход графа, проверку того, имеют ли два узла общее ребро (связаны), извлечение значений из узлов или ребер и удаление узлов или ребер из графа.
Что касается использования, графики используются повсеместно. Их особенно интенсивно используют в сетях, но они встречаются в искусственном интеллекте, интеллектуальном анализе данных, разработке игр, геоинформатике и множестве других дисциплин. В формальной информатике они видят еще большее применение, а именно как способ представления государства.
Фактически все, что вы можете представить в виде набора соединений, может быть представлено в виде графика и реализовано с помощью этого ADT в некоторой форме.
Вот пример графика, который я сделал:
источник
Граф - это просто набор объектов, соединенных линиями, называемыми вершинами.
Термин «граф» - это абстракция и обобщение многих структур данных, используемых при разработке программного обеспечения. Связанные списки, двоичные деревья и AST являются графиками.
По сути, любая коллекция объектов, у которой есть указатели, которые связывают объекты друг с другом, является графом. Если у вас есть граф, вы можете применить к нему принципы теории графов для решения определенных задач .
источник