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;

}

}

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

Висновки

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


 

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

42717. Электронные таблицы. Построение диаграмм 237 KB
  Горизонтальная ось X ось категорий вертикальная ось Y ось значений. Горизонтальная ось X ось значений вертикальная ось Y ось категорий. они отображают зависимость данных ось Y от величины которая меняется с постоянным шагом ось Х.
42718. ОЦЕНКА ХАРАКТЕРИСТИК ПРОГРАММ НА ОСНОВЕ ЛЕКСИЧЕСКОГО АНАЛИЗА 199.5 KB
  Определить значения метрик Холстеда на основе которых дать оценку качества разработанного исходного текста программы.1 Реализация программы Текст программы для реализации возможного решения поставленной задачи разработанной с использованием языка программирования С приведен в таблице 1: Таблица 1 Текст программы для вычисления значения функции F Номер строки Строки программы 1 using System; 2 nmespce holsted 3 { 4 clss Progrm 5 { 6 sttic void Minstring[] rgs 7 { 8 double x y F; 9 chr check; 10 do 11 { 12 Console.2 Словарь программы В...
42719. Оценка характеристик программ на основе лексического анализа. Метрики 262.5 KB
  Наиболее ценным для практики является то что такая оценка может быть получена вручную на основе зрительного анализа текста программы либо автоматически с помощью специально разработанных программных анализаторов причем относительно несложных. Джилб предположил что логическая сложность должна являться значимым если не определяющим фактором для оценки стоимости программы на начальных этапах ее проектирования. Логическая сложность программы Джилб определяет как насыщенность программы условными операторами типа IFTHENELSE и...
42720. Оценка надежности программных средств 227.5 KB
  Она основана на предположении об экспоненциальной зависимости плотности вероятности интервалов времени между проявлением ошибок от интенсивности ошибок. Кроме того в модели полагается что интенсивность ошибок на каждом случайном интервале времени линейно зависит от количества оставшихся в программе ошибок. Если допустить что ошибка после ее каждого проявления устраняется и при этом в программный модуль не вносятся новые то интенсивность ошибок ti на интервале ti определяется следующим соотношением: 1 где N количество ошибок...
42721. Интерфейсы, делегаты, события 277.5 KB
  Таблица 1 Список используемых элементов управления Элемент управления Класс Описание textBox1 TextBox Окно ввода имени продавца textBox2 TextBox Окно ввода фамилии продавца textBox3 TextBox Окно ввода стажа продавца textBox4 TextBox Окно вывода списка продавцов textBox5 TextBox Окно ввода оклада продавца textBox6 TextBox Окно ввода имени менеджера textBox7 TextBox Окно ввода фамилии менеджера textBox8 TextBox Окно ввода стажа менеджера textBox9 TextBox Окно ввода оклада менеджера textBox10 TextBox Окно вывода зарплаты менеджера button1 Button...
42722. Поняття алгоритму. Блок схема запису алгоритмів 24 KB
  Мета: ознайомитись з поняттям алгоритм розглянути властивості алгоритму способи запису алгоритмів ознайомитись з правилами креслення схем алгоритму. Скласти схему алгоритму для обчислення виразу: Алгоритм последовательность действий приводящая к конкретному результату.
42723. Основы языка С# и знакомство с основными элементами управления C# 430 KB
  В C как и в C C нумерация элементов массива идет с нуля. Естественно что в нашем примере у массива 6 =23 элементов k[00] первый k[12] последний.rry Элемент Вид Описание Length Свойство Количество элементов массива по всем размерностям Rnk Свойство Количество размерностей массива BinrySerch Статический метод Двоичный поиск в отсортированном массиве Cler Статический метод Присваивание элементам массива значений по умолчанию Copy Статический метод Копирование заданного диапазона элементов одного массива в другой массив CopyTo...
42724. Исследование электрических величин двухобмоточного однофазного трансформатора 119 KB
  Исследование электрических величин двухобмоточного однофазного трансформатора. Цель работы: изучить конструкцию однофазного трансформатора описать принцип его действия замерить величины в различных режимах работы в масштабе построить характеристики и векторные диаграммы. б Коэффициент трансформации трансформатора зависит . в В режиме холостого хода с увеличением напряжения коэффициент мощности трансформатора .
42725. Методы классификации основанные на сравнении с эталоном 732 KB
  Поэтому обычно возникает необходимость сократить это число посредством выделения информативных признаков которые предполагаются инвариантными или малочувствительными по отношению к изменениям и искажениям. Результаты измерений признаков отображаются в пространство признаков. В этом случае будут установлены границы областей принятия решений для разделения признаков новых фрагментов подлежащих классификации см. Первая задача заключается в выборе подмножества признаков и их упорядочиванию в заданном множестве измерений.