75658

Графи. Обхід графу. Пошук

Лабораторная работа

Информатика, кибернетика и программирование

Користувач довільним чином розміщує точки графа – майбутні вузли. Потім за допомогою діалогового вікна заповнює матрицю суміжності. Ця матриця формує ребра графа, які можна окремо вивести на екран у вигляді списку. Матриця заповнюється не нижче головної діагоналі, так як вона симетрична відносно неї для неорієнтованого графа. Зв’язки між вузлами можна видалити і побудувати знову.

Украинкский

2015-01-24

224.07 KB

0 чел.

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Лабораторна робота №8 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013

Тема: Графи. Обхід графу. Пошук.

Мета: набуття навичок програмування графів.

Завдання:

Забезпечити зберігання графа у вигляді матриці суміжності.

Варіант № 9.

9.

Розробити програму, яка за матрицею суміжності формує множину ребер.

Складність алгоритму

Складність алгоритму обходу графа  дорівнює O(  3N2 + 2N ) від t, де:

t - час виконання;
Nкількість вузлів графа.

Опис алгоритму

Користувач довільним чином розміщує точки графа – майбутні вузли. Потім за допомогою діалогового вікна заповнює матрицю суміжності. Ця матриця формує ребра графа, які можна окремо вивести на екран у вигляді списку. Матриця заповнюється не нижче головної діагоналі, так як вона симетрична відносно неї для неорієнтованого графа. Зв’язки між вузлами можна видалити і побудувати знову.


Блок-схема алгоритму


Лістинг фрагментів програми 

//---Node.h—------------------------------------------------------------------------------------

#pragma once

class Node

{

public:

int number;

int x;

int y;

Node *next[6];

bool self;

Node(int _number, int _x, int _y); Node(const Node &arg);

Node(void);

~Node(void);

void Show(HDC hdc);

};

extern Node** graph;

extern int MAX_ARRAY;

//---Node.cpp ------------------------------------------------------------------------------------

#include "StdAfx.h"

Node** graph;

int MAX_ARRAY=1;

Node::Node(void)

{

for (int i=0; i<6; ++i)

 next[i]=0;

x=300;

y=50;

self=false;

}

Node::Node(int _number, int _x, int _y):number(_number), x(_x), y(_y)

{

for (int i=0; i<6; ++i)

 next[i]=0;

self=false;

}

Node::Node(const Node &arg)

{

number=arg.number;

x=arg.x;

y=arg.y;

for (int i=0; i<6; ++i)

 next[i]=0;

self=false;

}

Node::~Node(void)

{

}

void Node::Show(HDC hdc)

{

HPEN hNodePen, hSelfPen, holdpen;

HBRUSH hNodeBrush, holdbrush;

 

hNodePen = CreatePen(PS_SOLID, 4, RGB(21, 236, 150));

hSelfPen = CreatePen(PS_SOLID, 4, RGB(150, 200, 150));

holdpen = (HPEN)SelectObject(hdc, hNodePen);

hNodeBrush = CreateSolidBrush(RGB(21, 236, 150));

holdbrush = (HBRUSH)SelectObject(hdc, hNodeBrush);

 

if (this!=0)

for (int i=0; i<MAX_ARRAY; ++i)

 if (next[i]!=0)

 {

   holdpen = (HPEN)SelectObject(hdc, hSelfPen);

   POINT pnt;

   ::MoveToEx(hdc, x, y, &pnt);

   ::LineTo(hdc, next[i]->x, next[i]->y);

 }

if (self)

{

 holdpen = (HPEN)SelectObject(hdc, hSelfPen);

 POINT pnt;

  ::MoveToEx(hdc, x, y, &pnt);

  ::LineTo(hdc, x, y-60);

  ::LineTo(hdc, x-60, y-60);

  ::LineTo(hdc, x-60, y);

  ::LineTo(hdc, x, y);

}

holdpen = (HPEN)SelectObject(hdc, hNodePen);

Ellipse(hdc, x-30, y-30, x+30, y+30);

 

char buffer[20];

itoa (number,buffer,10);

::TextOutA(hdc, x-5, y-7, (LPCSTR) buffer, strlen(buffer) );

 

::DeleteObject(hNodePen);

::DeleteObject(hSelfPen);

::DeleteObject(hNodeBrush);

 

}

// ------ stdafx.h: ------------------------------------------------------------------------------------

#pragma once

#include "targetver.h"

#define WIN32_LEAN_AND_

#include <windows.h>

#include <stdlib.h>

#include <malloc.h>

#include <memory.h>

#include <tchar.h>

#include "Node.h"

#include <string>

#include <time.h>

#include <vector>

using namespace std;

//---- Main.cpp ------------------------------------------------------------------------------------

У цьому файлі міститься графічне моделювання графа, функції малювання, роботи з вікном, створення вікон тощо.

void FindEdges()  //  функція обходу графу з пошуком ребер

