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;

}

}

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

Висновки

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


 

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

82595. Система дошкольного образования 139.5 KB
  Система дошкольного образования Республики Беларусь обеспечивает реализацию конституционного права родителей на образование ребенка при первом же обращении их в органы образования. Каждой семье, каждому ребенку предоставляются возможности в получении качественного дошкольного образования...
82596. Основные течения философии ХIХ в. (позитивизм, марксизм, философия жизни, феноменология) 40.49 KB
  Философия XIX века включает различные философские течения и школы в том числе: романтизм и идеализм на подъеме немецкой философии противоположное движение позитивизм во Франции и Англии материализм Маркса и Фейербаха философия отдельных великих мыслителей Шопенгауэр Ницше Кьеркегор неокантианство...
82597. Щелочные полевые шпаты. Плагиоклазы. Бариевые полевые шпаты 99.5 KB
  Можно с уверенностью сказать что полевые шпаты являются наиболее изученными минералами и все важнейшие этапы развития минералогии и петрографии связаны с их исследованием. Полевые шпаты широко используются в керамической промышленности как наполнители лёгкие абразивы например в производстве...
82598. АНАЛІЗ БАЛАНСУ АПТЕКИ ТА ЙОГО СТРУКТУРИ 64.8 KB
  Самофінансування здійснюється за рахунок прибутку й амортизації. У процесi нагромадження обсяг прибутку піддається зменшенню за рахунок податків і різних платежів із прибутку. В остаточному підсумку залишається нерерозподілений прибуток.
82599. «Великая депрессия»: характер и причины возникновения. Новый курс Рузвельта 43.29 KB
  Важнейшей разделительной вехой в истории США XX в., как и в американской истории в целом, стал 1933 г. Краткое различие между двумя эпохами американской истории, разделенными этой датой, можно охарактеризовать следующим образом.
82600. КОРПОРАТИВНАЯ ЭТИКА. ЮРИДИЧЕСКАЯ И СОЦИАЛЬНАЯ ОТВЕТСТВЕННОСТЬ ФИРМЫ 46.54 KB
  Деловой этикет порядок поведения работников компании включающий систему регламентированных правил поведения в различных деловых ситуациях в том числе при деловой переписке деловом общении приеме на работу обращении к руководству и т.д.
82601. Основы управления персоналом 83.5 KB
  На основе внутренней мотивации люди действуют спокойнее быстрее добросовестнее тратят меньше сил лучше усваивают задания и знания. Добиться желаемого поведения можно двумя путями: подобрать человека с заданным уровнем внутренней мотивации или воспользоваться внешней.
82602. Роль кардинала Ришельє в історії Франції 144.5 KB
  Бажаючи досягти абсолютної влади, Ришельє вступає на шлях придушення будь-якого опору, обмеження привілеїв окремих міст і провінцій і, врешті-решт, знищення противників. Ришельє проводить цю політику від імені Людовика XIII. При цьому сходження Ришельє на політичний олімп було важким і болісним.
82603. Педагогічні умови розвитку ораторських здібностей 108.5 KB
  Основні аспекти розвитку ораторських здібностей молодших школярів. Педагогічні умови розвитку ораторських здібностей. Засоби практичного розвитку ораторських здібностей. Психологопедагогічна робота з розвитку ораторських здібностей...