На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
[!] Как относитесь к модерированию на этом форуме? Выскажите свое мнение здесь
Модераторы: Qraizer
Страницы: (4) « Первая ... 2 3 [4]  все  ( Перейти к последнему сообщению )  
> Обход графа в ширину , Обход графа в ширину
    & убери, в 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,0525 ]   [ 17 queries used ]   [ Generated: 28.03.24, 14:45 GMT ]