{

for (int i=0; i<MAX_ARRAY; ++i)

{

 if(graph[i]->self)

 {

  nodes.push_back(graph[i]->number);

  nodes.push_back(graph[i]->number);

 }

 for (int j=i; j<MAX_ARRAY; ++j)

 {

  if(graph[i]->next[j]!=0)

  {

   nodes.push_back(graph[i]->number);

   nodes.push_back(graph[i]->next[j]->number);

  }

 }

}

strcpy(edges, "The edges of the graph are: ");

for (size_t i=0; i<nodes.size(); ++i)

{

 char buffer[20];

 itoa (nodes[i], buffer, 10);

 strcat(edges, buffer);

 strcat(edges, "->");

 itoa (nodes[i+1], buffer, 10);

 strcat(edges, buffer);

 strcat(edges, ", ");

 ++i;

}

}

Результат виконання 

Висновки

Набуто навички програмування графів. В результаті виконання лабораторної роботи створено програму для побудови графа за допомогою матриці суміжності і забезпечено формування множини ребер.


 

А также другие работы, которые могут Вас заинтересовать

47384. Организация логистических процессов распределения товаров (на примере ОАО "Полоцкий молочный комбинат") 331.39 KB
  Предмет исследования: распределительная логистика Цель работы: обоснование актуальности создания распределительного центра продукции ОАО Полоцкий молочный комбинат в городе Риге обоснование актуальности использования услуг дистрибьютора в городе Пскове и актуальность внедрения логистического программного обеспечения на предприятии и оценка экономической эффективность предложенных мероприятий. Исследование и разработки: изучены основные аспекты логистических процессов распределения товаров проанализирована организация логистической...
47385. Разработка маркетинговой стратегии развития организации на примере ООО “Антарес” 170.01 KB
  Раздел 1 Маркетинг как философия производства Содержит анализ литературных источников посвященных рассмотрению теоретических аспектов маркетинга классификации услуг анализ потребителей и их потребностей сегментации рынка услуг по пошиву одежды особенностям стимулирования сбыта в данной отраслевой группе влияние рекламы как основного элемента коммуникационного воздействия на потребителя.1 Понятие маркетинга особенности маркетинга услуг.2 Эффективность внедряемой услуги 655 Правовая часть...
47386. Влияние самооценки на успешность обучения в младшем школьном возрасте 383.5 KB
  Широкое распространение феномена оценки в учебновоспитательном процессе школы послужило причиной того что оценивание учителем результатов учебной деятельности учащихся и самооценивание выделилось в последние годы в самостоятельное направление. Согласно теории учебной деятельности оценочная деятельность порождает потребность ученика или учителя получить информацию о том соответствует или нет качество знаний и умений учащихся по предмету требованиям программы. Целью оценочной деятельности является таким образом контроль успеваемости...
47387. Разработка миссии и целей компании «Ultra» 254.18 KB
  В первую очередь целевое начало в деятельности организации возникает потому что организация это объединение людей преследующих определенные цели. так же как и те кто являются хозяевами организации или работают в организации преследуя свои собственные цели при взаимодействии с организацией придают ее существованию определенную направленность и тем самым развивают целевое начало в деятельности организации. Цели и задачи исследования. Первая глава посвящена теоретическому осмыслению понятий миссия цели система целей и др.
47388. Технологічний процес визначення оптимальних змішаних стратегій автотранспортного підприємства 412 KB
  Особлива увага приділяється автомобільному транспорту бо саме він є самим мобільним і швидко реагує на зміни ринкового середовища тому саме цьому виду транспорту надають перевагу наші підприємці при здійсненні внутрішніх перевезень і перевезень в країни ближнього зарубіжжя. Україна росташована в центрі Європи на перетині важливих торгівельних шляхів і тому особливу увагу слід приділяти розвитку транспорту щоб не лишень забезпечувати власні потреби але й виводити цю галузь господарства на міжнародний рівень. Застарілі методи...
47389. Отграничение вандализма от смежных составов преступления 101.77 KB
  В соответствии с ч.1 статьи 214 Уголовного Кодекса Российской Федерации:- вандализм, то есть осквернение зданий или иных сооружений, порча имущества на общественном транспорте или в иных общественных местах,- (наказывается штрафом в размере до 40 тысяч рублей или в размере заработной платы или иного дохода осужденного за период до 3 месяцев, либо обязательными работами на срок от 120 до 180 часов, либо исправительными работами на срок от 6 месяцев до 1 года, либо арестом на срок до 3 месяцев).
47390. Строительство в г. Абакан, расчет и архитектурные особенности 2.07 MB
  Недостатком является стесненность площадки что не позволяет оптимально разместить на ней механизмы и материалы необходимые для проведения работ. Варианты фундаментов: ленточный работающий как балка на упругом основании; столбчатый под колонны. Данный дипломный проект был разработан при помощи ЭВМ. Методы проверки качества маркировка и транспортирование пиломатериалов должно производится по ГОСТ 656463 укладка и хранение – по ГОСТ 3808 поверхностная антисептическая обработка – по ГОСТ 1095064.
47391. Специфика патриотического воспитания дошкольников с отклонениями в эмоционально-личностном развитии и поведении 99.95 KB
  Они делают акцент на приобщение детей к культурному наследию народа. Куликова предлагают одним из решений проблемы воспитания патриотизма детейдошкольников познание ими РодиныРоссии. разработать комплекс занятий для детей с отклонениями направленных на патриотическое воспитание. Уровень патриотического воспитания детей дошкольного возраста с отклонениями в развитии и поведении станет выше если в процессе работы будут использованы игровые словесные наглядные экскурсионные методы и формы функционирования воспитательной системы...