Целью работы является изучение основных структур данных, использующихся для хранения графов, и разработка программы, преобразующей одни структуры в другие на примере «Матрица смежности Список ребер». Будет разработан алгоритм преобразования исходной структуры данных хранения графа в выходную структуру данных, а также программная реализация разработанного алгоритма.
Для графа, представленного на рис. 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