Графы можно хранить и в форме списка ребер. В этом случае каждое ребро обозначается двумя числами − номером начальной и конечной вершины.
Количество вершин графа хранится в отдельной переменной, так как изолированные (не связанные ни с одной из вершин) вершины не попадают в список ребер.
num_vertices = 6 # Количество вершин
edges_list = [[0, 1], # Список ребер
[0, 2],
[0, 4],
[1, 2],
[1, 3],
[1, 4],
]
Познакомимся еще с некоторыми понятиями, имеющими отношение к графам. Последовательность ребер, в которой последняя вершина каждого ребра является началом другого ребра, за исключением последней, называется путем. Замкнутый путь называют циклом. Так, в верхнем примере ребра, соединяющие вершины 1, 2, 3, образуют путь, а путь между вершинами 1, 2, 5 − это цикл.
Как было отмечено, совсем не обязательно соединение всех вершин графа между собой. Если в графе существует путь между любыми двумя его вершинами, то его называют связным графом.
Если ребро соединяет вершину саму с собой, то такое ребро называют петлей. Если ребро имеет определенное направление (например, ребро идет не от вершины В к вершине А, а из вершины А к вершине В), то такое ребро называют дугой. То есть ребро соединяет две вершины графа, а дуга начинается из одной вершины и заканчивается в другой. Граф, все ребра которого являются дугами, называют ориентированным графом, или диграфом.
Для сохранения ориентированных графов в памяти можно использовать (немного изменив предыдущие способы) следующие способы представления:
Дерево (древовидная структура) является одним из видов графа − это связный граф без цикла. То есть между любыми двумя вершинами дерева есть путь, но в дереве нет замкнутых путей.