Реализация основных операций над графами, представленных в виде матриц смежностей (стр. 5 из 5)
{
for(int j=0;j<vertexNumber;j++)
{
graph[i][n]=-1;
graph[n][j]=-1;
}
}
}
else
{
for(int i=0;i<vertexNumber;i++)
{
for(int j=0;j<vertexNumber;j++)
{
graph[i][n]=0;
graph[n][j]=0;
}
}
}
}
void MatrixGraph::PrintMatrix()
{
for(int i=0; i<=vertexNumber; i++)
{
cout.width(3);
if(i==0){cout<<" "; i++;}
cout<<"X"<<i;
}
cout<<endl<<endl;
for(int i=0;i<vertexNumber;i++)
{
cout.width(4);
cout<<"X"<<i+1;
for(int j=0;j<vertexNumber;j++)
{
cout.width(4);
if(graph[i][j]==-1)
{
cout<<"#";
}
else
{
cout<<graph[i][j];
}
}
cout<<endl<<endl;
}
}
void MatrixGraph::addArc(int from,int to)
{
if(from<0||from>=vertexNumber||to<0||to>=vertexNumber)
return;
graph[from][to]=1;
}
void MatrixGraph::deleteArc(int from,int to)
{
if(from<0||from>=vertexNumber||to<0||to>=vertexNumber)
return;
graph[from][to]=0;
}
int MatrixGraph::hasArc(int from,int to)
{
if(from<0||from>=vertexNumber||to<0||to>=vertexNumber)
return false;
return graph[from][to];
}
void MatrixGraph::ComplementGraph()
{
for(int i=0;i<vertexNumber;i++)
{
for(int j=0;j<vertexNumber;j++)
{
if(graph[i][j]==0)
{
graph[i][j]=1;
}
else
{
if(graph[i][j]==1)
{
graph[i][j]=0;
}
}
}
}
for(int i=0;i<vertexNumber;i++)
{
for(int j=0;j<vertexNumber;j++)
{
if(i==j)
{
graph[i][j]=0;
}
}
}
}
void MatrixGraph:: ShowUnion(MatrixGraph a)
{
int max,min;
a.Size()>vertexNumber ? max=a.Size():max=vertexNumber;
a.Size()<vertexNumber? min=a.Size():min=vertexNumber;
MatrixGraph c(max);
for(int i=0;i<max;i++)
{
for(int j=0;j<max;j++)
{
if(a.hasArc(i,j)==1|| hasArc(i,j)==1)
{c.addArc(i,j); }
}
}
c.PrintMatrix();
}
Файл «Kursach.cpp»
#include "stdafx.h"
#include<windows.h>
#include<iostream>
#include"MatrixGraph.h"
using namespace std;
void main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
MatrixGraph a(6),b(6);
a.addArc(0,1);
a.addArc(1,2);
a.addArc(1,4);
a.addArc(2,3);
a.addArc(3,2);
a.addArc(4,0);
cout<<"Матрица А."<<endl;
a.PrintMatrix();
b.addArc(0,1);
b.addArc(1,4);
b.addArc(4,0);
b.addArc(4,3);
cout<<"Матрица B."<<endl;
b.PrintMatrix();
int n,from,to,vertex;
do
{
cout.width(3);
cout<<"///////////////////////////////////////\n";
cout<<"// 1.Добавить дугу в матрицу А. //\n";
cout<<"// 2.Удалить дугу из матрицы А. //\n";
cout<<"// 3.Добавить дугу в матрицу B. //\n";
cout<<"// 4.Удалить дугу из матрицы B. //\n";
cout<<"// 5.Добавить вершину в матрицу А. //\n";
cout<<"// 6.Удалить вершину из матрицы A. //\n";
cout<<"// 7.Вывод объединения А и B. //\n";
cout<<"// 8.Вывод дополнения А. //\n";
cout<<"// 9.Выход... //\n";
cout<<"///////////////////////////////////////\n";
cin>>n;
switch(n)
{
case 1:cout<<"Ведите вершины.\n";
cin>>from>>to;
from--;to--;
a.addArc(from,to);
a.PrintMatrix();break;
case 2:cout<<"Ведите вершины.\n";
cin>>from>>to;
from--;to--;
a.deleteArc(from,to);
a.PrintMatrix();break;
case 3:cout<<"Ведите вершины.\n";
cin>>from>>to;
from--;to--;
b.addArc(from,to);
b.PrintMatrix();break;
case 4:
cout<<"Ведите вершины.\n";
cin>>from>>to;
from--;to--;
b.deleteArc(from,to);
b.PrintMatrix();break;
case 5:cout<<"Ведите вершину.\n";
cin>>vertex;
//vertex--;
a.addNode(vertex);
a.PrintMatrix();break;
case 6:cout<<"Ведите вершину.\n";
cin>>vertex;
vertex--;
a.deleteNode(vertex,true);
a.PrintMatrix();break;
case 7:a.ShowUnion(b);break;
case 8:a.ComplementGraph();
a.PrintMatrix();
case 9:cout<<"Выход...\n";break;
default: cout<<"Попробуйте еще\n";
}
}while(n!=9);
}
ПРИЛОЖЕНИЕ В.
Результаты тестирования.Рисунок B5–Вывод матрицы А , B и операций над графами.
Рисунок B6–Вывод выполнение операции добавление дуги.
а) б)
с)
Рисунок B7–Вывод выполнение операции удаление и добавление вершины матрицы.
Рисунок B8–Вывод выполнение операции объединение А и В.
Рисунок B9–Вывод выполнение операции дополнение А .
Рисунок B10–Вывод выполнение операции удаление дуги.
Рисунок В11– Выход из меню.
Список литературы:
1. Лафоре Р. Oобъектно-ориентированное программирование в С++. Классика Computer Science. 4-ое изд. /Р.Лафоре–СПб.: Питер, 2004.-924с.:ил.
2. Герберт Шилдт. С++ руководство для начинающих. 2-ое издание. / Пер. с англ. — М. : Издатель-ский дом "Вильяме", 2005. — 672 с. : ил. — Парал. тит. англ.
3. Герберт Шилдт. Полный справочник по С++, 4-е издание. . Пер. с англ. — М. : Издательский дом "Вильяме", 2006. — 800 с. : ил. — Парал. тит. англ.
15ВЫ 5-8459-0489-7 (рус.)
4.Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4