Что такое ориентированный граф и в чем его особенности?

Ориентированный граф — это граф, у которого имеется множество вершин (узлов) и множество рёбер (дуг), где каждая дуга имеет направление.

Особенности:

• Направленные рёбра: Движение по ребру возможно только в одном направлении, указанном стрелкой.
• Степень вершины: Для ориентированного графа определяют входящую степень (число рёбер, оканчивающихся в вершине) и исходящую степень (число рёбер, начинающихся в вершине).
• Пути и циклы: Путь — это последовательность вершин, соединённых рёбрами в правильном направлении. Цикл — это путь, начинающийся и заканчивающийся в одной и той же вершине. Ориентированные графы могут содержать ориентированные циклы.
• Связность: Различают слабую связность (игнорируя направления рёбер, граф связан как неориентированный) и сильную связность (для любых двух вершин A и B существует ориентированный путь из A в B и из B в A).
• Представление: Могут быть представлены списком смежности или матрицей смежности, где для ориентированного графа матрица, в общем случае, не симметрична.

Пример представления с помощью списка смежности:

# Граф G = (V, E), где V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

graph = {
    0: [1],
    1: [2],
    2: [0]
}

Пример представления с помощью матрицы смежности:

# Граф G = (V, E), где V = {0, 1, 2}, E = {(0, 1), (1, 2), (0, 2)}

matrix = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # no outgoing edges from 2
]