Ориентированный граф (или диграф) — это структура данных, состоящая из множества вершин (узлов) и множества ориентированных ребер (дуг), соединяющих эти вершины. Каждое ребро имеет направление, указывающее, какая вершина является начальной, а какая — конечной.
Основные характеристики:
- Вершины (Nodes / Vertices): Элементы графа, представленные точками. Могут обозначать объекты, состояния или этапы.
- Ребра (Edges / Arcs): Связи между вершинами. В ориентированном графе ребро имеет направление, указывающее на переход от одной вершины к другой. Обозначаются упорядоченной парой (u, v), где u — начальная вершина, v — конечная.
- Направленность: Ключевая особенность, отличающая ориентированный граф от неориентированного. Перемещение возможно только вдоль направления ребра. Ребро из A в B не означает возможности перемещения из B в A, если нет отдельного ребра из B в A.
- Петли (Loops): Ребро, соединяющее вершину саму с собой (v, v).
- Кратные ребра (Multiple Edges): Несколько ребер, соединяющих одну и ту же пару вершин в одном и том же направлении. В простых ориентированных графах кратные ребра не допускаются.
- Изолированные вершины: Вершины без входящих и исходящих ребер.
- Степень вершины:
- Входящая степень (In-degree): Количество ребер, входящих в вершину.
- Исходящая степень (Out-degree): Количество ребер, исходящих из вершины.
Применение в QA:
- Графы состояний для тестирования конечных автоматов.
- Графы потоков управления для анализа кода и построения тестовых случаев.
- Моделирование зависимостей в системах (например, зависимости между сервисами или модулями).
- Тестирование сценариев использования со строгой последовательностью действий.