#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <Windows.h>
#include <malloc.h>
#include <locale.h>
//#include <fstream>
#define u 100
//using namespace std;
/*Структура вершины графа, представленного списком смежности*/
typedef struct ListNode_
{
int info;
ListNode_ *next;
} ListNode;
bool flag [u]= {false};
ListNode *BEGIN[u];
/*Набор процедур, реализующих обход в ширину BFS*/
struct QueneNode
{
int info;
QueneNode *next;
};
QueneNode *BeginQuene;
QueneNode *EndQuene;
void InitQuene()
{
BeginQuene=NULL;
EndQuene=NULL;
}
void EnQuene(int x)//занесение в очередь
{
QueneNode *p;
p=(QueneNode *) malloc(sizeof(QueneNode));
p->info=x;
p->next=NULL;
if(BeginQuene==NULL)
BeginQuene=p;
else EndQuene->next=p;
EndQuene=p;
}
int DeQuene()
{
int val;
QueneNode *p;
p=(QueneNode *) malloc(sizeof(QueneNode));
p=BeginQuene;
val=BeginQuene->info;
BeginQuene=p->next;
if(BeginQuene==NULL)
EndQuene=NULL;
free(p);
return val;
}
bool IsEmptyQuene()
{
if(EndQuene==NULL)
return true;
else return false;
}
void BFS(int cur)
{
EnQuene(cur);
flag[cur] = true;
while (IsEmptyQuene() != true)
{
cur = DeQuene();
ListNode *List = BEGIN[cur];
while (List != NULL)
{
if (flag[List->info] == false)
{
EnQuene(List->info);
flag[List->info] = true;
printf("%d-%d\n", cur + 1, List->info + 1);
}
List = List->next;
}
}
}
int main()
{	
int i,j;
int M, N; // размеры матрицы инцидентности
FILE *f=fopen("graph.txt","r");
// выделяем память под M строк для матрицы инцидентости
int **incidenceMatrix = new int*[M];
for (int row = 0; row < M; row++)
{
// для каждой строки выделяем память под N элементов
incidenceMatrix[row] = new int[N];
// считываем значения
for (int column = 0; column < N; column++)
fscanf(f, "%d", &incidenceMatrix[row][column]);
}
// adjacencyMatrix - матрица инцидентности размерами MxN
// выделяем память для матрицы смежности
bool **adjacencyMatrix = new bool*[M];
for (int row = 0; row < M; row++)
{
adjacencyMatrix[row] = new bool[M];
for (int column = 0; column < M; column++)
adjacencyMatrix[row][column] = false;
}
// заполняем матрицу смежности значениями
// проходимся по каждому столбцу
for (int column = 0; column < N; column++)
{
// индексы откуда и куда
int from = -1, to = -1;
// ищем строку, где будет указана информация откуда (1) и куда (-1)
for (int row = 0; row < M && (from == -1 || to == -1); row++)
{
if (incidenceMatrix[row][column] == 1)
from = row;
else if (incidenceMatrix[row][column] == -1)
to = row;
}
// помечаем переход в матрице смежности
adjacencyMatrix[from][to] = true;
}
for(i = 0 ; !feof(f);  i++)
{
int n1;
fscanf(f,"%d",&n1);/*считываем количество вершин, смежных с i-й вершиной*/
for(j=0;j<n1;j++)
{
int a;
fscanf(f,"%d",&a);/*считываем номер очередной j-й вершины, смежной с вершиной i */
ListNode *cuz= (ListNode*) malloc(
sizeof(ListNode));
cuz->info=a-1;/*заносим в поле info списка значение номера j-й смежной вершины на 1 меньше ее реального номера, так как в массиве вершин нумерация элементов начинается с 0, а не с 1, как нумеруются вершины графа */
cuz->next=BEGIN[i];
BEGIN[i]=cuz;
}
}
fclose(f);
int FST;
SetConsoleTitleW(L"Lab2");
setlocale(LC_ALL, "russian");
printf("Введите номер вершины, с которой будет начат обход графа в ширину:\n");
scanf("%d", &FST);
/*Подготовка массива flag к использованию для поиска в ширину*/
printf("\nОбход в ширину BFS\n");
for(i=0;i<u;i++) flag[i]=false;
/*Реализация поиска в ширину*/
InitQuene();
BFS(FST-1);
getch();
for(i=0;i<u;i++)
{
ListNode *cuz, *tmp;
cuz=BEGIN[i];
while(cuz!=NULL)
{
tmp=cuz;
cuz=cuz->next;
free(tmp);
}
}
return 0;
}