колиць, зокрема від кількості рядків і кількості чисел в кожному рядку.
Кожен вузол динамічного списку, що використовується в програмі, має наступну структуру:
struct DirectedGraph {oneArc; * previousArc; * nextArc;
};
До складу даної структури входять: змінна-представник структурного типу ArcGraph oneArc, два покажчика типу int (під дані типу int відводиться чотири байти). Так як структура ArgGraph складається з двох змінних типу int, то змінна oneArc має розмір 8 байт. І цього випливає, що дана структура має розмір 4 +4 +8 = 16 байт. p align="justify"> Матриця суміжності має тип bool, тобто кожен елемент матриці буде мати розмір 1 байт.
Так само в програмі містяться: покажчик на об'єкт класу ostream, що займає 80 байт, об'єкт класу fstream, що займає 184 байти, об'єкт класу string, що займає 32 байти, п'ять змінних типу short, кожна з яких займає 2 байта, три змінних типу int, що займають по 4 байти, змінна типу bool, що займає 1 байт і сімнадцять змінних типу char, що займають по 1 байту.
Прийнявши за M кількість дуг у графі, за N кількість вершин, а так само з урахуванням пам'яті, займаної усіма змінними, ми отримаємо таку формулу
В
Висновок
Під час виконання курсової роботи був розроблений алгоритм, вирішальний поставлене завдання. За складеним алгоритмом була написана програма, що дозволяє:
В· Вводити список околиць орієнтованого графа з файлу;
В· Виводити на екран або у файл список околиць і ступеня результату всіх вершин;
В· Знаходити вершину з найбільшим ступенем результату;
В· Видаляти вершини, суміжні з вершиною, що має найбільший ступінь результату;
В· Складати матрицю суміжності і виводити її на екран або у файл.
Список використаної літератури
В«C/C + + програмування на мові високого рівняВ» Т. А. Павловська.
В«Повний довідник по С + +, 4-е виданняВ» Герберт Шилдт
В«Теорія графівВ» В. В. Бєлов, У. М. Воробйов.
Рішення контрольних прикладів
Приклад 1
Вихідний граф:
В
Граф після видалення:
В
матриця суміжний граф алгоритм
Аналіз тимчасової складності:
Використовуючи формулу 1, а так само з урахуванням того, що M = 38, 16, N = 17, ступінь результату вершини 1: 3, ступінь результату вершини 2: 2, ступінь результату вершини 3: 4, ст...
