XIV Международная студенческая научная конференция Студенческий научный форум - 2022

Целью работы является изучение основных структур данных, использующихся для хранения графов, и разработка программы, преобразующей одни структуры в другие на примере «Матрица смежности  Список ребер». Будет разработан алгоритм преобразования исходной структуры данных хранения графа в выходную структуру данных, а также программная реализация разработанного алгоритма.

Для графа, представленного на рис. 1, матрица инцидентности показана в таблице 1

Рисунок 1. - Пример графа Таблица 1. Матрица смежности графа
	0	1	0	0
	0	0	1	1
	0	0	0	1
	1	0	0	0

За один шаг просмотра можно ответить, существует ли ребро из х в y.

Независимо от количества ребер объем требуемой памяти равен n2.

Еще один способ хранения графов – это список ребер, то есть список, в котором перечислены все ребра графа. Список ребер графа, представленного на рис. 1, приведен на рис. 2.

Рисунок 2. – Список ребер графа

Алгоритм преобразования матрицы смежности в cписок ребер представлен блок-схемой на рис. 3

Рисунок 3. – Алгоритм преобразования матрицы смежности в список ребер

Листинг программы :

#include <iostream>

#include <cstdlib>

#include <list>

using namespace std;

struct ListOfRibs

{

int start,

end,

weight;

};

int main()

{

int n, m;

cout <<" Enter size array N x M"<< endl<<"N = ";

cin >> n;

cout <<"M = ";

cin >> m;

int** ar = newint* [n];

for (int i = 0; i < n; i++)

{

ar[i] = newint[m];

}

bool f;

cout <<"f = 0, manual input"<< endl<<"f != 0, avotomacly input"<< endl<<"f = ";

cin >> f;

if (!f) {

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++) {

cout <<"ar["<< i <<"]["<< j <<"] = ";

cin >> ar[i][j];

}

}

else {

srand(0);

for (int i = 0; i < n; i++) {

cout << endl;

for (int j = 0; j < m; j++) {

ar[i][j] = rand() % 10;

cout << ar[i][j] <<"\t";

}

}

cout <<"\n\n";

}

list <ListOfRibs> listOfRibs;

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

if (ar[i][j])

{

ListOfRibs inp;

inp.end = j;

inp.start = i;

inp.weight = ar[i][j];

listOfRibs.push_back(inp);

}

for (auto iter = listOfRibs.begin(); iter != listOfRibs.end(); iter++)

{

cout <<"Start = "<< iter->start;

cout <<",\t end = "<< iter->end;

cout <<",\t weight = "<< iter->weight << endl;

}

}

Пример работы программы приведен на рис.4.

Рисунок 4. – Пример работы программы

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

Окулов, С. М. Основы программирования /Окулов С. М. М.: БИНОМ. Лаборатория знаний, 2012. 340С.

Черноухов С.А. Вектор смежности и ассоциативный массив смежности как способы представления и хранения графов / S.A. Chernouhov. Adjacency vector and adjacency map as data structures to represent a graph // Сборник статей Международной научно-практической конференции «Проблемы внедрения результатов инновационных разработок и пути их решения» – Стерлитамак: АМИ, 2019, с. 65-69

Код для цитирования: Скопировать