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;

}

}

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

Висновки

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


 

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

8738. Общественный прогресс. Критерии прогресса 46.5 KB
  Общественный прогресс. Критерии прогресса 1 вариант. Прогресс - направление развития, для которого характерно поступательное движение общества от низших и простых форм общественной организации к более высоким и сложным. Регресс - обратное движение...
8739. Общество и научно-технический прогресс 37.5 KB
  Общество и научно-технический прогресс Вариант 1 Современное состояние научно - технического прогресса определяется понятием научно-технической революции. Научно-техническая революция (НТР)- это качественный скачок в развитии производительных с...
8740. Развитие знаний об обществе. Общественные науки 32 KB
  Развитие знаний об обществе. Общественные науки (социология, политология, культурология, история, религиоведение, экономика, обществознание и др.) Вариант 1 Этапы развития знаний об обществе. Познание общества в форме мифологического сознания ...
8741. Обществознание в средние века и в новое время 29 KB
  Обществознание в средние века и в новое время Вариант К анализу тенденций общественного развития, а также критике негативных сторон государственности обращается в своем теологическом трактате О граде божьем средневековый богослов Августин Блаженн...
8742. Обществознание XX века 39.5 KB
  Вариант 1 Обществознание XX века: Теория ценностей Макса Вебера (в происхождении капитализма решающая роль протестантизма) Технократизм Уолта Ростоу (теория стадий экономического развития: традиционная переходящая стадия сдвига...
8743. Цивилизации и формации 32.5 KB
  Вариант 1 Цивилизации и формации Наиболее разработанные в исторической и философской науках подходы к объяснению сущности исторического процесса - формационный и цивилизационный подходы. Первый из них принадлежит к марксистской (коммунистическо...
8744. Традиционное и индустриальное общества 39 KB
  Вариант 1 Традиционное и индустриальное общества Традиционное общество (Восток) Индустриальное общество (Запад). Непрерывность исторического процесса, отсутствие явных граней между эпохами, резких сдвигов и скачков. История движется неравном...
8745. Цивилизации Древнего Востока (речные) 46 KB
  Цивилизации Древнего Востока (речные) Египет - IV тыс. до н.э. (империя - 3200-525г. до н.э.) Месопотамия - III тыс. до н.э. (Вавилонская империя - 3000 – 538 г. до н.э.) Индия - III - II тыс. до н.э. (XVIII век д...
8746. Древнегреческая цивилизация (морская) 52 KB
  Древнегреческая цивилизация (морская) Основные понятия: морские цивилизации, колонии, полис, гражданская община, автаркия, тирания, олигархия, демократия, натуральное хозяйство, товарно-денежные отношения, эллинизм, мировая империя. Особенности ра...