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

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

    Здесь у тебя вроде все правильно, во всяком случае технически.
    У тебя переменным M N не присвоены значения, проверь чему они равны.

    Добавлено
    Цитата Славян @
    Как-то так, видимо

    Смотои ниже, как у него используется adjacencyMatrix
      Используется, насколько я понял, как MxM. Ну тогда надо лишь комментарий поправить:
      ExpandedWrap disabled
        // adjacencyMatrix - матрица инцидентности размерами MxM
      :oops:

      Добавлено
      Блин, не понимаю, что (в Опере?)сломалось: в своём сообщении №33 смайлик рисовался. Поправил букву N на M и перестал рисоваться. Буковки пишутся. :wall:
      П.С. wall тоже, небось не нарисуется.
      Сообщение отредактировано: Славян -
        Так вылета нет, я поправил. Теперь бы большую матрицу бы придумать, и проверку на максимальное количество добавить. Есть какой онлайн конструктор графов?

        Добавлено
        ExpandedWrap disabled
          #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;
          }

        блин похоже не корректно выводит, можете погонять на разных наборах? Выводит что то, но что?
        Сообщение отредактировано: tdmods -
          Цитата tdmods @
          fscanf(f,"%w",&N);

          Что такое "%w"? Здесь, наверное, "%d" должен быть. Да и для M тоже - они у тебя оба int объявлены
            Олег Месли ставлю %d, то вылет программы...
              Цитата tdmods @
              Олег Месли ставлю %d, то вылет программы...

              Сделай после fscanf(f,"%u",&M); fscanf(f,"%w",&N); - prinf("M=%d, N=%d\n", M, N);
              и посмотри, что там возвращается
                Олег М смысла в этом нет, так как туда он не доходит. Рушится в самом начале.
                  Вообще, судя по всему, тебе там надо делать fscanf("%d %d\n", &M, &N);

                  Добавлено
                  Цитата tdmods @
                  Олег М смысла в этом нет, так как туда он не доходит. Рушится в самом начале.

                  В каком начале?
                  Поставь в каждой строчке в начале prinf("%d\n", __LINE__) и посмотри, которая последняя исполнится
                    FILE *f=fopen("graph.txt","r");
                    fscanf(f,"%d %d\n", &M, &N);

                    Тоже рушит программу сразу после старта, ничего не выводит, хотя попробую. И еще нужна матрица побольше, где взять ХЗ.
                    Сообщение отредактировано: tdmods -
                      Цитата tdmods @
                      Тоже рушит программу сразу после старта, ничего не выводит, хотя попробую.

                      Нашёл строчку, которая последняя исполнилась? И покажи код
                        Олег М

                        Вроде все таки перестало вылетать, такое чувство что из за того, что матрицу меняю вылет.

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


                        Но теперь после обход в ширину ничего не выводит, а прежний код выводил.
                          Цитата tdmods @
                          Вроде все таки перестало вылетать, такое чувство что из за того, что матрицу меняю вылет.

                          Ты выведи на экран то что ты начитал из файлов - переменные M и N и матрицы incidenceMatrix и adjacencyMatrix. Это для начала. А то так долго можно гадать, что именно не работает.
                            Олег М ни черта не ясно мне.

                            4321318 6553180
                            ExpandedWrap disabled
                              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");


                            Выводить не ясно что.
                            Сообщение отредактировано: tdmods -
                              Цитата tdmods @
                              Олег М ни черта не ясно мне.

                              4321318 6553180

                              Ты там забыл добавить M, N в printf
                                FILE *f=fopen("graph.txt","r");
                                fscanf(f,"%d %d\n", &M, &N);
                                printf("%d %d\n", &M, &N);

                                6553180 6553176
                                Введите номер вершины, с которой будет начат обход графа в ширину:
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (4) 1 2 [3] 4  все


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0488 ]   [ 17 queries used ]   [ Generated: 29.03.24, 10:54 GMT ]