Как создать ориентированный граф питон

Бывают и несимметричные отношения, и их изображают ориентированными рёбрами (directed edges). В ориентированном графе наличие ребра из x в y не гарантирует наличие ребра из y в x.

Если явно не указано обратное, то рассматривают только графы без петель (loop) и без кратных рёбер (multiple edge). Такие графы называются простыми (simple).

Самые простые графы — это деревья. Во многих задачах, связанных с графами, используется обходы графа, в результате которых в графе выделяются деревья, состоящие из некоторых вершин графа и некоторых его рёбер. У этих деревьев отмечена вершина, которая называется его корнем (root). Дерево с отмеченной вершиной — корнем — называется корневым деревом (rooted tree).

В корневых деревьях чётко различаются путь к корню и путь от корня. Сосед вершины на пути к корню называется её родителем (parent). Соседи вершины на пути от корня называются её детьми или сыновьими вершинами (child, children). Все вершины на пути из вершины к корню, кроме исходной, называются её предками (ancestor). Все вершины на пути из корня называются потомками (descendant). Вершины, у которых общий родитель, называются братьями (sibling). И наконец вершины, у которых нет потомков, называются листьями (leaf, leaves, terminal vertex).

Представление графа

Рассмотрим граф c $n = |V|$ вершинами $v_1,\ldots‌,v_n$. Его матрицей смежности (adjacency matrix) называется $(n\times n)$-матрица a, в которой $$ a_ = \begin 1,&\text\\ 0 &\text \end $$ Матрица смежности неориентированного графа, таким образом, симметрична ($a_ = a_$). В таком представлении мы можем за время O(1) проверить, соединены ли данные вершины ребром (посмотрев на один элемент массива). В то же время хранение матрицы требует памяти O(n 2 ), что во многих случаях неэкономно. Альтернативное представление — список смежности (adjacency list). Требуемая при этом память пропорциональна размеру графа (сумме числа вершин и числа рёбер). Элементами списка смежности являются списки, по одному для каждой вершины графа. Для вершины u в таком списке хранятся вершины, в которые ведут рёбра из u, то есть вершины v, для которых $(u, v) \in E$. Для ориентированного графа каждое ребро входит только в один из этих списков (для начальной вершины), а для неориентированного в два (для двух концов ребра). Список смежности, таким образом, требует памяти $O(|V|+ |E|)$. Проверка наличия ребра $(u, v)$ теперь требует просмотра списка вершины u (что может быть больше O(1) шагов, если вершины хранятся именно в списке, а не в множестве или словаре). Зато в этом представлении легко просмотреть всех соседей заданной вершины (что часто бывает необходимо). Список смежности для неориентированного графа симметричен (если u содержится в списке для v, то и v содержится в списке для u).

Матрица смежности или список смежности?

Что лучше? Ответ зависит от отношения между числом вершин $|V|$ и числом рёбер $|E|$. Заметим, что $|E|$ может быть довольно малым — порядка $|V|$ (если $|E|$ сильно меньше $|V|$, то граф уже вырожденный — в частности, содержит изолированные вершины). Или же довольно большим — порядка $|V|^2$ (если граф содержит все возможные рёбра). Графы с большим числом рёбер называют плотными (dense), с малым — разреженными (sparse).
Выбирая алгоритм, полезно понимать, с какими графами ему в основном придётся иметь дело. Важно это и при хранении: если хранить веб-граф, в котором больше восьми миллиардов вершин, в виде матрицы смежности, то занимать она будет миллионы терабайтов, что сравнимо с общей ёмкостью всех жёстких дисков в мире. И дальше, скорее всего, будет только хуже (матрица может расти быстрее, чем производство дисков). А вот хранить граф Интернета в виде списка смежности вполне разумно, поскольку хранить нужно несколько десятков миллиардов гиперссылок, каждая из которых будет занимать в списке всего несколько байтов, и такого размера диск поместится в карман. Такая разница происходит из-за того, что граф Интернета очень разрежен: страница содержит в среднем пару десятков ссылок на другие страницы — из нескольких миллиардов возможных.

Напоминание про множества и словари

Про множества

Задание множеств

A = set() # Пустое множество A = # Явное перечисление элементов A = set('hello') # Множество букв в строке B = [1, 2, 1, 2]; A = set(B) # Множество из списка или любого итерируемого объекта A = # Генератор множеств

Работа с элементами множеств

C = for elem in C: # Перебираем все элементы множества print(elem) sorted(C) # Список из отсортированных элементов множества 1 in C # Проверка принадлежности A.add(3) # Добавление элемента A.remove(3) # Удаление элемента, который есть в множестве A.discard(4) # Удаление элемента, которого может не быть в множестве A.pop() # Извлечение случайного элемента из множества с удалением его

Операции с множествами

len(A) # Количество элементов в множестве A | B # Возвращает множество, являющееся объединением множеств A и B. A |= B # Добавляет в множество A все элементы из множества B. A & B # Возвращает множество, являющееся пересечением множеств A и B. A &= B # Оставляет в множестве A только те элементы, которые есть в множестве B. A - B # Возвращает разность множеств A и B (A, но не B). A -= B # Удаляет из множества A все элементы, входящие в B. A ^ B # Возвращает симметрическую разность множеств A и B. A ^= B # Записывает в A симметрическую разность множеств A и B. A = B # Возвращает true, если B является подмножеством A. A < B # Эквивалентно A B # Эквивалентно A >= B and A != B

Про словари

Задание словарей

