Граф — это нелинейная структура данных, состоящая из конечного множества вершин и рёбер, соединяющих их.
Путь в графе — это последовательность вершин такая, что каждая пара соседних вершин соединена ребром. Другими словами, для каждого существует ребро между и .
Первая вершина называется началом пути, а последняя вершина называется концом пути.
Примеры с рисунка:
Длина пути — это количество рёбер в нём.
Цикл — это путь, который начинается и заканчивается в одной и той же вершине, то есть .
Пример с рисунка:
Компонента связности — это множество вершин такое, что любая вершина из множества может достичь любой другой вершины из того же множества, используя рёбра графа.
Для графа на рисунке компоненты связности:
Рёбра могут быть ориентированными или неориентированными.
Если ребро неориентированное, то мы можем перемещаться как из в , так и из в .
Если ребро ориентированное, то перемещение разрешено только из в .
Ребро может иметь вес .
Вес представляет стоимость использования этого ребра. Например, в дорожной сети вершины могут представлять города, рёбра могут представлять дороги, а вес может представлять стоимость или расстояние перемещения по этой дороге.
Между одной и той же парой вершин может быть более одного ребра. Такие рёбра называются кратными рёбрами или параллельными рёбрами.
У вершины также может быть ребро к самой себе. Такое ребро называется петлёй.
Неориентированный граф — это граф, в котором все рёбра неориентированные.
Ориентированный граф — это граф, в котором все рёбра ориентированные.
Ациклический ориентированный граф — это ориентированный граф, который не содержит циклов.
Связный граф — это граф, в котором каждая вершина может достичь любой другой вершины.
Другими словами, он состоит ровно из одной компоненты связности.
Дерево — это связный неориентированный граф без циклов.
Важные свойства дерева:
Двудольный граф — это граф, вершины которого можно разделить на две группы так, что каждое ребро соединяет вершину из одной группы с вершиной из другой.
То есть нет рёбер, соединяющих две вершины из одной и той же группы.
Бинарное дерево — это дерево, в котором каждая вершина имеет не более двух детей.
Каждый ребёнок сам является корнем другого бинарного дерева.
В каждой вершине мы обычно храним данные и указатели на её родителя и детей.
Существует три распространённых способа обхода бинарного дерева:
Алгоритм:
Результат обхода:
Алгоритм:
Результат обхода:
Алгоритм:
Результат обхода:
struct Node {
Node* parent;
Node* left;
Node* right;
int value;
Node(Node* parent_, int value_) : parent(parent_),
value(value_),
left(nullptr),
right(nullptr) {}
};
void printPreOrder(Node* node) {
if (node == nullptr) {
return;
}
cout << node->value << " ";
printPreOrder(node->left);
printPreOrder(node->right);
}
void printInOrder(Node* node) {
if (node == nullptr) {
return;
}
printInOrder(node->left);
cout << node->value << " ";
printInOrder(node->right);
}
void printPostOrder(Node* node) {
if (node == nullptr) {
return;
}
printPostOrder(node->left);
printPostOrder(node->right);
cout << node->value << " ";
}