Вывести компоненты связности питон

В прошлом занятии мы обсудили способы хранения графов. В этом занятии мы начнём изучать алгоритмы на графах. Договоримся, что мы рассматриваем исключительно неориентированные графы без петель и кратных рёбер.

Поставим следующую задачу. Дан граф, в котором выделена вершина s. Требуется найти все вершины, лежащие в одной компоненте связности с ней. Иными словами, нужно понять, до каких вершин можно добраться из s. Будем считать, что граф задан списками смежности:

Наш алгоритм будет основан на рекурсии. Опишем его идею. Встанем в вершину s и посмотрим на всех её соседей. Посетим каждого такого соседа. Когда будем посещать соседа, посмотрим на его соседей, и так далее. Когда мы посещаем вершину, мы вызываем функцию dfs(v), передавая в качестве параметра v номер этой вершины. Эскиз кода таков:

Давайте подумаем, почему этот код не работает. Сначала вызовется функция dfs(0). Внутри функции переменная w примет значение 2, и вызовется функция dfs(2). При просмотре соседей вершины 2 мы увидим соседа 0 и опять вызовем dfs(0). Мы вошли в вечную рекурсию. Функции dfs(0) и dfs(2) будут продолжать вызывать друг друга, создавая новые фреймы в стеке вызовов функций, пока не будет превышен лимит интерпретатора на глубину рекурсии. *очень много страшных слов*

Как же исправить это недоразумение? Надо как-то помечать вершины, в которых мы были, и не ходить ещё раз в уже посещённые вершины.

Давайте заведём массив visited размера n, по ячейке на каждую вершину. В ячейке visited[v] будет лежать значение False, если вершина v пока не была посещена алгоритмом, и True, если вершина v была посещена. При первом заходе в вершину v мы меняем значение visited[v] с False на True.

Теперь наш код работает. Посмотрите в визуализаторе, в каком порядке dfs() посещает вершины. Обратите также внимание на стек вызовов функций. Заметьте, что значения локальных переменных v, которые лежат в стеке вызовов, в точности соответствуют вершинам пути, по которому мы пришли в текущую вершину из стартовой вершины s. Это замечание нам потом пригодится.

Вспомним же, наконец, какую задачу мы решали. Мы хотели посчитать количество вершин, которые достижимы из v. Но это ровно те вершины, которые были посещены функцией dfs(). А у них в массиве visited стоит метка True. Ответ получаем моментально:

2. Подсчет количества компонент связности

Пусть, однако, это не так, и для некоторых вершин visited[v] == False. Выберем среди таких вершин произвольную и запустим dfs() уже от неё. Запущенный обход в глубину посетит все вершины второй компоненты связности.

Такие действия надо производить до тех пор, пока в массиве visited остаются значения False. На практике делают один проход по всем вершинам, и каждый раз от непосещённых вершин запускается новый обход в глубину.

Лёгко добавить в этот код переменную, которая будет считать количество компонент связности. Проделайте это.

Оценим суммарное время работы программы, которая подсчитывает количество компонент связности. Оценку произведём в обозначениях «О-большое». При этом буквой V мы обозначаем количество вершин в графе, а буквой E — количество рёбер.

Функция dfs() вызывается один раз от каждой вершины. Таким образом, только на её вызов и на константные по времени действия в ней (вроде изменения ячейки visited[v]) тратится O(V) действий. Далее, в цикле по переменной w каждый сосед каждой вершины будет просмотрен ровно один раз. Рассмотрим, например, ребро (0, 2). Его наличие означает, что внутри вызова dfs(0) в цикле по соседям вершины 0 переменная w в какой-то момент примет значение 2. Аналогично, при вызове dfs(2) переменная w ровно один раз примет значение 0. Таким образом, эти операции вносят суммарный вклад 2E = O(E) в общее время работы программы. Других действий в программе нет, так что суммарная сложность алгоритма получается O(V + E).

3. Проверка наличия пути между двумя вершинами

Теперь можно завести массив component, в которой для каждой вершины мы запишем номер её компоненты. Как это можно сделать? Заметим, что пока мы посещаем вершины одной и той же компоненты связности, значение переменной num_components не меняется. А при переходе к рассмотрению новой компоненты связности значение этой переменной увеличивается. Значит, значение переменной num_components в тот момент, когда мы вызывали функцию dfs(v), логично считать номером компоненты связности для вершины v. Давайте запоминать это значение в массиве component. Приведём окончательный код.

Теперь представим, что нам дают номера двух вершин v и w, и спрашивают, есть ли путь между ними. Мы проверяем, равны ли значения component[v] и component[w]. Если они равны, то вершины v и w лежат в одной компоненте связности, и между ними существует путь. В противном случае такого пути нет.

В задаче, которую мы научились решать, есть две фазы: фаза подготовки (фаза предподсчёта) и фаза ответов на запросы (фаза ответов на запросы в коде не представлена). Сложность задач, которые состоят из этих двух фаз, принято оценивать отдельно по каждой фазе. В нашем случае время предподсчёта составляет O(V + E), а время ответа на запрос составляет O(1) (оно никак не зависит от размера графа).

4. Обход в глубину на неявных графах

