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

    В методичке дан лишь один пример, лишь под смежность. Работаю с 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;

                                нужно чтобы программа заработала и выполняла задание выше....
                                  Ну я и написал, что можно по-старинке слепить FILE *f; И дальше уже с ним работать, благо все примеры в коде у вас есть. Меняйте, компилируйте и выкладывайте куски с непонятными/трудными проблемами. Так пока трудно угадать, где ещё у вас сложности.
                                    ifs >> incidenceMatrix[row][column]; на что это поменять, чтобы код работал?
                                      На scanf( f, "%d", &incidenceMatrix[row][column]);

                                      Добавлено
                                      Ой, на fscanf. :blush:
                                        Славян ошибка компиляции в этой строке cannot convert 'FILE {aka _iobuf}' to 'const char*' for argument '1' to 'int scanf(const char*, ...)'
                                          Ну да, ибо надо fscanf.8-)
                                            Славян собралось, сейчас погоняю.
                                              Вылет при начале работы, приложил файлом так как кодировка бьется

                                              Матрица:

                                              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)
                                                Без обид, но я шибко ленюсь скачивать, так что пусть с кривой кодировкой, но забросьте код в сообщение, если не сверхсложно, а?.. :oops:
                                                  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;
                                                    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; Зачем неправду писать? :-?
                                                      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");
                                                        // выделяем память под 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 @
                                                        Извиняюсь, но все равно программа вылетает

                                                        А где ты M и N присваиваешь? Там после fopen, наверное должен быть fscanf для них
                                                          tdmods, пишете, что "adjacencyMatrix - матрица инцидентности размерами MxN", а память выделяете для MxM (в main'е). :yes-sad:
                                                            Славян можете ткнуть носом в кусок кода?

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

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

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

                                                            bool **incidenceMatrix;

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

                                                            Еще и fscanf добавить.
                                                              Не, чутка неправильно. Речь же про adjacencyMatrix, а не про incidenceMatrix.
                                                              Как-то так, видимо:
                                                              ExpandedWrap disabled
                                                                // 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;
                                                                }
                                                                Цитата 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
                                                                                            Введите номер вершины, с которой будет начат обход графа в ширину:
                                                                                              & убери, в printf
                                                                                                Олег Мвывело 4 и 5 как и должно быть. Что дальше.
                                                                                                  Уже лучше. Теперь выведи содержимое матриц
                                                                                                    А как вывод то матрицы указать?
                                                                                                      ExpandedWrap disabled
                                                                                                        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")
                                                                                                        }
                                                                                                      Сообщение отредактировано: Олег М -
                                                                                                        Олег М
                                                                                                        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, 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 Введите номер вершины, с которой будет начат обход графа в ширину:

                                                                                                        Добавлено
                                                                                                        Похоже попутаны списки смежности и матрица смежности.

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


                                                                                                        Добавил проверку на каком элементе закончить.
                                                                                                        Сообщение отредактировано: tdmods -
                                                                                                          Цитата tdmods @
                                                                                                          for(i = 0 ; !feof(f);  i++)
                                                                                                          {
                                                                                                          int n1;
                                                                                                          fscanf(f,"%d",&n1);/*ñ÷èòûâàåì êîëè÷åñòâî âåðøèí, ñìåæíûõ ñ i-é âåðøèíîé*/
                                                                                                          for(j=0;j<n1;j++)


                                                                                                          А это что? Ты ж вроде уже весь файл вычитал в матрицу.
                                                                                                            Олег Мсчитывает количество смежных вершин

                                                                                                            Добавлено
                                                                                                            Блин а оно же тут из файла пишется... вот и
                                                                                                              Цитата tdmods @
                                                                                                              ExpandedWrap disabled
                                                                                                                p=(QueneNode *) malloc(sizeof(QueneNode));
                                                                                                                p=BeginQuene;
                                                                                                              Что-то вас не поймёшь: то исправляете эту ошибку, то снова её пишете. Как же в итоге?
                                                                                                                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, 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;
                                                                                                                  }
                                                                                                                Сообщение отредактировано: tdmods -
                                                                                                                  А ты зачем adjacencyMatrix строил, если нигде её потом не используешь? Насколько я понимаю, именно по ней путь и ищется
                                                                                                                    Олег М вот и ответ. Как ее вписать?

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


                                                                                                                    Как я понял нужно править вот этот кусок. Как?
                                                                                                                      "Беглым взглядом вижу, что преобразование Вы закончили. Теперь, используя эту матрицу нужно решать. Как дальше делать - также как и со старой, только меняется порядок вершин. Если раньше все были в списке смежные. То теперь для конкретной вершины cur нужно просмотреть все смежные, to, и если есть ребро cur->to, то добавляем to в очередь и т.д."

                                                                                                                      Как это реализовать?
                                                                                                                      0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                                                                                                      0 пользователей:


                                                                                                                      Рейтинг@Mail.ru
                                                                                                                      [ Script execution time: 0,1571 ]   [ 19 queries used ]   [ Generated: 28.03.24, 08:41 GMT ]