Обхід графа в ширину
Пошук в ширину — один із базових алгоритмів, що є основою багатьох інших. Наприклад, алгоритм Дейкстри пошуку найкоротших шляхів з одної вершини і алгоритм Прима пошуку мінімального остового дерева можуть розглядатися як узагальнення пошуку в ширину. Згідно з цим алгоритмом обхід вершин заданого графа 
здійснюється в порядку їх віддаленості від деякої заздалегідь обраної, або зазначеної як початкова, вершини 
(називається коренем пошуку в ширину). Інакше кажучи, спочатку відвідується сама вершина , потім всі вершини, суміжні з , тобто ті, які знаходяться від неї на відстані в одне ребро, потім вершини, що знаходяться від на відстані в два ребра, і так далі.
Пошук в ширину в неорієнтованому графі
Розглянемо алгоритм пошуку в ширину із заданої стартової вершини . Отже, спочатку всі вершини позначаються як непройдені. Першою відвідується вершина , вона стає єдиною пройденою активною вершиною. На наступному кроці, досліджуються ребра, інцидентні даній вершині. У загальному випадку, при такому дослідженні, можливі два варіанти подальших дій:
Збережено в категорії: Дослідження операцій · Мітки: граф, дерево пошуку в ширину, зворотнє ребро, обхід графа в ширину, пошук в ширину, ребро дерева
(Ще не оцінили)
Загрузка ...Обхід графа в глибину
Пошук в глибину (або обхід в глибину) є одним з основних і найбільш часто вживаних алгоритмів обходу всіх вершин і ребер графа. Згідно з цим алгоритмом обхід здійснюється за наступним правилом: у графі 
вибираємо довільну вершину, наприклад 
, і починаємо з неї пошук. Початкова вершина (називається коренем пошуку в глибину) після цього вважається пройденою. На наступному кроці, вибираємо ребро 
, інцидентне вершині (орієнтуємо при цьому його напрямок з в 
), і з його допомогою, переходимо у вершину . Відмітимо, що ребро після цих дій вважається переглянутим і називається ребром дерева, а вершина називається батьківською по відношенню до вершини .
Пошук в глибину в неорієнтованому графі
У загальному випадку, коли ми перейшли в будь-яку вершину графа, в нашому випадку це вершина , виникають два варіанти можливих дій:
Збережено в категорії: Дослідження операцій · Мітки: граф, дерево пошуку в глибину, зворотнє ребро, обхід графа в глибину, пошук в глибину, ребро дерева
(Ще не оцінили) Загрузка ...Попадання точки в заштриховану область: Приклад 3
В даному параграфі продовжимо цикл розв'язоку задач з використанням команди розгалуження, а якщо бути більш точним, то задач на попадання точки в заштриховану область. Для цього, припустимо, що в декартовій системі координат міститься два кола. Перше з них радіуса десять з центром в початку координат і друге — радіуса пять з центром в точці 
.
Ілюстрація графічної області
Необхідно написати програму, що визначає, чи потрапляє точка з заданими координатами 
в зафарбовану на малюнку синім кольором область. Результат роботи вивести у вигляді текстового повідомлення.
Збережено в категорії: Різне · Мітки: коло, координати точки, попадання точки в заштриховану область, потрапляння точки в область, пряма, точка
(Ще не оцінили) Загрузка ...Попадання точки в заштриховану область: Приклад 2
В даному параграфі знову-таки буде розглядатись задача на попадання точки в заштриховану область та її реалізація в середовищі програмування Delphi. Отже, нехай в прямокутній системі координат міститься набір наступних геометричних фігур: два кола радіус яких дорівнює десять та пять відповідно і пряма, проведена під кутом 
до осі абсцис.
Ілюстрація графічної області
Необхідно написати програму, що дозволяє перевірити потрапляння точки з координатами 
в заштрихованную область, що складається з двох фрагментів.
Збережено в категорії: Різне · Мітки: коло, координати точки, попадання точки в заштриховану область, потрапляння точки в область, пряма, точка
(Ще не оцінили) Загрузка ...Знаходження найкоротших маршрутів від першої до всіх інших вершин в орієнтованому графі
Delphi-програма реалізує процес відшукання найкоротших маршрутів від першої до всіх інших вершин в орієнтованому графі, використовуючи для цього алгоритм Дейкстри.
Після запуску проекту на екран виводиться форма, в якій, на першому кроці, необхідно задати граф. Для цього достатньо, у компоненті типу TEdit, вказати кількість вершин графа, що розглядається, та скористатись кнопкою «Створити матрицю». В результаті, на головній формі появиться відповідна таблиця типу TStringGrid (матриця суміжності). Далі, необхідно заповнити її даними, які відповідатимуть за відстані між вершинами. Також відмітимо, що не існуючі ребра позначаються символом «-».
Після того, як матрицю заповнено, пошук найкоротших маршрутів здійснюється за допомогою кнопки «Знайти мінімальні маршрути». В результаті виконання даного кроку, в нижній частині форми, а саме в компоненті TMemo, здійснюється вивід списку вершин, через які проходять мінімальні маршрути, а також вивід їх довжин.
Збережено в категорії: Програми на Delphi (Дослідження операцій) · Мітки: алгоритм Дейкстри на delphi, граф, мінімальні маршрути, матриця суміжності, орієнтований граф, пошук найкоротших маршрутів
(Кількість голочів: 2, середній бал: 5.00 із 5) Загрузка ...Попадання точки в заштриховану область: Приклад 1
Нехай в декартові системі координат, міститься набір наступних геометричних фігур: коло радіус якого дорінює десять; пряма, яка паралельна осі ординат і проходить через точку 
; пряма, проведена під кутом 
до осі абсцис.
Складемо delphi-програму, основним завданням якої буде визначення того, чи попадає задана користувачем точка з координатами 
в заштриховану область, включаючи її межі.
Ілюстрація графічної області
Для цього запустимо середовище програмування Delphi, створимо новий проект, та на головній формі розмістимо компоненти наступним чином:
Збережено в категорії: Різне · Мітки: коло, координати точки, попадання точки в заштриховану область, попадання точки в область, пряма, точка
(Кількість голочів: 1, середній бал: 5.00 із 5) Загрузка ...Знаходження найкоротшого шляху між двома вершинами в орієнтованому графі використовуючи алгоритм Дейкстри
Delphi-проект розроблено за проханням користувача на ім'я andrey_khorolskiy («...Бажано передбачити можливість пошуку найкоротшого маршруту не тільки між початковою та кінцевою вершинами, але і між початковою і проміжною без пошуку маршруту до кінцевої...») і реалізує процес знаходження найкоротшого шляху між двома вершинами в орієнтованому графі, використовуючи для цього алгоритм Дейкстри.
Виходячи з того, що інтерфейс головної форми розглядуваного delphi-проекту аналогічний проектам, які реалізують інші алгоритми на графах, лише з однією відмінністю (панель інструментів міститься додаткове поле типу TEdit, в яке, способом введення з клавіатури, необхідно вказати номер вершини, для якої будується маршрут), то основні її елементи та процес побудови орієнтованого графа розглядати не будемо. Це все детально можна почитати перейшовши, наприклад, за посиланням Знаходження найкоротшого шляху від однієї вершини графа до всіх інших вершин в середовищі програмування delphi. А перейдемо до практики, тобто провіримо його роботу на конкретному прикладі.
Для цього, розглянемо деякий орієнтований граф, і припустимо, що для нього необхідно знайти мінімальний маршрут від вершини номер один, до вершини номер три.
Збережено в категорії: Програми на Delphi (Дослідження операцій) · Мітки: Delphi програма, Delphi проект, алгоритми на графах, вершина графа, дослідження операцій на delphi, найкоротший маршрут між двома вершинами, орієнтоване ребро, орієнтований граф
(Кількість голочів: 1, середній бал: 5.00 із 5) Загрузка ...
Загрузка ...