Обход графа в ширину , Обход графа в ширину

[Славян]

Ну я и написал, что можно по-старинке слепить FILE *f; И дальше уже с ним работать, благо все примеры в коде у вас есть. Меняйте, компилируйте и выкладывайте куски с непонятными/трудными проблемами. Так пока трудно угадать, где ещё у вас сложности.

[tdmods]

ifs >> incidenceMatrix[row][column]; на что это поменять, чтобы код работал?

[Славян]

На scanf( f, "%d", &incidenceMatrix[row][column]);

Добавлено 14.05.17, 10:14
Ой, на fscanf.

[tdmods]

Славян ошибка компиляции в этой строке cannot convert 'FILE {aka _iobuf}' to 'const char*' for argument '1' to 'int scanf(const char*, ...)'

[Славян]

Ну да, ибо надо fscanf.

[tdmods]

Славян собралось, сейчас погоняю.

[tdmods]

Вылет при начале работы, приложил файлом так как кодировка бьется

Матрица:

4 5
1 0 0 - 1 0
-1 1 0 0 -1
0 0 1 1 1
0 -1 -1 0 0
Прикреплённый файлgraph.cpp (3,63 Кбайт, скачиваний: 148)

[Славян]

Без обид, но я шибко ленюсь скачивать, так что пусть с кривой кодировкой, но забросьте код в сообщение, если не сверхсложно, а?..

[tdmods]

#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;
}

[Славян]

Странно всё это. Пишете, что поправили то место, а сейчас же в коде и строки есть: p=malloc(...); p = A; Зачем неправду писать?

[tdmods]

#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;
  if( !BeginQuene ) return -666; // пусто, нечего удалять
  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()
{
SetConsoleTitleW(L"Lab2");
setlocale(LC_ALL, "russian");
int i,j,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;
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;
}

Извиняюсь, но все равно программа вылетает.

Сообщение отредактировано: tdmods - 14.05.17, 14:52

[Олег М]

Цитата tdmods @ 14.05.17, 14:44

Извиняюсь, но все равно программа вылетает

А где ты M и N присваиваешь? Там после fopen, наверное должен быть fscanf для них

[Славян]

tdmods, пишете, что "adjacencyMatrix - матрица инцидентности размерами MxN", а память выделяете для MxM (в main'е).

[tdmods]

Славян можете ткнуть носом в кусок кода?

bool **adjacencyMatrix = new bool*[M];

как я понял речь про вот это?

Если я правильно понял:

bool **incidenceMatrix;

incidenceMatrix[column] = new bool*[M];
incidenceMatrix[row] = new int[N];

Еще и fscanf добавить.

[Славян]

Не, чутка неправильно. Речь же про adjacencyMatrix, а не про incidenceMatrix.
Как-то так, видимо:

// adjacencyMatrix - матрица инцидентности размерами MxN
// выделяем память для матрицы смежности
bool **adjacencyMatrix = new bool*[M];
for (int row = 0; row < M; row++)
{
  adjacencyMatrix[row] = new bool[N];
  for( int column = 0; column < N; column++)
    adjacencyMatrix[row][column] = false;
}