Омӯзиши таърифҳои асосии назарияи графҳо
Граф як сохтори додаҳои ғайрихаттӣ мебошад, ки аз маҷмӯи маҳдуди қуллаҳо ва канорҳо, ки онҳоро пайваст мекунанд, иборат аст.
Роҳ дар граф пайдарпаии қуллаҳо мебошад, ки ҳар як ҷуфти қуллаҳои ҳамсоя бо як канор пайваст аст. Ба ибораи дигар, барои ҳар як , байни ва як канор вуҷуд дорад.
Қуллаи аввал оғоз-и роҳ номида мешавад, ва қуллаи охир анҷом-и роҳ номида мешавад.
Намунаҳо аз расм:
Дарозии роҳ шумораи канорҳо дар он аст.
Давр роҳест, ки аз ҳамон қулла оғоз шуда дар ҳамон қулла анҷом меёбад, яъне, .
Намуна аз расм:
Компоненти пайваст маҷмӯи қуллаҳост, ки ҳар қулла дар маҷмӯъ метавонад бо истифода аз канорҳои граф ба ҳар қуллаи дигар дар ҳамон маҷмӯъ расад.
Барои графи дар расм, компонентҳои пайваст инҳоянд:
Канорҳо метавонанд самтдор ё бесамт бошанд.
Агар канор бесамт бошад, пас мо метавонем ҳам аз ба ва ҳам аз ба ҳаракат кунем.
Агар канор самтдор бошад, пас ҳаракат танҳо аз ба иҷозат дода мешавад.
Канор метавонад вазн дошта бошад.
Вазн арзиши истифодаи он канорро ифода мекунад. Масалан, дар шабакаи роҳҳо, қуллаҳо метавонанд шаҳрҳоро ифода кунанд, канорҳо метавонанд роҳҳоро ифода кунанд, ва вазн метавонад арзиш ё масофаи сафар дар тӯли он роҳро ифода кунад.
Мумкин аст байни ҳамон ҷуфти қуллаҳо зиёда аз як канор вуҷуд дошта бошад. Чунин канорҳо канорҳои сершумор ё канорҳои параллелӣ номида мешаванд.
Қулла инчунин метавонад ба худ як канор дошта бошад. Чунин канор ҳалқа номида мешавад.
Графи бесамт графест, ки дар он ҳамаи канорҳо бесамт мебошанд.
Графи самтдор графест, ки дар он ҳамаи канорҳо самтдор мебошанд.
Графи самтдори бедавр графи самтдорест, ки ягон давр надорад.
Графи пайваст графест, ки дар он ҳар қулла метавонад ба ҳар қуллаи дигар расад.
Ба ибораи дигар, он аз маҳз як компоненти пайваст иборат аст.
Дарахт графи бесамти пайвастест, ки давр надорад.
Хосиятҳои муҳими дарахт:
Графи дуқисмӣ графест, ки қуллаҳои он метавонанд ба ду гурӯҳ тақсим карда шаванд, ба тавре ки ҳар як канор қуллаеро аз як гурӯҳ ба қуллае аз гурӯҳи дигар пайваст мекунад.
Пас ягон каноре нест, ки ду қулларо аз як гурӯҳ пайваст кунад.
Дарахти дуӣ дарахтест, ки дар он ҳар қулла ҳадди аксар ду фарзанд дорад.
Ҳар як фарзанд худ решаи як дарахти дуии дигар аст.
Дар ҳар қулла, мо одатан додаҳо ва ишорагарҳоро ба волидайн ва фарзандонаш нигоҳ медорем.
Се роҳи маъмул барои гузариши дарахти дуӣ вуҷуд дорад:
Алгоритм:
Натиҷаи гузариш:
Алгоритм:
Натиҷаи гузариш:
Алгоритм:
Натиҷаи гузариш:
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 << " ";
}