Что нужно сделать чтобы произвольный граф g преобразовать в дерево
Алгоритм получения дерева из графа
1. Выбирается любая вершина. Счетчик i принимаем равным 1 (i=1).
2. Если i = k, то дерево построено.
3. Если i ¹ k, то выбирается любая незадействованная вершина и ребро, соединяющее данную вершину с любой из выбранных.
4. Счетчик увеличивается на единицу.(i= i+1).
5. Переход на пункт 2.
Преобразовать граф, представленный на рис. 3.12 в дерево:
 |
1. Найдем цикломатическое число 
, т.е. необходимо изъять 4 ребра.
2. Выбираем вершину 5. 
3. Присоединяем вершину 3.
4. 
5. Присоединяем вершину 4.
6. 
7. Присоединяем вершину 1.
8. 
9. Присоединяем вершину 2.
10. 
Преобразовать направленный граф в дерево
Дан массив arr [] размера N. От i до arr [i] есть грань. Задача состоит в том, чтобы преобразовать этот ориентированный граф в дерево, изменив некоторые ребра. Если для некоторого i arr [i] = i, то i представляет корень дерева. В случае нескольких ответов выведите любой из них.
Примеры:
Input: arr[] = <1, 2, 0>;
Output: <0, 2, 0>.
Подход: рассмотрим 2-й пример изображения выше, на котором показан пример функционального графика. Он состоит из двух циклов 1, 6, 3 и 4. Наша цель — сделать граф, состоящий ровно из одного цикла ровно одной вершины, зацикленного на себе.
Операция изменения эквивалентна удалению некоторого исходящего ребра и добавлению нового, переходя в другую вершину. Давайте сначала сделаем наш граф, содержащий только один цикл. Для этого можно выбрать любой из первоначально представленных циклов и сказать, что он будет единственным. Затем следует рассмотреть каждый второй цикл, удалить все его ребра в цикле и заменить его ребром, идущим к любой из вершин выбранного цикла. Таким образом, цикл будет нарушен, и его вершины (наряду с древовидными) будут связаны с единственным выбранным циклом. Нужно будет делать точно циклCount — 1 таких операций. Обратите внимание, что удаление любого ребра без цикла не имеет смысла, потому что оно не нарушает ни одного цикла.
Следующее — сделать длину цикла равной 1. Это может быть уже выполнено, если выбрать цикл минимальной длины, а эта длина равна 1. Таким образом, если исходный граф содержит какой-либо цикл длины 1, мы сделано с помощью cycCount — 1 операция. В противном случае цикл содержит более одной вершины. Это можно исправить ровно одной операцией — нужно просто разорвать любое из ребер в цикле, скажем, от u до arr [u], и добавить ребро от u к u. Граф останется состоящим из одного цикла, но состоящим из одной зацикленной вершины. В этом случае мы закончили с операциями cycleCount.
Чтобы выполнить все описанные выше операции, можно использовать структуру DSU или просто серию DFS. Обратите внимание, что в реализации удаления и создания ребер нет необходимости, нужно только проанализировать исходный граф.
Ниже приведена реализация вышеуказанного подхода:
// CPP программа для преобразования ориентированного графа в дерево
#include
using namespace std;
// Функция для поиска корня вершины
int find( int x, int a[], int vis[], int root[])
root[x] = find(a[x], a, vis, root);
// Функция для преобразования ориентированного графа в дерево
void Graph_to_tree( int a[], int n)
// Vis массив, чтобы проверить, посещен индекс или нет
// массив root [] для хранения родителя каждой вершины
// Найти родителя каждого родителя
// par хранит корень результирующего дерева
// Если не существует собственного цикла
// Сделать вершину в цикле корнем дерева
if (i == find(a[i], a, vis, root)) <
if (i == find(a[i], a, vis, root)) <
// Распечатать полученный массив
// Код драйвера для проверки вышеуказанных функций
int n = sizeof (a) / sizeof (a[0]);
// Java программа для конвертации
// направленный граф в дерево
// Функция для поиска корня вершины
static int find( int x, int a[],
root[x] = find(a[x], a, vis, root);
// Функция для преобразования ориентированного графа в дерево
static void Graph_to_tree( int a[], int n)
// Vis массив для проверки, является ли индекс
// посещенный или нет root [] массив
// сохранить родителя каждой вершины
int []vis = new int [n];
int []root = new int [n];
// Найти родителя каждого родителя
// par хранит корень результирующего дерева
// Если не существует собственного цикла
// Сделать вершину в цикле корнем дерева
if (i == find(a[i], a, vis, root))
if (i == find(a[i], a, vis, root))
// Распечатать полученный массив
static public void main ( String []arr)
// Этот код предоставлен 29AjayKumar
# Программа Python3 для конвертации
# направленный граф в дерево
# Функция поиска корня вершины
def find(x, a, vis, root):
root[x] = find(a[x], a, vis, root)
# Функция для преобразования ориентированного графа в дерево
def Graph_To_Tree(a, n):
# Vis массив, чтобы проверить, посещен индекс или нет
Массив # root [] предназначен для хранения родителя каждой вершины.
# Найти родителя каждого родителя
# par хранит корень полученного дерева
# Если не существует собственного цикла
# Сделать вершину в цикле как корень дерева
if i = = find(a[i], a, vis, root):
if i = = find(a[i], a, vis, root):
# Распечатать полученный массив
if __name__ = = «__main__» :
# Этот код предоставлен
# sanjeev2552
// C # программа для конвертации
// направленный граф в дерево
// Функция для поиска корня вершины
static int find( int x, int []a,
root[x] = find(a[x], a, vis, root);
// Функция для преобразования ориентированного графа в дерево
static void Graph_to_tree( int []a, int n)
// Vis массив для проверки, является ли индекс
// посещенный или нет root [] массив
// сохранить родителя каждой вершины
int []vis = new int [n];
int []root = new int [n];
// Найти родителя каждого родителя
// par хранит корень результирующего дерева
// Если не существует собственного цикла
// Сделать вершину в цикле корнем дерева
if (i == find(a[i], a, vis, root))
if (i == find(a[i], a, vis, root))
// Распечатать полученный массив
static public void Main ( String []arr)
// Этот код предоставлен Принчи Сингхом
Графы — определения, деревья, хранение и поиск в глубину
Основные определения
Примеры графа
Теоретическое задание
Назовите степень 1-ой и 6-ой вершины и какие ребра инциденты им.
1
Если какие-то две вершины соединены более, чем одним ребром, то говорят, что граф содержит кратные ребра. Если ребро соединяет вершину саму с собой, то такое ребро называют петлей.
Простой граф не содержит петель и кратных ребер. Если не сказано ничего про наличие петель и кратных ребер, мы будем всегда считать, что граф простой.
Теоретическое задание
Сколько может быть рёбер в простом графе в \(N\) вершинами?
2
Теоретическое задание
Найдите цикл размера 4 и петлю в этом непростом графе.
Также часто рассматривают ориентированные графы — это графы, у которых ребра имеют направление, а иначе граф – неориентированный.
Хранение графа в программе
Также чаще всего вам дают считать граф как просто список всех рёбер в нем (но не всегда, конечно). Как оптимально считать и сохранить граф? Есть 3 способа.
Для графа существуют несколько основных способов хранения:
Плотные графы, имеющие большое количество ребер следует хранить при помощи матрицы смежности, а разреженные графы, имеющие малое количество ребер, оптимальнее при помощи списка.
Практическое задание
Для окончательного закрепления темы советую решить первые 2 задачи.
Деревья
Пример дерева
Действительно, если предыдущий алгоритм начать из висячей вершины, то мы уткнемся в другую висячую вершину.
Действительно, если есть связный граф, в котором меньше, чем \(N-1\) ребро, то давайте уберем из его цикла ребро. Граф при этом остается связным, а число ребер уменьшается. Давайте повторять это, пока в какой-то момент циклов в графе не будет, а значит осталось дерево. Но мы уже доказали, что в дереве \(N-1\) ребро, это противоречие, ведь у нас сначала было меньше ребер, а мы еще и удалили сколько-то.
DFS (Алгоритм обхода графа в глубину)
Обход в глубину — простой, но многофункциональный алгоритм обхода графа по ребрам. Самое главное, что он может — это проверить, какие вершины достижимы из данной.
При обходе графа мы используем вспомогательный массив used, в котором храним 1, если вершина была посещена или 0 иначе. В начале мы считаем, что все вершины не использовались, затем мы выбираем одну вершину, помечаем ее посещенной и запускаемся рекурсивно из всех ее соседей, тогда мы посетим все вершины, которые достижимы из данной, если же остались вершины с used = 0 значит они недостижимы.
Красивая визуализация: https://visualgo.net/en/dfsbfs
Практическое задание
Задачи 3-5 в контесте.
Поиск компонент связности графа
Поиск в глубину dfs будет обходить ту компоненту связности, из вершины которой, он был вызван. Поэтому для поиска компонент связности можно каждый раз вызываться из любой непосещенной вершины и тогда в результате мы посетим все вершины, а следовательно и найдем все компоненты связности.
Практическое задание
На данную тему задачи 6 и 10 в контесте.
Остовное дерево
Остованым деревом в связном графе называется любое подмножество ребер, которое является деревом на всех вершинах. То есть любой способ выкинуть несколько ребер так, чтобы осталось дерево на N вершинах и N-1 ребро выделяет в графе остовное дерево.
Практическое задание
7 задача в контесте на выделение остовного дерева в графе.
Раскраска графа в два цвета
Корректной раскраской графа в два цвета назывется такая раскраска, что никакое ребро не соединяет две вершины одного цвета. Графы, которые можно так раскрасить, называют еще двудольными.
Практическое задание
8 задача в контесте на раскраску графа в два цвета
Поиск циклов в графе
Циклом в графе \(G\) называется ненулевой путь, ведущий из вершины \(v\) в саму себя. Граф называют ацикличным, если в нем нет циклов.
Заметим, что цикл будет тогда и только тогда, когда мы пытаемся войти в вершину с цветом 1.
Практическое задание
9 задача в контесте на поиск цикла в графе.
Теория графов — деревья
Деревья — это графики, которые не содержат ни одного цикла. Они представляют иерархическую структуру в графической форме. Деревья относятся к простейшему классу графов. Несмотря на их простоту, они имеют богатую структуру.
Деревья предоставляют целый ряд полезных приложений, от простого семейного дерева до сложных в структурах данных компьютерной науки.
дерево
Связный ациклический граф называется деревом. Другими словами, связный граф без циклов называется деревом.
Дерево с ‘n’ вершинами имеет ‘n-1’ ребер. Если у него есть еще одно ребро, превышающее ‘n-1’, то это дополнительное ребро, очевидно, должно соединиться с двумя вершинами, что приводит к образованию цикла. Затем он становится циклическим графом, что является нарушением для графа дерева.
Пример 1
График, показанный здесь, является деревом, потому что у него нет циклов, и он связан. Он имеет четыре вершины и три ребра, т. Е. Для ‘n’ вершин ‘n-1’ ребер, как указано в определении.
Примечание. Каждое дерево имеет как минимум две вершины первой степени.
Пример 2
В приведенном выше примере вершины «a» и «d» имеют степень один. А две другие вершины ‘b’ и ‘c’ имеют второй уровень. Это возможно, потому что для того, чтобы не формировать цикл, в диаграмме должно быть как минимум два отдельных ребра. Это не что иное, как два ребра со степенью один.
Несвязный ациклический граф называется лесом. Другими словами, непересекающаяся коллекция деревьев называется лесом.
пример
Следующий график выглядит как два подграфа; но это один несвязный граф. На этом графике нет циклов. Отсюда ясно, что это лес.
Охватывающие деревья
Пусть G — связный граф, тогда подграф H в G называется остовным деревом в G, если —
Остовное дерево T неориентированного графа G является подграфом, который включает в себя все вершины G.
Реализация графов и деревьев на Python
Продолжаем публикацию наиболее интересных глав из книги Magnus Lie Hetland «Python Algorithms». Предыдущая статья расположена по адресу habrahabr.ru/blogs/algorithm/111858. Сегодня же речь пойдет об эффективной работе с графами и деревьями и особенностях их реализации в Python. Базовая терминология теории графов уже обсуждалась (например здесь: habrahabr.ru/blogs/algorithm/65367), так что я не включил часть главы о терминах в эту статью.
Реализация графов и деревьев
Многие задачи, например, задача обхода точек по кратчайшему маршруту, могут быть решены с помощью одного из мощнейших инструментов — с помощью графов. Часто, если вы можете определить, что решаете задачу на графы, вы по-крайней мере на полпути к решению. А если ваши данные можно каким-либо образом представить как деревья, у вас есть все шансы построить действительно эффективное решение.
Графами можно представить любую структуру или систему, от транспортной сети до сети передачи данных и от взаимодействия белков в ядре клетки до связей между людьми в Интернете.
Ваши графы могут стать еще полезнее, если добавить в них дополнительные данные вроде весов или расстояний, что даст возможность описывать такие разнообразные проблемы как игру в шахматы или определение подходящей работы для человека в соответствии с его способностями.
Деревья — это просто особый вид графов, так что большинство алгоритмов и представлений графов сработают и для них.
Однако, из-за их особых свойств (связность и отсутствие циклов), можно применить специальные (и весьма простые) версии алгоритмов и представлений.
На практике в некоторых случаях встречаются структуры (такие как XML-документы или иерархия каталогов), которые могут быть представлены в виде деревьев (с учетом атрибутов IDREF и символьных ссылок XML-документы и иерархия каталогов становятся собственно графами). На самом деле эти «некоторые» случаи довольно-таки общие.
Описание задачи в терминах графов является довольно абстрактным, так что если вам нужно реализовать решение, вы должны представить графы в виде каких-либо структур данных. (Это придется делать даже при проектировании алгоритма и только, потому что нужно знать, сколько времени будут выполняться различные операции на представлении графа). В некоторых случаях граф будет уже составлен в коде или данных, так что отдельной структуры не потребуется. Например, если вы пишете веб-краулер, собирающий информацию о сайтах по ссылкам, графом будет сама сеть. Если у вас есть класс Person с атрибутом friends, являющимся списком других объектов типа Person, то ваша объектная модель уже будет графом, на котором можно использовать различные алгоритмы. Однако существуют и специальные способы представления графов.
В общих словах, мы ищем способ реализации функции смежности, N(v), так, чтобы N[v] было каким-либо набором (или в отдельных случаях просто итератором) смежных с v вершин. Как и во многих других книгах мы сосредоточимся на двух наиболее известных представлениях: списках смежности и матрицах смежности, потому что они наиболее полезны и обобщены. Альтернативные представления описаны в последнем разделе ниже.
«Черный ящик»: словари и множества
Списки смежности и тому подобное
Один из наиболее очевидных способов представления графов — это списки смежности. Смысл их в том, что для каждой вершины создается список (или множество, или другой контейнер или итератор) смежных с ней вершин. Разберем простейший способ реализации такого списка, предположив, что имеется n вершин, пронумерованных 0… n-1.
Таким образом, каждый список смежности является списком таких номеров, а сами эти списки собраны в главный список размера n, индексированный номерами вершин. Обычно сортировка таких списков случайная, так что речь в действительности идет об использовании списков для реализации множеств смежности. Термин список просто исторически устоялся. Python, к счастью, имеет отдельный тип для множеств, который во многих случаев удобно использовать.
Примерный граф, для которого будут показаны разные представления, изображен на рис. 1. Для начала положим, что все вершины пронумерованы (a=0, b =1, …). С учетом этого граф можно представить очевидным способом, как показано в следующем листинге. Чтобы было удобнее, я присвоил номера вершин переменным, названным в соответствии с метками вершин на рисунке. Но можно работать и прямо с числами. Какой вершине какой список принадлежит указано в комментариях. Если хотите, потратьте несколько минут, чтобы убедиться, что представление соответствует рисунку.
Рис. 1. Примерный граф для демонстрации разных видов представления
Имя N из листинга связано с функцией N, описанной выше. В теории графов N(v) представляет множество смежных с v вершин. Так же и в нашем коде N[v] является множеством смежных с v вершин. Предполагая, что N определена как в примере выше, в интерактивном режиме Python можно поизучать это представление:
Другим возможным представлением, которое в некоторых случаях даст меньше накладных расходов, являются собственно списки смежности. Пример такого списка приведен в листинге ниже. Доступны все те же операции, но проверка смежности вершины выполняется за Θ(n). Это дает серьезное снижение скорости, но если вам действительно требуется это представление, то это его единственная проблема. (Если все, что делает ваш алгоритм — это обход соседних вершин, то использование объектов типа множество не просто бессмысленно: накладные расходы могут ухудшить постоянные множители в асимптотике вашей реализации).
Можно поспорить, что это представление на самом деле — набор массивов смежности, а не классические списки смежности, т.к. тип список в Python в действительности является динамическим массивом. Если хотите, вы можете реализовать тип связанного списка и использовать его вместо типа list из Python. Это может сделать дешевле в плане производительности произвольные вставки в список, но вам, вероятно, и не понадобится такая операция, потому что с тем же успехом можно добавлять новые вершины к концу списка. Преимущество использования встроенного list в том, что он представляет собой очень быструю и хорошо отлаженную структуру (в отличие от любых структур списков, которые можно реализовать на чистом Python).
При работе с графами постоянно всплывает идея о том, что лучшее представление зависит от того, что именно нужно сделать с графом. Например, используя списки (или массивы) смежности можно сохранить накладные расходы небольшими и обеспечить эффективный обход N(v) для любой вершины v. Однако, проверка, являются ли u и v смежными, потребует времени Θ(N(v)), что может стать проблемой при высокой плотности графа (т.е. при большом числе ребер). В этих случаях на помощь придут множества смежности.
Совет:
Известно, что удаление объектов из середины list в Python довольно затратно. Удаление с конца при этом происходит за константное время. Если вы не заботитесь о порядке вершин, то можете удалять случайную вершину за константное время перезаписывая ее той, что находится в конце списка смежности, и вызывая затем метод pop.
Небольшой вариацией на тему этого представления можно назвать сортированные списки смежных вершин. Если списки нечасто меняются, их можно держать отсортированными и использовать бисекцию для проверки смежности вершины, что приведет к немного меньшим накладным расходам (в плане использования памяти и времени итерации), но увеличит сложность проверки до Θ(log2 k), где k — количество смежных с данной вершин. (Это все равно очень маленькое значение. На практике, впрочем, использование встроенного типа set доставляет гораздо меньше хлопот).
Еще одна небольшая доработка заключается в использовании словарей вместо множеств или списков. Смежные вершины могут быть ключам словаря, а в качестве значения можно использовать любые дополнительные данные, например, вес ребра. Как это выглядит можно увидеть в листинге ниже (веса выбраны случайно).
Словарь смежности можно использовать точно так же как и другие представления, с учетом дополнительной информации о весах:
Если хотите, можете использовать словари смежности даже если у вас нет полезных данных вроде весов ребер (используя None или другое значение вместо данных). Это даст вам все преимущества множеств смежности, но при этом будет работать с (очень-очень) старыми версиями Python, не имеющими поддержки типа set(множества были введены в Python 2.3 в виде модуля sets. Встроенный тип set доступен начиная с Python 2.4).
До этого момента сущность, хранящая структуры смежности — списки, множества или словари — была списком, индексированным номерами вершин. Более гибкий вариант (позволяющий использовать произвольные, хэшируемые, имена вершин) строится на базе словаря в качестве основной структуры (такие словари со списками смежности Гвидо ван Россум использовал в своей статье «Python Patterns — Implementing Graphs», выложенной по адресу www.python.org/doc/essays/graphs.html). Листинг ниже показывает пример словаря, содержащего множества смежности. Заметьте, что вершины в нем обозначены символами.
Если из листинга выше выбросить конструктор set, то останутся строки смежности, которые будут работать как списки смежности (неизменяемые) из символов (с чуть меньшими накладными расходами). Казалось бы, далеко не лучшее представление, но, как и было сказано выше, все зависит от вашей программы. Откуда вы получаете данные для графа? (Может быть, они уже в виде текста?) Как вы собираетесь их использовать?
Матрицы смежности
Другая распространенная форма представления графов — это матрицы смежности. Основное отличие их в следующем: вместо перечисления всех смежных с каждой из вершин, мы записываем один ряд значений (массив), каждое из которых соответствует возможной смежной вершине (есть хотя бы одна такая для каждой вершины графа), и сохраняем значение (в виде True или False), показывающее, действительно ли вершина является смежной. И вновь простейшую реализацию можно получить используя вложенные списки, как видно из листинга ниже. Обратите внимание, что это также требует, чтобы вершины были пронумерованы от 0 до V-1. В качестве значений истинности используются 1 и 0 (вместо True и False), чтобы сделать матрицу читабельной.
Способ использования матриц смежности слегка отличается от списков и множеств смежности. Вместо проверки входит ли b в N[a], вы будете проверять, истинно ли значение ячейки матрицы N[a][b]. Кроме того, больше нельзя использовать len(N[a]), чтобы получить количество смежных вершин, потому что все ряды одной и той же длины. Вместо этого можно использовать функцию sum:
Матрицы смежности имеют ряд полезных свойств, о которых стоит знать. Во-первых, так как мы не рассматриваем графы с петлями (т.е. не работаем с псевдографами), все значения на диагонали ложны. Также, ненаправленные графы обычно описываются парами ребер в обоих направлениях. Это значит, что матрица смежности для ненаправленного графа будет симметричной.
Расширение матрицы смежности для использования весов тривиально: вместо сохранения логических значений, сохраняйте значения весов. В случае с ребром (u, v) N[u][v] будет весом ребра w(u,v) вместо True. Часто в практических целях несуществующим ребрам присваиваются бесконечные веса. (Это гарантирует, что они не будут включены, например, в кратчайшие пути, т. к. мы ищем путь по существующим ребрам). Не всегда очевидно, как представить бесконечность, но совершенно точно есть несколько разных вариантов.
Один из них состоит в том, чтобы использовать некорректное для веса значение, такое как None или -1, если известно, что все веса неотрицательны. Возможно, в ряде случаев полезно использовать действительно большие числа. Для целых весов можно применить sys.maxint, хотя это значение и не обязательно самое большое (длинные целые могут быть больше). Есть и значение, введенное для отражения бесконечности: inf. Оно недоступно в Python напрямую по имени и выражается как float(‘inf’)(гарантируется, что это работает для Python 2.6 и старше. В ранних версиях подобные специальные значения были платформо-зависимы, хотя float(‘inf’) или float(‘Inf’) должны сработать на большинстве платформ).
Листинг ниже показывает, как выглядит матрица весов, реализованная вложенными списками. Использованы те же веса, что и в листинге выше.
Бесконечное значение обозначено как подчеркивание (_), потому что это коротко и визуально различимо. Естественно, можно использовать любое имя, которое вы предпочтете. Обратите внимание, что значения на диагонали по-прежнему равны нулю, потому что даже без учета петель, веса часто интерпретируются как расстояния, а расстояние от вершины до самой себя равно нулю.
Конечно, матрицы весов дают возможность очень просто получить веса ребер, но, к примеру, проверка смежности и определение степени вершины, или обход всех смежных вершин делаются иначе. Здесь нужно использовать бесконечное значение, примерно так (для большей наглядности определим inf = float(‘inf’)):
Обратите внимание, что из полученной степени вычитается 1, потому что мы не считаем значения на диагонали. Сложность вычисления степени тут Θ(n), в то время как в другом представлении и смежность, и степень вершины можно определить за константное время. Так что вы всегда должны понимать, как именно вы собираетесь использовать ваш граф и выбирать для него соответствующее представление.
Массивы специального назначения из NumPy
Реализация деревьев
Любое представление графов, естественно, можно использовать для представления деревьев, потому что деревья — это особый вид графов. Однако, деревья играют свою большую роль в алгоритмах, и для них разработано много соответствующих структур и методов. Большинство алгоритмов на деревьях (например, поиск по деревьям) можно рассматривать в терминах теории графов, но специальные структуры данных делают их проще в реализации.
Проще всего описать представление дерева с корнем, в котором ребра спускаются вниз от корня. Такие деревья часто отображают иерархическое ветвление данных, где корень отображает все объекты (которые, возможно, хранятся в листьях), а каждый внутренний узел показывает объекты, содержащиеся в дереве, корень которого — этот узел. Это описание можно использовать, представив каждое поддерево списком, содержащим все его поддеревья-потомки. Рассмотрим простое дерево, показанное на рисунке. 2.
Мы можем представить это дерево как список списков:
Каждый список в сущности является списком потомков каждого из внутренних узлов. Во втором примере мы обращаемся к третьему потомку корня, затем ко второму его потомку и в конце концов — к первому потомку предыдущего узла (этот путь отмечен на рисунке).
Рис. 2. Пример дерева с отмеченным путем от корня к листу
В ряде случаев возможно заранее определить максимальное число потомков каждого узла. (Например, каждый узел бинарного дерева может иметь до двух потомков). Поэтому можно использовать другие представления, скажем, объекты с отдельным атрибутом для каждого из потомков как в листинге ниже.
Для обозначения отсутствующих потомков можно использовать None (в случае если у узла только один потомок). Само собой, можно комбинировать разные методы (например, использовать списки или множества потомков для каждого узла).
Распространенный способ реализации деревьев, особенно на языках, не имеющих встроенной поддержки списков, это так называемое представление «первый потомок, следующий брат». В нем каждый узел имеет два «указателя» или атрибута, указывающих на другие узлы, как в бинарном дереве. Однако, первый из этих атрибутов ссылается на первого потомка узла, а второй — на его следующего брата (т.е. узел, имеющий того же родителя, но находящийся правее, — прим. перев). Иными словами, каждый узел дерева имеет указатель на связанный список его потомков, а каждый из этих потомков ссылается на свой собственный аналогичный список. Таким образом, небольшая модификация бинарного дерева даст нам многопутевое дерево, показанное в листинге ниже.
Отдельный атрибут val здесь введен просто для того, чтобы получить понятный вывод при указании значения (например, «c») вместо ссылки на узел. Естественно, все это можно изменять. Вот пример того, как можно обращаться с этой структурой:
А вот как выглядит это дерево:
Атрибуты kids и next показаны пунктирными линиями, а сами ребра дерева — сплошными. Я немного схитрил и не стал показывать отдельные узлы для строк «a», «b» и т.д. Вместо этого я трактую их как метки на соответствующих родительских узлах. В более сложном дереве вместо использования одного атрибута и для хранения значения узла и для ссылки на список потомков, для обеих целей могут понадобиться отдельный атрибуты. Обычно для обхода дерева используется более сложный код (включая циклы и рекурсию), чем приведенный здесь с жестко заданным путем.
Шаблон проектирования «Набор»
Множество разных представлений
Несмотря на то, что существует масса представлений графов, большинство изучают и используют только два вида (с изменениями), уже описанных в этой главе. Джереми Спинред в своей книге «Effective Graph Representation» пишет, что его, как исследователя компьютерного представления графов, «особенно раздражают» большинство вводных статей. Приводимые в них описания хорошо известных представлений (списков и матриц смежности) обычно адекватны, но более общие объяснения нередко ошибочны. Как пример он показывает следующий ложный вывод о представлении графов, который основывается на неверных положениях из разных статей:
«Существует два метода представления графов в компьютере: списки и матрицы смежности. Работа с матрицами смежности быстрее, но они требуют больше памяти, чем списки смежности, так что вам нужно выбрать один из двух способов, исходя из того, какой ресурс для вас важнее» (стр. 9).
Спинред отмечает, что эти заключения сомнительны по нескольким причинам. Во-первых, есть много интересных способов представления графов, не только два описанных. Например, существуют списки ребер (или множества ребер), являющиеся списком всех ребер в виде пар вершин (или специальных объектов-ребер), существуют матрицы инцидентности, показывающие, какие ребра каким вершинам инцидентны (полезно для мультиграфов). Также существуют специальные методы для особых типов графов, вроде деревьев (описанных выше) и интервальных графов (здесь не рассматриваются). Полистайте книгу Спинреда, чтобы узнать о представлениях графов, которые вам могут когда-нибудь понадобиться.
Во-вторых, идея компромисса между памятью и временем работы может ввести в заблуждение: есть проблемы, решение которых со списками смежности будет быстрее, чем с матрицами смежности, а для произвольного графа на практике списки смежности требуют больше памяти, чем матрицы.
Так что, вместо того, чтобы полагаться на простые обобщенные выводы, подобные описаным, нужно вникнуть в специфику своей задачи. Основным критерием, вероятно, будет асимптотическая сложность того, что вы делаете. Например, поиск ребра (u, v) в матрице смежности выполняется за Θ(1), а обход смежных с v вершин — за Θ(n), в то время как на списке смежности обе операции будут выполнены за Θ(d(v)), т.е. будут зависеть от количества смежных с данной вершин.
Если асимптотическая сложность вашего алгоритма не зависит от типа представления, вы можете провести какие-либо эмпирические тесты, описанные ранее в этой главе. Или, как часто и бывает, можно выбрать то представление, которое лучше сочетается с вашим кодом и проще в поддержке.
Важный способ использования графов, который еще не был затронут, не касается их представления. Дело в том, что во многих задачах данные уже имеют структуру графа, или даже дерева, и мы можем использовать для них соответствующие алгоритмы для графов и деревьев без создания специальных представлений. В ряде случаев это происходит, если представление графа составлено вне нашей программы. Например, при разборе XML-документов или обходе каталогов файловой системы древовидная структура уже создана и для нее существуют определенные API. Иными словами, мы неявно задаем граф. К примеру, чтобы найти наиболее эффективное решение для заданной конфигурации кубика Рубика, можно определить состояние кубика и методы его изменения. Но даже если явно не описывать и не сохранять каждую конфигурацию, возможные состояния сформируют неявный граф (или множество вершин) с ребрами — операторами изменения состояния. Дальше можно использовать такие алгоритмы, как A* или двунаправленный алгоритм Дейкстры, чтобы найти кратчайший путь до состояния решения. В таких случаях функция получения соседних вершин N(v) будет работать «на лету», вероятно, возвращая смежные вершины как коллекцию или другую форму объекта-итератора.
И последний тип графов, которого я коснусь в этой главе, называется графом подзадач. Это глубокая концепция, к которой я еще неоднократно буду обращаться, описывая различные техники построения алгоритмов. Вкратце, большинство задач может быть разложено на подзадачи: меньшие задачи, часто имеющие похожую структуру. Они формируют вершины графа подзадач, а их зависимости (т.е. какая подзадача от какой зависит) выражаются ребрами. И хотя алгоритмы на графы редко применяются на графах подзадач (они используются больше как инструмент анализа), такие графы отлично позволяют понять технику «разделяй и властвуй» и динамическое программирование.