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;

}

}

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

Висновки

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


 

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

66616. Характеристика выпрямителя и сглаживающего фильтра блока питания ПК 5.21 MB
  Классификация источников питания СВТ В зависимости от характера преобразования энергии в источнике питания выполняемого при получении на его выходе требуемого напряжения источники питания подразделяются на: Первичные источники питания; Вторичные источники питания.
66617. Порядок проведения аудиторской проверки по основным участкам бухгалтерского учета и налогообложения хозяйственных операций 319.92 KB
  Ознакомиться с учетной политикой организации и внутренними нормативными документами изучить: организацию бухгалтерского учета; построение учетного аппарата; формы бухгалтерского учета; первичный учет и документооборот; взаимосвязь аналитического и синтетического учета.
66618. Канали QPSK з Rayleigh Fading та AWGN 804.45 KB
  Звернути увагу на сузір’я блоку Rayleigh Output та на лічильних помилкових бітів.(другий рядок в блоці Display1). Коли точки на діаграмі розміщені в відповідних квадрантах кількість помилок на змінюється. При переміщенні (повороті) діаграми...
66619. Виды АРУ приемных устройств РЛС. Работа АРУ с обратной связью 371.16 KB
  Мощность отраженного радиолокационного сигнала принимаемого от отражающего объекта, изменяется прямопропорционально четвертой степени дальности или удвоенного времени распространения энергии зондирующего радиолокационного сигнала до этого объекта.
66620. Дирижерская интерпретация музыкального произведения (генезис и эволюция) 196.5 KB
  В истории научной мысли дирижирование, как деятельность и вид музыкального исполнительства, является своеобразным «оплотом» творческого лагеря, правила и особенности существования в котором, казалось бы, не подвластны объяснению. Действительно, количество парадоксальных и взаимоисключающих явлений...
66622. ТЕНДЕНЦІЇ РОЗВИТКУ КОМП’ЮТЕРНИХ ТЕХНОЛОГІЙ В НАВЧАННІ І ВИХОВАННІ 56.73 KB
  Основною метою державної політики в галузі освіти є створення умов для розвитку особистості й творчої самореалізації кожного громадянина України, оновлення змісту освіти та організації навчально-виховного процесу відповідно до демократичних цінностей...