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;

}

}

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

Висновки

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


 

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

81275. Право и политика 37.71 KB
  Мицкевич зародилось и понятие политики как общественного светского института выражавшего общие дела интересы полиса городагосударства типичного для государственности Древней Греции и Рима . Поэтому политики не существовало в первобытном обществе где даже индивид не отделял свои интересы от интересов родовой общины. Государство главный политик центральный субъект политической жизни и политической организации любого общества: если все другие субъекты политики политические партии профсоюзы отдельные политики и др. выражают...
81276. Право и экономика 36.48 KB
  Определяющую роль в сфере экономики играют отношения собственности. В марксистской теории соотношение права и экономики трактуется исходя из общих закономерностей связи базиса экономической структуры общества экономического строя которая складывается независимо от воли и сознания людей и надстройки идеологических отношений и институтов. В то же время Маркс и Энгельс не рассматривали определяющее значение экономики по отношению к праву прямолинейно не упрощали его: учитывалось влияние на право других факторов других частей...
81277. Право и мораль. Единство права и морали 38.26 KB
  Соотношение между правом и моралью сложное оно включает в себя четыре компонента: единство различие взаимодействие и противоречия. Единство права и морали состоит в том что: право и мораль представляют собой разновидности социальных норм образующих в совокупности целостную систему нормативного регулирования и в силу этого обладают некоторыми общими чертами у них единая нормативная основа; право и мораль преследуют в конечном счете одни и те же цели и задачи упорядочение и совершенствование общественной жизни внесение в нее...
81278. Формы (источники) права 38.83 KB
  Наряду с этим источником права следует также признать форму выражения государственной воли форму в которой содержится правовое решение государства. Обычно в теории называют четыре вида источников права: нормативный акт судебный прецедент санкционированный обычай и договор. В отдельные исторические периоды источниками права признавали правосознание правовую идеологию а также деятельность юристов.
81279. Нормативно-правовой акт: понятие, виды 39.43 KB
  Нормативные акты создаются в основном государственными органами имеющими право принимать нормативные решения по тем вопросам которые переданы им для разрешения. Нормативные акты характеризуются следующими признаками. Нормативные акты это носители хранилища жилища правовых норм из них мы черпаем знания о правовых нормах. 2 Нормативные акты должны издаваться только в пределах компетенции правотворческого органа иначе по одному и тому же вопросу в государстве будет существовать несколько нормативных решений между которыми возможны...
81280. Норма права: Понятие, структура, классификация. Способы изложения норм права в нормативно-правовых актах 41.26 KB
  Нормы права это правило поведения имеющее обязательный характер и поддерживаемое силой государственного принуждения. Внутренняя определенность нормы проявляется в содержании объеме прав и обязанностей четких указаниях на последствия ее нарушения. Она обладает качеством системности которое проявляется в структурном построении нормы в специализации и кооперации норм различных отраслей и институтов права. Структура нормы права объединяет три элемента: гипотезу диспозицию и санкцию.
81281. Система права и система законодательства 36.02 KB
  Система права как его содержание это внутренняя структура права соответствующая характеру регулируемых им общественных отношений. Система законодательства внешняя форма права выражающая строение его источников т. Структура права носит объективный характер и обусловлена экономическим базисом общества.
81282. Типология правовых систем 38.05 KB
  При классификации правовых систем используют различные факторы начиная с этических расовых географических религиозных и заканчивая юридической техникой и стилем права. Она основана на сочетании двух критериев: идеологии включающей религию философию экономические и социальные структуры и юридической техники включающей в качестве основной составляющей источники права. Основным признаком этой правовой семьи является ее формирование на основе римского права. Решающая роль в становлении ее принадлежала средневековым университетам Европы...
81283. Публичное и частное право. Материальное и процессуальное право. Международное и национальное право 41.33 KB
  Материальное и процессуальное право. Международное и национальное право. Основное деление всего права есть деление его на право публичное и частное или гражданское.