На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
[!] Как относитесь к модерированию на этом форуме? Выскажите свое мнение здесь
Модераторы: Qraizer
Страницы: (4) [1] 2 3 ... Последняя » все  ( Перейти к последнему сообщению )  
> Обход графа в ширину , Обход графа в ширину
    Ребята день добрый. Не знаю правильный ли я выбрал раздел, но напишу сюда.
    Задание: используя метод поиска в ширину, найти и вывести путь в ориентированном графе между двумя вершинами. Номера начальной и конечной вершин ввести с клавиатуры. Граф задать в текстовом файле матрицей инциденций.

    В методичке дан лишь один пример, лишь под смежность. Работаю с Dev C++, так как он дан в методичке.

    Я во первых не могу понять, что нужно поправить в программе под данный тип матрицы. И собственно саму матрицу подобрать.
    ExpandedWrap disabled
      #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;
      }
      1.В функции DeQuene() явно что-то не так, ибо на одной строке память выделяете, а на следующей же забиваете на неё; забываете адрес.
      2.Функцию IsEmptyQuene() можно сократить до "bool IsEmptyQuene() { return EndQuene==NULL; }"
        Славян код из методического пособия.... Как мне быть......
          П.С. это вы так случайно попутали букву u на n в слове "очередь"=Queue, или сознательно исказили слово?.. :D
            Код из методического пособия, ничего не правил.
              Собственно, если DeQuene() удаляет узел, то её код должен быть каким-то таким:
              ExpandedWrap disabled
                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;
                }
                Алгоритм мне подсказали, но я никогда не делал такое и вообще бы не додумался бы до преобразования матриц.

                Как преобразовать, могу подсказать алгоритм:
                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

                Кто нибудь поймет что нужно сделать?
                  Цитата tdmods @
                  В методичке дан лишь один пример, лишь под смежность.

                  В методичке ведь не сказано "делать по примеру", верно? Таким образом, есть постановка задачи, и есть требование к результату. Первым делом читаем матчасть.

                  Далее прогаем:
                  1. Объявляем граф в терминах задания (в предлагаемом виде)
                  2. Создаем класс, в котором реализуем методы получения данных, которые требует алгоритм, указанный выше
                  3. Создаем метод, реализуемый алгоритмом, указанным выше

                  Если есть методика, отличная от указанной в вики, и именно она требуется к исполнению - пересматриваем все три пункта под нее. Да, методика (читай алгоритм решения) будет иная, но методология та же.
                    ExpandedWrap disabled
                      #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 заменить?
                      Быть может нужно строку
                      ExpandedWrap disabled
                        std::ifstream ifs("graph.txt");

                      заменнить на
                      ExpandedWrap disabled
                        FILE *f=fopen("graph.txt","rt");

                      ну и прочие строки с ifs поправить.
                        Славян можете дать код как правильно поправить, чтобы все работало? Я только начинаю свою работу с C++ и многое мне в новинку.
                          У вас просто весьма странное поведение: я же написал, что в строке память выделяется, а потом сразу на неё (память) вы плюёте, а вы, тем не менее, всё равно оставили то место без изменения. Почему же так? Т.е. почему вы не правите ошибки или не отвечаете на своё видение ситуации?:-?
                          Смысла в полном коде весьма мало; гораздо интереснее двигаться шагами, исправляя проблемы и находя какие-то пути их обхода.;)
                            Славян поправил я это место, в итоге еще одна НОВАЯ ошибка, мне сейчас важнее со сменой указателя разобраться. Можете мне хотя бы направление дать?
                            Сообщение отредактировано: tdmods -
                              Пока не сильно ясно про какую смену указателя речь. Не сложно же - вставляйте имеющийся код (не руками же набираете) и будем смотреть на проблемы! :yes:

                              Добавлено
                              П.С. хм... что-то не догоняю, отчего yes в конце смайликом не рисуется?.. :-?

                              Добавлено
                              О, и эта эмоция (с вопросиком) тоже. Что-то где-то поломалось...
                              Сообщение отредактировано: Славян -
                                Славян мне нужно:

                                1) либо на что то заменить "f"
                                2) либо убрать std;

                                нужно чтобы программа заработала и выполняла задание выше....
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0393 ]   [ 17 queries used ]   [ Generated: 28.03.24, 20:06 GMT ]