До сих пор мы предполагали, что граф хранится в списке смежности, а вершины графа занумерованы числами 0, 1, 2 и т. д. На практике графы могут храниться по-другому, и у вершин могут быть не номера, а названия. Наконец, граф может не храниться вовсе. Рассмотрим лабиринт, нарисованный на клетчатой бумаге. Например, чёрные клетки могут означать наличие пространства в лабиринте, а белые — его отсутствие (стены).

Пусть мы хотим рассматривать этот лабиринт как граф. Вершинами будут чёрные клетки (пространство), а две клетки-вершины соединены ребром тогда, когда они соединены по стороне. Тогда каждая вершина естественно обозначается не одним номером, а парой чисел — координатами клетки.

На таком графе можно запустить обход в глубину, который может искать путь между двумя клетками. В частности, с помощью обхода в глубину можно найти выход из лабиринта. При этом не нужно явно строить граф, записывая все рёбра между вершинами в списки смежности. Для обхода в глубину достаточно уметь по вершине получать список её соседей.

Пусть мы стоим в клетке с координатами (x, y). Соседями данной клетки являются клетки (x — 1, y), (x, y — 1), (x, y + 1) и (x + 1, y), если только получившиеся координаты неотрицательны.

Покажем эскиз кода, который позволит элегантно перебрать всех соседей клетки (x, y) в языке Питон. При этом используется вариация множественного присваивания для счетчика цикла for.

5. Вывод пути до вершины, поиск циклов

Запустим dfs() от вершины s. Заметим, что в тот момент, когда мы дойдём до вершины t, в стеке вызовов функций будут последовательно лежать вызовы функции dfs() от всех вершин интересующего нас пути. Наш путь уже лежит где-то в памяти программы, но он лежит там, откуда вытащить его непросто. А нам надо легко его получать. Значит, придётся нам хранить его самостоятельно.

Для этого давайте заведём глобальный список path, в котором всегда будет поддерживаться путь от вершины s до той вершины, которую мы сейчас посещаем. При заходе в вершину мы кладём её номер в конец списка path. При выходе из вершины не забывайте свои номера. О номерах, оставленных другими вершинами, сообщайте машинисту.

Надеюсь, вы без труда допишете код, который будет выводить искомый путь в нужный момент.

6. Двудольные графы

Наконец, последнее, о чём хочется поговорить в этом занятии — это о двудольных графах. Граф называется двудольным, если все его вершины можно разбить на две группы, при этом все рёбра должны обязательно идти из одной группы в другую, и запрещены рёбра, соединяющие две вершины из одной группы. На примере внизу двумя группами являются группа b и группа g.

Можно смотреть на двудольные графы как на графы, вершины которого раскрашены в два цвета. При этом раскраска является правильной, т. е. каждое ребро соединяет вершины разных цветов. На рисунке приведены несколько двудольных графов.

Некоторые графы нельзя правильно раскрасить в два цвета. Например, граф-треугольник нельзя раскрасить в два цвета: хотя бы одно ребро всегда будет соединять вершины одного цвета. На самом деле, можно доказать такую теорему.

Теорема. Граф является двудольным тогда и только тогда, когда в нём нет циклов нечётной длины.

Но давайте не будем обсуждать доказательство этой теоремы. Вместо этого научимся по графу понимать, можно ли его вершины правильно раскрасить в два цвета.

Я хочу дать лишь намёки на решение этой задачи. В решении стоит использовать обход в глубину, который будет ходить по вершинам и красить их. Вам понадобится глобальный массив color, в котором для каждой уже покрашенной вершины записывается её цвет. Наконец, стоит помнить текущий цвет, которым мы красим вершины. Лучше всего текущий цвет передавать в функцию dfs: тогда объявление функции будет выглядеть как dfs(v, curr_color). При вызове функции для соседа текущей вершины текущий цвет надо менять на противоположный.

7. Ограничение на глубину рекурсии в Питоне

Рекомендуем не думать над размером стека, который вам реально понадобится, и ставить этой функцией какое-нибудь большое число (10 6 или 10 9 ).

Источник

Реализация графов и деревьев на 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.

Небольшой вариацией на тему этого представления можно назвать сортированные списки смежных вершин. Если списки нечасто меняются, их можно держать отсортированными и использовать бисекцию для проверки смежности вершины, что приведет к немного меньшим накладным расходам (в плане использования памяти и времени итерации), но увеличит сложность проверки до Θ(log₂ 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) будет работать «на лету», вероятно, возвращая смежные вершины как коллекцию или другую форму объекта-итератора.

И последний тип графов, которого я коснусь в этой главе, называется графом подзадач. Это глубокая концепция, к которой я еще неоднократно буду обращаться, описывая различные техники построения алгоритмов. Вкратце, большинство задач может быть разложено на подзадачи: меньшие задачи, часто имеющие похожую структуру. Они формируют вершины графа подзадач, а их зависимости (т.е. какая подзадача от какой зависит) выражаются ребрами. И хотя алгоритмы на графы редко применяются на графах подзадач (они используются больше как инструмент анализа), такие графы отлично позволяют понять технику «разделяй и властвуй» и динамическое программирование.

Источник

Вывести компоненты связности питон

Число компонент связности