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;

}

}

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

Висновки

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


 

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

15997. Государственное и муниципальное управление 1.44 MB
  В предлагаемом пособии рассматривается в соответствии с утвержденной учебной программой широкий круг вопросов становления и развития местного самоуправления в России и за рубежом, дается характеристика органов местного самоуправления и муниципальных образований, рассматриваются вопросы формирования и использования местных финансов,
15998. Коррупция и организованная преступность в посткоммунистических государствах 369.5 KB
  Неформальные системы должны стать предметом специального изучения специалистов в области коррупции и организованной преступности в любом географическом контексте. Организованная преступность неизбежно окаймлена рамками неформальных систем и обычно зависит от коррупции
15999. Конкурентне право 2.99 MB
  У навчальному посібнику розглянуто основні аспекти правового захисту економічної конкуренції в Україні, окреслено поняття й види конкуренції та монополії, висвітлено основні положення законодавства про захист економічної конкуренції. Посібник містить навчальну програму курсу «Конкурентне право України».
16000. Виктимология социальные и криминологические проблемы 1.47 MB
  Туляков Вячеслав Алексеевич ВИКТИМОЛОГИЯ В монографии приведены результаты теоретического анализа основных науковедческих проблем современной виктимологии как перспективного направления социальноправовых исследований обеспечивающего повышение эффективнос...
16001. ВИКТИМОЛОГИЯ 924.5 KB
  Туляков В.А. ВИКТИМОЛОГИЯ ВИКТИМОЛОГИЯ от лат victime жертва и греч logos понятие учение область знания на стыке педагогики психологии социологии криминологии и этнографии изучающая различные категории людей жертв неблагопри...
16002. Історія вчень про державу та право 1.45 MB
  Посібник створений з урахуванням досвіду щодо подібних вітчизняних видань, а також власного напрацювання автора при викладанні навчальної дисципліни у вищих навчальних закладах. У посібнику вміщено теоретичний матеріал, перелік літератури, питання для заліку та самоконтролю знань студентів, глосарій контрольні тести-тренінги
16003. Наркоситуация в мире и транснациональный наркобизнес 316 KB
  Владивостокский центр изучения организованной преступности 2002 июль Наркоситуация в мире и транснациональный наркобизнес Реферат Тропиной Татьяны Наркобизнес – величайший массовый убийца. Исключая редкие случаи окровавленные руки п
16004. Валютное регулирование в международном инвестиционном праве 935 KB
  Валютное регулирование в международном инвестиционном праве Предисловие Разумное привлечение иностранного капитала в экономику России выгодно: иностранные инвестиции могут помочь стране быстро модернизировать промышленную базу и увеличить ее производстве...
16005. Современные международные отношения 2.56 MB
  На главную страницу ББК 6.4 С 56 Рекомендовано Учебнометодическим объединением вузов Российской Федерации по образованию в области международных отношений в качестве учебника для студентов обучающихся по специальностям Международные отношения и Реги