Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.145.2.184] |
|
Сообщ.
#1
,
|
|
|
Ребята день добрый. Не знаю правильный ли я выбрал раздел, но напишу сюда.
Задание: используя метод поиска в ширину, найти и вывести путь в ориентированном графе между двумя вершинами. Номера начальной и конечной вершин ввести с клавиатуры. Граф задать в текстовом файле матрицей инциденций. В методичке дан лишь один пример, лишь под смежность. Работаю с Dev C++, так как он дан в методичке. Я во первых не могу понять, что нужно поправить в программе под данный тип матрицы. И собственно саму матрицу подобрать. #include <stdlib.h> #include <stdio.h> #include <conio.h> #include <Windows.h> #include <malloc.h> #define n 100 #include <locale.h> /*Структура вершины графа, представленного списком смежно- сти*/ typedef struct ListNode_ { int info; ListNode_ *next; } ListNode; bool flag [n]= {false}; ListNode *BEGIN[n]; /*Набор процедур, реализующих обход в ширину 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, int end) { 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; FILE *f = fopen ("graph.txt" , "r"); 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; int end; SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); printf("Введите номер вершины, с которой будет начат обход графа в ширину:\n"); scanf("%d", &FST); printf("Введите номер вершины, на которой будет закончен обход графа в ширину:\n"); scanf("%d", &end); /*Подготовка массива flag к использованию для поиска в ширину*/ printf("\nОбход в ширину BFS\n"); for(i=0;i<n;i++) flag[i]=false; /*Реализация поиска в ширину*/ InitQuene(); BFS(FST-1, end); getch(); for(i=0;i<n;i++) { ListNode *cuz, *tmp; cuz=BEGIN[i]; while(cuz!=NULL) { tmp=cuz; cuz=cuz->next; free(tmp); } } return 0; } |
Сообщ.
#2
,
|
|
|
1.В функции DeQuene() явно что-то не так, ибо на одной строке память выделяете, а на следующей же забиваете на неё; забываете адрес.
2.Функцию IsEmptyQuene() можно сократить до "bool IsEmptyQuene() { return EndQuene==NULL; }" |
Сообщ.
#3
,
|
|
|
Славян код из методического пособия.... Как мне быть......
|
Сообщ.
#4
,
|
|
|
П.С. это вы так случайно попутали букву u на n в слове "очередь"=Queue, или сознательно исказили слово?..
|
Сообщ.
#5
,
|
|
|
Код из методического пособия, ничего не правил.
|
Сообщ.
#6
,
|
|
|
Собственно, если DeQuene() удаляет узел, то её код должен быть каким-то таким:
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; } |
Сообщ.
#7
,
|
|
|
Алгоритм мне подсказали, но я никогда не делал такое и вообще бы не додумался бы до преобразования матриц.
Как преобразовать, могу подсказать алгоритм: 1. Начнем перебирать столбцы, j=1..M 1.1. Начнем перебирать все элементы столбца, i=1..N 1.1.1. Если очередной элемент столбца равен 1 - зафиксируем начало ребра. Т.е. если a[i][j] = 1, то x = i; 1.1.2. Если очередной элемент столбца равен -1 - зафиксируем конец ребра, т.е. если a[i][j] = -1, то y = i; 1.2 Добавим ребро (x, y) в матрицу смежности, т.е. ADJ[x][y] = TRUE Здесь a - матрица инциденций, размером NxM ADJ - матрица смежности, размером NxN Кто нибудь поймет что нужно сделать? |
Сообщ.
#8
,
|
|
|
Цитата tdmods @ В методичке дан лишь один пример, лишь под смежность. В методичке ведь не сказано "делать по примеру", верно? Таким образом, есть постановка задачи, и есть требование к результату. Первым делом читаем матчасть. Далее прогаем: Если есть методика, отличная от указанной в вики, и именно она требуется к исполнению - пересматриваем все три пункта под нее. Да, методика (читай алгоритм решения) будет иная, но методология та же. |
Сообщ.
#9
,
|
|
|
#include <stdlib.h> #include <stdio.h> #include <conio.h> #include <Windows.h> #include <malloc.h> #include <locale.h> #include <fstream> #define n 100 using namespace std; /*Структура вершины графа, представленного списком смежности*/ typedef struct ListNode_ { int info; ListNode_ *next; } ListNode; bool flag [n]= {false}; ListNode *BEGIN[n]; /*Набор процедур, реализующих обход в ширину 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; // размеры матрицы инцидентности std::ifstream ifs("graph.txt"); // размеры я бы указал в файле первыми двумя значениями ifs >> M >> N; // выделяем память под 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++) ifs >> 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; int end; SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); printf("Введите номер вершины, с которой будет начат обход графа в ширину:\n"); scanf("%d", &FST); printf("Введите номер вершины, на которой будет закончен обход графа в ширину:\n"); scanf("%d", &end); /*Подготовка массива flag к использованию для поиска в ширину*/ printf("\nОбход в ширину BFS\n"); for(i=0;i<n;i++) flag[i]=false; /*Реализация поиска в ширину*/ InitQuene(); BFS(FST-1); getch(); for(i=0;i<n;i++) { ListNode *cuz, *tmp; cuz=BEGIN[i]; while(cuz!=NULL) { tmp=cuz; cuz=cuz->next; free(tmp); } } return 0; } Ребята подскажите мне пожалуйста вот что 'f' was not declared in this scope, как это поправить, на что нужно f заменить? |
Сообщ.
#10
,
|
|
|
Быть может нужно строку
std::ifstream ifs("graph.txt"); заменнить на FILE *f=fopen("graph.txt","rt"); ну и прочие строки с ifs поправить. |
Сообщ.
#11
,
|
|
|
Славян можете дать код как правильно поправить, чтобы все работало? Я только начинаю свою работу с C++ и многое мне в новинку.
|
Сообщ.
#12
,
|
|
|
У вас просто весьма странное поведение: я же написал, что в строке память выделяется, а потом сразу на неё (память) вы плюёте, а вы, тем не менее, всё равно оставили то место без изменения. Почему же так? Т.е. почему вы не правите ошибки или не отвечаете на своё видение ситуации?
Смысла в полном коде весьма мало; гораздо интереснее двигаться шагами, исправляя проблемы и находя какие-то пути их обхода. |
Сообщ.
#13
,
|
|
|
Славян поправил я это место, в итоге еще одна НОВАЯ ошибка, мне сейчас важнее со сменой указателя разобраться. Можете мне хотя бы направление дать?
|
Сообщ.
#14
,
|
|
|
Пока не сильно ясно про какую смену указателя речь. Не сложно же - вставляйте имеющийся код (не руками же набираете) и будем смотреть на проблемы! :yes:
Добавлено П.С. хм... что-то не догоняю, отчего yes в конце смайликом не рисуется?.. :-? Добавлено О, и эта эмоция (с вопросиком) тоже. Что-то где-то поломалось... |
Сообщ.
#15
,
|
|
|
Славян мне нужно:
1) либо на что то заменить "f" 2) либо убрать std; нужно чтобы программа заработала и выполняла задание выше.... |
Сообщ.
#16
,
|
|
|
Ну я и написал, что можно по-старинке слепить FILE *f; И дальше уже с ним работать, благо все примеры в коде у вас есть. Меняйте, компилируйте и выкладывайте куски с непонятными/трудными проблемами. Так пока трудно угадать, где ещё у вас сложности.
|
Сообщ.
#17
,
|
|
|
ifs >> incidenceMatrix[row][column]; на что это поменять, чтобы код работал?
|
Сообщ.
#18
,
|
|
|
На scanf( f, "%d", &incidenceMatrix[row][column]);
Добавлено Ой, на fscanf. |
Сообщ.
#19
,
|
|
|
Славян ошибка компиляции в этой строке cannot convert 'FILE {aka _iobuf}' to 'const char*' for argument '1' to 'int scanf(const char*, ...)'
|
Сообщ.
#20
,
|
|
|
Ну да, ибо надо fscanf.
|
Сообщ.
#21
,
|
|
|
Славян собралось, сейчас погоняю.
|
Сообщ.
#22
,
|
|
|
Вылет при начале работы, приложил файлом так как кодировка бьется
Матрица: 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) |
Сообщ.
#23
,
|
|
|
Без обид, но я шибко ленюсь скачивать, так что пусть с кривой кодировкой, но забросьте код в сообщение, если не сверхсложно, а?..
|
Сообщ.
#24
,
|
|
|
#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; } |
Сообщ.
#25
,
|
|
|
Странно всё это. Пишете, что поправили то место, а сейчас же в коде и строки есть: p=malloc(...); p = A; Зачем неправду писать?
|
Сообщ.
#26
,
|
|
|
#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; } Извиняюсь, но все равно программа вылетает. |
Сообщ.
#27
,
|
|
|
Цитата tdmods @ Извиняюсь, но все равно программа вылетает А где ты M и N присваиваешь? Там после fopen, наверное должен быть fscanf для них |
Сообщ.
#28
,
|
|
|
tdmods, пишете, что "adjacencyMatrix - матрица инцидентности размерами MxN", а память выделяете для MxM (в main'е).
|
Сообщ.
#29
,
|
|
|
Славян можете ткнуть носом в кусок кода?
bool **adjacencyMatrix = new bool*[M]; как я понял речь про вот это? Если я правильно понял: bool **incidenceMatrix; incidenceMatrix[column] = new bool*[M]; incidenceMatrix[row] = new int[N]; Еще и fscanf добавить. |
Сообщ.
#30
,
|
|
|
Не, чутка неправильно. Речь же про 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; } |
Сообщ.
#31
,
|
|
|
Цитата tdmods @ bool **adjacencyMatrix = new bool*[M]; как я понял речь про вот это? Здесь у тебя вроде все правильно, во всяком случае технически. У тебя переменным M N не присвоены значения, проверь чему они равны. Добавлено Цитата Славян @ Как-то так, видимо Смотои ниже, как у него используется adjacencyMatrix |
Сообщ.
#32
,
|
|
|
Используется, насколько я понял, как MxM. Ну тогда надо лишь комментарий поправить:
// adjacencyMatrix - матрица инцидентности размерами MxM Добавлено Блин, не понимаю, что (в Опере?)сломалось: в своём сообщении №33 смайлик рисовался. Поправил букву N на M и перестал рисоваться. Буковки пишутся. :wall: П.С. wall тоже, небось не нарисуется. |
Сообщ.
#33
,
|
|
|
Так вылета нет, я поправил. Теперь бы большую матрицу бы придумать, и проверку на максимальное количество добавить. Есть какой онлайн конструктор графов?
Добавлено #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"); fscanf(f,"%u",&M); fscanf(f,"%w",&N); // выделяем память под 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; } блин похоже не корректно выводит, можете погонять на разных наборах? Выводит что то, но что? |
Сообщ.
#34
,
|
|
|
Цитата tdmods @ fscanf(f,"%w",&N); Что такое "%w"? Здесь, наверное, "%d" должен быть. Да и для M тоже - они у тебя оба int объявлены |
Сообщ.
#35
,
|
|
|
Олег Месли ставлю %d, то вылет программы...
|
Сообщ.
#36
,
|
|
|
Цитата tdmods @ Олег Месли ставлю %d, то вылет программы... Сделай после fscanf(f,"%u",&M); fscanf(f,"%w",&N); - prinf("M=%d, N=%d\n", M, N); и посмотри, что там возвращается |
Сообщ.
#37
,
|
|
|
Олег М смысла в этом нет, так как туда он не доходит. Рушится в самом начале.
|
Сообщ.
#38
,
|
|
|
Вообще, судя по всему, тебе там надо делать fscanf("%d %d\n", &M, &N);
Добавлено Цитата tdmods @ Олег М смысла в этом нет, так как туда он не доходит. Рушится в самом начале. В каком начале? Поставь в каждой строчке в начале prinf("%d\n", __LINE__) и посмотри, которая последняя исполнится |
Сообщ.
#39
,
|
|
|
FILE *f=fopen("graph.txt","r");
fscanf(f,"%d %d\n", &M, &N); Тоже рушит программу сразу после старта, ничего не выводит, хотя попробую. И еще нужна матрица побольше, где взять ХЗ. |
Сообщ.
#40
,
|
|
|
Цитата tdmods @ Тоже рушит программу сразу после старта, ничего не выводит, хотя попробую. Нашёл строчку, которая последняя исполнилась? И покажи код |
Сообщ.
#41
,
|
|
|
Олег М
Вроде все таки перестало вылетать, такое чувство что из за того, что матрицу меняю вылет. #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,M, N; // размеры матрицы инцидентности SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); FILE *f=fopen("graph.txt","r"); fscanf(f,"%d %d\n", &M, &N); // выделяем память под 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; } Но теперь после обход в ширину ничего не выводит, а прежний код выводил. |
Сообщ.
#42
,
|
|
|
Цитата tdmods @ Вроде все таки перестало вылетать, такое чувство что из за того, что матрицу меняю вылет. Ты выведи на экран то что ты начитал из файлов - переменные M и N и матрицы incidenceMatrix и adjacencyMatrix. Это для начала. А то так долго можно гадать, что именно не работает. |
Сообщ.
#43
,
|
|
|
Олег М ни черта не ясно мне.
4321318 6553180 int i,j,M, N; // размеры матрицы инцидентности SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); FILE *f=fopen("graph.txt","r"); fscanf(f,"%d %d\n", &M, &N); printf("%d %d\n"); Выводить не ясно что. |
Сообщ.
#44
,
|
|
|
Цитата tdmods @ Олег М ни черта не ясно мне. 4321318 6553180 Ты там забыл добавить M, N в printf |
Сообщ.
#45
,
|
|
|
FILE *f=fopen("graph.txt","r");
fscanf(f,"%d %d\n", &M, &N); printf("%d %d\n", &M, &N); 6553180 6553176 Введите номер вершины, с которой будет начат обход графа в ширину: |
Сообщ.
#46
,
|
|
|
& убери, в printf
|
Сообщ.
#47
,
|
|
|
Олег Мвывело 4 и 5 как и должно быть. Что дальше.
|
Сообщ.
#48
,
|
|
|
Уже лучше. Теперь выведи содержимое матриц
|
Сообщ.
#49
,
|
|
|
А как вывод то матрицы указать?
|
Сообщ.
#50
,
|
|
|
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]); printf("%d ", incidenceMatrix[row][column]) } printf("\n") } |
Сообщ.
#51
,
|
|
|
Олег М
#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,M, N, column, row; // ðàçìåðû ìàòðèöû èíöèäåíòíîñòè SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); FILE *f=fopen("graph.txt","r"); fscanf(f,"%d %d\n", &M, &N); printf("%d %d\n", M, N); // âûäåëÿåì ïàìÿòü ïîä M ñòðîê äëÿ ìàòðèöû èíöèäåíòîñòè int **incidenceMatrix = new int*[M]; for (row = 0; row < M; row++) { // äëÿ êàæäîé ñòðîêè âûäåëÿåì ïàìÿòü ïîä N ýëåìåíòîâ incidenceMatrix[row] = new int[N]; // ñ÷èòûâàåì çíà÷åíèÿ for (column = 0; column < N; column++) { fscanf(f, "%d", &incidenceMatrix[row][column]); printf("%d ", incidenceMatrix[row][column]); } } // adjacencyMatrix - ìàòðèöà èíöèäåíòíîñòè ðàçìåðàìè MxN // âûäåëÿåì ïàìÿòü äëÿ ìàòðèöû ñìåæíîñòè bool **adjacencyMatrix = new bool*[M]; for (row = 0; row < M; row++) { adjacencyMatrix[row] = new bool[M]; for (column = 0; column < M; column++) { adjacencyMatrix[row][column] = false; printf("%d ", adjacencyMatrix[row][column]); } } // çàïîëíÿåì ìàòðèöó ñìåæíîñòè çíà÷åíèÿìè // ïðîõîäèìñÿ ïî êàæäîìó ñòîëáöó for (column = 0; column < N; column++) { // èíäåêñû îòêóäà è êóäà int from = -1, to = -1; // èùåì ñòðîêó, ãäå áóäåò óêàçàíà èíôîðìàöèÿ îòêóäà (1) è êóäà (-1) for (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; } Похоже, что преобразование не проходит: видно лишь исходную матрицу, а смежность нет Добавлено 4 5 1 0 0 -1 0 -1 1 0 0 -1 0 0 1 1 1 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Введите номер вершины, с которой будет начат обход графа в ширину: Добавлено Похоже попутаны списки смежности и матрица смежности. Добавлено #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, int end) { EnQuene(cur); flag[cur] = true; while (IsEmptyQuene() != true) { cur = DeQuene(); ListNode *List = BEGIN[cur]; while (List != NULL) { if (flag[List->info] == false && cur < end) { EnQuene(List->info); flag[List->info] = true; printf("%d-%d\n", cur + 1, List->info + 1); } List = List->next; } } } int main() { int i,j,M, N, column, row; // ðàçìåðû ìàòðèöû èíöèäåíòíîñòè SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); FILE *f=fopen("graph.txt","rt"); fscanf(f,"%d %d\n", &M, &N); //printf("%d %d\n", M, N); // âûäåëÿåì ïàìÿòü ïîä M ñòðîê äëÿ ìàòðèöû èíöèäåíòîñòè int **incidenceMatrix = new int*[M]; for (row = 0; row < M; row++) { // äëÿ êàæäîé ñòðîêè âûäåëÿåì ïàìÿòü ïîä N ýëåìåíòîâ incidenceMatrix[row] = new int[N]; // ñ÷èòûâàåì çíà÷åíèÿ for (column = 0; column < N; column++) fscanf(f, "%d", &incidenceMatrix[row][column]); //printf("%d ", incidenceMatrix[row][column]); } // adjacencyMatrix - ìàòðèöà èíöèäåíòíîñòè ðàçìåðàìè MxN // âûäåëÿåì ïàìÿòü äëÿ ìàòðèöû ñìåæíîñòè bool **adjacencyMatrix = new bool*[M]; for (row = 0; row < M; row++) { adjacencyMatrix[row] = new bool[M]; for (column = 0; column < M; column++) adjacencyMatrix[row][column] = false; } // çàïîëíÿåì ìàòðèöó ñìåæíîñòè çíà÷åíèÿìè // ïðîõîäèìñÿ ïî êàæäîìó ñòîëáöó for (column = 0; column < N; column++) { // èíäåêñû îòêóäà è êóäà int from = -1, to = -1; // èùåì ñòðîêó, ãäå áóäåò óêàçàíà èíôîðìàöèÿ îòêóäà (1) è êóäà (-1) for (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); int End; printf("Ââåäèòå íîìåð âåðøèíû, íà êîòîðîé áóäåò çàâåðøåí îáõîä ãðàôà â øèðèíó:\n"); scanf("%d", &End); /*Ïîäãîòîâêà ìàññèâà flag ê èñïîëüçîâàíèþ äëÿ ïîèñêà â øèðèíó*/ printf("\nÎáõîä â øèðèíó BFS\n"); for(i=0;i<u;i++) flag[i]=false; /*Ðåàëèçàöèÿ ïîèñêà â øèðèíó*/ InitQuene(); BFS(FST-1,End); 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; } Добавил проверку на каком элементе закончить. |
Сообщ.
#52
,
|
|
|
Цитата tdmods @ for(i = 0 ; !feof(f); i++) { int n1; fscanf(f,"%d",&n1);/*ñ÷èòûâàåì êîëè÷åñòâî âåðøèí, ñìåæíûõ ñ i-é âåðøèíîé*/ for(j=0;j<n1;j++) А это что? Ты ж вроде уже весь файл вычитал в матрицу. |
Сообщ.
#53
,
|
|
|
Олег Мсчитывает количество смежных вершин
Добавлено Блин а оно же тут из файла пишется... вот и |
Сообщ.
#54
,
|
|
|
Цитата tdmods @ Что-то вас не поймёшь: то исправляете эту ошибку, то снова её пишете. Как же в итоге? p=(QueneNode *) malloc(sizeof(QueneNode)); p=BeginQuene; |
Сообщ.
#55
,
|
|
|
#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, int end) { EnQuene(cur); flag[cur] = true; while (IsEmptyQuene() != true) { cur = DeQuene(); ListNode *List = BEGIN[cur]; while (List != NULL) { if (flag[List->info] == false && cur < end) { EnQuene(List->info); flag[List->info] = true; printf("%d-%d\n", cur + 1, List->info + 1); } List = List->next; } } } int main() { int i,j,M, N, column, row; // размеры матрицы инцидентности SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); FILE *f=fopen("graph.txt","rt"); fscanf(f,"%d %d\n", &M, &N); //printf("%d %d\n", M, N); // выделяем память под M строк для матрицы инцидентости int **incidenceMatrix = new int*[M]; for (row = 0; row < M; row++) { // для каждой строки выделяем память под N элементов incidenceMatrix[row] = new int[N]; // считываем значения for (column = 0; column < N; column++) fscanf(f, "%d", &incidenceMatrix[row][column]); //printf("%d ", incidenceMatrix[row][column]); } // adjacencyMatrix - матрица инцидентности размерами MxN // выделяем память для матрицы смежности bool **adjacencyMatrix = new bool*[M]; for (row = 0; row < M; row++) { adjacencyMatrix[row] = new bool[M]; for (column = 0; column < M; column++) adjacencyMatrix[row][column] = false; } // заполняем матрицу смежности значениями // проходимся по каждому столбцу for (column = 0; column < N; column++) { // индексы откуда и куда int from = -1, to = -1; // ищем строку, где будет указана информация откуда (1) и куда (-1) for (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; for(j=0;j<4;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); int End; printf("Введите номер вершины, на которой будет завершен обход графа в ширину:\n"); scanf("%d", &End); /*Подготовка массива flag к использованию для поиска в ширину*/ printf("\nОбход в ширину BFS\n"); for(i=0;i<u;i++) flag[i]=false; /*Реализация поиска в ширину*/ InitQuene(); BFS(FST-1,End); 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; } |
Сообщ.
#56
,
|
|
|
А ты зачем adjacencyMatrix строил, если нигде её потом не используешь? Насколько я понимаю, именно по ней путь и ищется
|
Сообщ.
#57
,
|
|
|
Олег М вот и ответ. Как ее вписать?
Добавлено for(i = 0 ;i< adjacencyMatrix [row]; 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; } } Как я понял нужно править вот этот кусок. Как? |
Сообщ.
#58
,
|
|
|
"Беглым взглядом вижу, что преобразование Вы закончили. Теперь, используя эту матрицу нужно решать. Как дальше делать - также как и со старой, только меняется порядок вершин. Если раньше все были в списке смежные. То теперь для конкретной вершины cur нужно просмотреть все смежные, to, и если есть ребро cur->to, то добавляем to в очередь и т.д."
Как это реализовать? |