айкоротшій шлях у зваження графі - це шлях з мінімальною вагою, даже ЯКЩО число ребер у дорозі и можна Зменшити. Если, Наприклад, шлях Складається з п'яти ребер з загальною вагою 24, а шлях - з трьох ребер з загальною вагою 36, то шлях вважається більш коротким. Граф або орграф назівається зв'язного, ЯКЩО будь-яку пару вузлів можна з'єднати прінаймні одним шляхом. Цикл - це шлях, Який ПОЧИНАЄТЬСЯ и закінчується в одній и тій же вершіні. У аціклічному графі Або або орграфі циклі відсутні. Зв'язного аціклічній граф назівається неукоріненім деревом. Структура неукоріненого дерева така ж, что ї у дерева, Тільки в ньом НЕ віділено корінь. Однак Кожна вершина неукоріненого дерева может служити его коренем. p> Інформацію про графа або орграф можна зберігаті двома способами: у вігляді матріці суміжності або у вігляді списку ребер. Матриця суміжності Забезпечує швидкий доступ до ІНФОРМАЦІЇ про ребра графа, протікання ЯКЩО в графі мало ребер, то ця матриця буде містіті набагато больше порожніх комірок, чем заповненості. Довжина списку ребер пропорційна числу ребер у графі, однак при корістуванні списком годину Отримання ІНФОРМАЦІЇ про ребро збільшується. Жоден з ціх методів НЕ перевершує Інший Свідомо. У основу Вибори підходящого методу повінні лежать попередні знання про графа, Які будут оброблятіся алгоритмом. Если в графі багатая вершин, причому Кожна з них пов'язана позбав з невелика кількістю других вершин, список ребер віявляється ефектівнішім, оскількі ВІН займає менше місця, а довжина Списків ребер, что переглядаються, невелика. Если ж число вершин у графі мале, то краще скористати матрицю суміжності: вона буде невелика, и даже ВТРАТИ при зберіганні в матричному вігляді розрідженого графа будут незначні. Если ж у графі багатая ребер и ВІН почти повний, то матриця суміжності всегда є КРАЩА способом зберігання графа. У реалізації програмного продукту Обраний способ зберігання даніх самє матрицю суміжності, Аджея для даного алгоритму вона віявляється більш універсальною. p> Матриця суміжності AdjMat графу G = (V, E) з кількістю вершин запісується у вігляді двовімірного масиву розміром. У Кожній комірці цього масиву записання значення 0 за віключенням позбав тихий віпадків, коли з вершини у вершину проходити ребро, и тоді в комірці записання значення 1, тоб
В
Діагональні елєменти матріці будут Рівні 0, оскількі шлях Із вершини в неї саму НЕ коштує Нічого.
Список ребер AdjList графу з кількістю вершин запісується у вігляді одновімірного масиву Довжина N, КОЖЕН елемент Якого - посилання на агентство список. Такий список прісвоєній до кожної вершини графу и ВІН складає по одному елементами на шкірні вершину графа, сусідню з даною. p align="justify"> Елементи списку ребер для зваження графу містять Додаткове поле, призначеня для зберігання ваги ребра.
1.2 Поиск в глибінь
При роботі з графами часто доводитися Виконувати д...