D = <> # Пустой словарь D = # Явное перечисление D = dict([(1, 'a'), (2, 'b')]) # Словарь из списка пар элементов D = dict(zip([1, 2], ['a', 'b'])) # Словарь из итерируемого объекта, возвращающего пары элементов (ключ-значение) D = # Генератор словарей

Работа с элементами словаря

len(D) # Количество элементов в словаре D[key] # Поиск по ключу, который есть в словаре key in D # Проверка принадлежности словарю D[key] = value # Установка или изменение значения del D[key] # Удаление ключа, который есть в словаре value = D.pop(key) # Удаления ключа вместе с возвращением значения value = D.pop(key, no_key_value) # Удаления ключа вместе с возвращением значения. Если ключа нет, то no_key_value key, value = D.popitem() # Извлечение из словаря пары (ключ, значение) с удалением ключа D.get(key, no_key_value) # Значение по ключу, no_key_value, если ключа нет D[key] = D.get(key, 0) + 1 # Самая простая реализация счётчика for key in D: # Перебираем все ключи print(key, D[key]) for key, value in D.items(): # Перебираем все пары (ключ, значение) print(key, value) for value in D.values(): # Перебор всех значений print(value) sorted(D) # Отсортированный список ключей sorted(D.values()) # Отсортированный список значений sorted(D.items()) # Отсортированный по ключу список пар (ключ, значение) sorted(D.items(), key=lambda x: x[1]) # Отсортированный по значению список пар (ключ, значение)

Список смежности и матрица смежности: туда и обратно

A: От матрицы смежности к списку ребер, неориентированный вариант

Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.

Входные данные включают число n — количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, — его матрицу смежности. Выведите список ребер заданного графа (в любом порядке).

5 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0
1 3 2 3 2 5

B: От списка ребер к матрице смежности, неориентированный вариант

Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.

Входные данные включают число n — количество вершин в графе, и число m — количество рёбер. Затем следует m пар чисел — ребра графа. Выведите матрицу смежности заданного графа.

5 3 1 3 2 3 2 5
0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0

C: От матрицы смежности к списку ребер, ориентированный вариант

Ориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.

Входные данные включают число n — количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, — его матрицу смежности. Выведите список ребер заданного графа (в любом порядке).

5 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
2 5 3 1 3 2

D: От списка ребер к матрице смежности, ориентированный вариант

Простой ориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.

Входные данные включают число n — количество вершин в графе, и число m — количество рёбер. Затем следует m пар чисел — ребра графа. Выведите матрицу смежности заданного графа.

5 3 1 3 2 3 5 2
0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

Как хранить графы в программе

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

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

В спортивном программировании вершины графа — обычно последовательные числа от 1 до $n$. В этом случае граф лучше хранить как список списков или вектор векторов (в C++). Однако в этом разминочном листке предполагается использование питона и словаря множеств. Это удобно и быстро. Спортивные модификации алгоритмов будут в отдельном листке.

E: digraph_from_input

Программа получает на вход число рёбер в ориентированном графе N . Далее следует N строк, задающие рёбра графа. Каждая строка имеет вид откуда_ребро куда_ребро .

Программа должна сформировать словарь digraph смежности ориентированного графа и вывести его при помощи функции pprint из модуля pprint .

Реализуйте функцию digraph_from_input() , которая считывает граф в таком формате из стандартного ввода и возвращает словарь digraph .

8 A B B C B D B E C E D E E F G D
<'A': <'B'>, ‘B’: , ‘C’: , ‘D’: , ‘E’: , ‘F’: set(), ‘G’: >

F: graph_from_input

Программа получает на вход число рёбер в неориентированном графе N . Далее следует N строк, задающие рёбра графа. Каждая строка имеет вид откуда_ребро куда_ребро .

Программа должна сформировать словарь graph смежности неориентированного графа и вывести его при помощи функции pprint из модуля pprint .

Реализуйте функцию graph_from_input() , которая считывает граф в таком формате из стандартного ввода и возвращает словарь graph .

8 A B B C B D B E C E D E E F G D
<'A': <'B'>, ‘B’: , ‘C’: , ‘D’: , ‘E’: , ‘F’: , ‘G’: >

G: Степень вершины

Дан неориентированный граф.

Выведите степень каждой вершины. Вершины должны выводиться в лексикографическом порядке.

8 A B B C B D B E C E D E E F G D
A 1 B 4 C 2 D 3 E 4 F 1 G 1

H: Эйлеров цикл в связном графе

Дан связный неориентированный граф.

Выведите YES , если в нём есть эйлеров цикл, и NO иначе.

Python в СРЦОД: 8. Матрица смежности и список ребер

Граф называется неориентированным, если по всем его ребрам можно ходить в обоих направлениях. Так как граф простой, то у него не должно быть петель (т.е. для любой вершины этого графа нет ребра в её саму). Считываем в матрицу смежности весь граф и проверяем, чтобы для любого i и j (i!=j) выполнялось a[i][j]==a[j][i], а если i==j, то a[i][j] всегда должно быть равно нулю.

По заданной квадратной матрице \(n times n\) —>n×n из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

Входные данные

На вход программы поступает число \(n\) \((1 \le n \le 100)\) – размер матрицы, а затем n строк по \(n\) чисел, каждое из которых равно 0 или 1, – сама матрица.

Выходные данные

Выведите «YES», если приведенная матрица может быть матрицей смежности простого неориентированного графа, и «NO» в противном случае.

Входные данные

5 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0