Государственный комитет Российской Федерации по телекоммуникациям
Сибирский государственный университет
телекоммуникаций и информатики
Лабораторная работа 5
По дисциплине « Дискретная Математика»
Поиск компонент связности графа
Работу выполнил
студент 2 курса
группы ПБТ-12
Работу проверил
Работа защищена
«___» __________2013г.
С оценкой «_______»
Новосибирск 2013
Задание. Граф задан его матрицей смежности. Требуется определить количество компонент связности этого графа. При этом должны быть конкретно перечислены вершины, входящие в каждую компоненту связности.
Выбор алгоритма поиска компонент связности – произвольный. Например, приветствуется использование одного из видов обхода.
Пользователю должна быть предоставлена возможность редактировать исходную матрицу, т. е. изменять исходный граф без выхода из программы. Предусмотреть также возможность изменения количества вершин.
Решение:
1. Описание программы:
Основными переменными являются массивы целых чисел A - хранит в себе матрицу смежности, cp – является черным списком пройденных вершин,
Основными функциями являются: newElement(), CreateMatriX(),completePoint(),searchCSS(), TopRound()
Функция searchCSS() проверяет, нужно ли обходить данную точку или нет, для выявления КСС.
Функция TopRound() обходит вершину и анализирует сколько путей от нее и сколько в нее, в соответствии с этим делает вывод о КСС.
Функция newElement () служит для ввода кол-ва вершин и проверки на ошибки, переход к созданию матрицы;
Функция CreateMatriX() организует ввод 1 и 0 в матрицу смежности и дальнейший переход к поиску в ширину;
Функция completePoint() опускает флаги в 0 и говорит о том что ни одна вершина не была пройдена, со временем массив заполнится единицами и не позволит выводить одно и то же
Вспомогательными же функциями являются: elemMatriX ()-организует проверку на правильность заполнения ячеек матрицы, Menu() – организует интерактивное меню, , matriXS – выводит на экран матрицу смежности, crossPoint – поиск самой потенциальной точки по матрице смежности.
Алгоритм решения задачи: Вводим количество n вершин, заполняем матрицу n X n элементов, далее просматриваем какая точка наиболее интересна для обхода, далее начинаем от это точки путь, постепенно записывая в out путь. При выполнении максимального количества шагов по вершинам (все послед шаги приводящие к циклу) выводим конечное выражение обхода графа. Выводим меню.;
2. Текст программы:
#include <stdio. h>
#include <conio. h>
#include <stdlib. h>
int A[20][20];
int cp[20];
void TopRound(int top, int n)
{
int I[20];
int O[20];
int b=0,i, j,k=0,q=0;
for(j=1;j<=n;j++)
{
if (A[top][j]==1 && top!=j)
{
k++;
I[k]=j;
}
if(A[j][top]==1 && j!=top)
{
q++;
O[q]=j;
}
}
printf("{");
printf("%2d",top);
i=1;j=1;
while(i<k+1 && j<q+1)
{
if(I[i]>O[j])
{
j++;
}
else if(I[i]<O[j])
{
i++;
}
else if(I[i]==O[j])
{
b=I[i];
cp[b]=1;
printf("%2d",I[i]);
i++;
j++;
}
}
printf("}\n");
}
void searchCSS(int n)
{
printf("KSS:\n");
for(int i=1;i<=n;++i)
{
if(cp[i]==0)
{
cp[i]=1;
TopRound(i, n);
}
}
}
void matriXS(int n)
{
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
if(i==0 && j==0)
{
printf(" ");
}
else
{
printf("%2d",A[i][j]);
}
}
printf("\n");
}
}
void elemMatriX(int i, int j)
{
int iac = 0;
printf("Zapolnjaem, jachejku %d-%d\n",i, j);
scanf("%d",&iac);
if (iac==0 || iac==1)
{
A[i][j]=iac;
}
else
{
printf("Zadannoe znachenie mozhet prinimat' 1 ili 0\n");
elemMatriX(i, j);
}
}
void newElement();
void Menu(void)
{
printf("\n MENU \n");
printf(" 1 - Izmenit matricu otnoshenia i kolichestvo vershin\n");
printf(" Esc - Vyhod\n");
switch (getch())
{
case 49: newElement();break;
case 27: break;
default: Menu();
}
}
void completePoint(int n)
{
for(int i=1;i<=n;++i)
{
cp[i]=0;
}
}
void CreateMatriX(int n)
{
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
if(i==0 && j==0)
{
for(int e=1;e<=n;e++)
{
A[e][0]=e;
}
}
if(i==0 && j>0)
{
A[0][j]=j;
}
if(i>0 && j>0)
{
clrscr();
matriXS(n);
printf("Martica smezhnosti\n");
elemMatriX(i, j);
}
}
}
clrscr();
matriXS(n);
printf("Matrica smezhnosti zapolnena. Nazhmite ljubuju klavishu dlja prodolzhenija\n");
completePoint(n);
getch();
searchCSS(n);
Menu();
}
void newElement()
{
int n;
printf("Vvedite n vershin\n");
scanf("%d",&n);
if(n<0)
{
printf("kolichestvo vershin ne mozhet byt' otricatel'noj ili ravnoj 0\n");
newElement();
}
else
{
CreateMatriX(n);
}
}
int main()
{
clrscr();
newElement();
getch();
}
3. Описание входных данных:
n = 6;//Количество вершин.
Заполняем матрицу смежности:
Результат:
