24 января 2010 в 09:45
Графы. Часть 1.
Графы - одна из самых сложных структур данных, которые мы рассмотрим.
Как обычно, начнём с примитивных вещей. Граф - структура данных состоящая из узлов. Как вы, наверное, помните, связные списки тоже состоят из узлов. Отличие графов от связных списков (и от других структур данных, состоящих из узлов) заключается в том, что узлы в графе могут соединяться с любым другим узлом графа. Вообще говоря, связные списки - это частный случай графов.
Наиболее наглядное представление графов даст рисунок:
Граф состоит из двух частей: узлы, которые содержат данные и дуги, которые соединяют узлы друг с другом. Каждый узел может быть соединён с любым другим.
На рисунке представлен граф состоящий из пяти узлов.
Двунаправленные графы
Двунаправленные графы (bi-directional graphs) - самый простой тип графов. Именно этот тип представлен на рисунке. В данном типе графов, если два узла соединены друг с другом, то между этими узлами можно свободно "перемещаться".
Однонаправленные графы
В однонаправленных графах, если между двумя узлами есть дуга, то она "указывает" только в одну сторону. На рисунке у дуги только одна стрелочка. Для перехода в обе стороны потребуется две дуги.
В будущем мы будем пользоваться именно однонаправленными графами, так как они наиболее гибкие.
В программах графы могут быть представлены разными способами: списком смежности, таблицей инциденций, массивом дуг и др. Некоторые из этих способов мы рассмотрим позже.
Сейчас же мы рассмотрим довольно сложную реализацию графов. Обычно, в учебниках по алгоритмам/структурам данных приводится довольно простая реализация графов, например, списком смежности. Подобные реализации обычно используют только двухмерный массив. Но нам этот вариант не подойдёт. Мы создадим хоть и сложную структуру данных, но очень гибкую. Создавать мы будем именно однонаправленные графы. Для данной реализация нам понадобятся двусвязные списки. Для этого воспользуемся библиотекой algorithms_v0.1. Для понимания кода, вы должны уметь довольно уверенно пользоваться связными списками, которые мы уже рассмотрели. Конечно же в нашей реализации будут использоваться шаблонные классы. В графе присутствует две основные сущности: дуги и узлы. Соответственно, нам понадобятся два типа: ArcType и NodeType. В узлах может хранится, например, какие-нибудь объекты класса. В дугах же можно расстояния между узлами (вес дуги). Весь код размещается в двух файлах в проекте algorithms решения libraries, т.е. в том же проекте, что и реализация двусвязного списка. Необходимые файлы: Graph.h и Graph.cpp GraphArc Класс дуг очень прост. GraphNode Обратите внимание, что данный класс не содержит указатели на другие узлы, вместо этого используется указатель на связный список в котором хрянятся все дуги этого графа. Последняя переменная marked очень важна. Она используется при поиске по графу. NodeGraph содержит три функции: добавление дуги, удаление дуги и поиск дуги.
Добавление дуги к узлу
И последний, самый сложный класс - Graph. Объект класса хранит все узлы графа. Для хранения узлов в графе, мы конечно же будем использовать связные списки.
Пока что, завершим краткий обзор графов. Конечно же мы ещё вернёмся к рассмотрению этой поистине обширной теме. На данный момент, нам хватит информации для рассмотрения других структур данных - частных случаев графов, прежде всего деревьев.
2 декабря 2016 в 19:28
Hey esto es un gran poste. Puedo utilizar una porcin en ella en mi sitio? Por supuesto ligara a su sitio as que la gente podra leer el artculo completo si ella quiso a. Agradece cualquier manera.
2 декабря 2016 в 19:28
Hey esto es un gran poste. Puedo utilizar una porcin en ella en mi sitio? Por supuesto ligara a su sitio as que la gente podra leer el artculo completo si ella quiso a. Agradece cualquier manera.
27 июня 2017 в 06:07
Both cheap and gorgeous fine imitation watches;<a href="http://www.replicaluxury.co.uk">rolex replica</a> filling your success sty le!
<a href="http://www.replica-watch.co.uk/">copy watches</a> Replica watch online.
27 июня 2017 в 06:07
Both cheap and gorgeous fine imitation watchesBreitling replica filling your success style!
replica horloges nederland ervaringen Replica watch online.
авторизуйтесь
или войдите через