1 / 1 / 0
Регистрация: 18.02.2016
Сообщений: 71
1

Обход неориентированного графа в ширину, заданного матрицей смежности

14.11.2017, 02:15. Показов 1093. Ответов 0
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Есть вот такая программа. Она в неориентированном графе, заданным списком смежности находит и выводит все вершины, достижимые из заданной.
Как можно изменить код, чтобы делал всё тоже самое, но только чтобы граф был задан матрицей смежности?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <Windows.h>
#include <malloc.h>
#define n 100
     /*Структура вершины графа, представленного списком смежно-
сти*/
     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;
}
}
}
void 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;
          SetConsoleCP(1251);
          SetConsoleOutputCP(1251);
          printf("Введите номер вершины, с которой будет начат обход графа:\n");
 
 
     scanf("%d", &FST);
     /*Подготовка массива 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.11.2017, 02:15
Ответы с готовыми решениями:

Определить может ли матрица быть матрицей смежности простого неориентированного графа
Найдите ошибку. По заданной квадратной матрице n×n из нулей и единиц определите, может ли данная...

Обход неориентированного графа в ширину. В конце выдаёт путь: 1
#include &lt;iostream&gt; #include &lt;queue&gt; #include &lt;conio.h&gt; using namespace std; int n;// число...

Список смежности и обход графа в ширину
нужно создать список смежности и пройти граф в ширину. как с помощью struct{}; создать список...

По заданной квадратной матрице из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа
помогите решить вот такую задачу пожалуйста(( По заданной квадратной матрице n*n из нулей и единиц...

0
14.11.2017, 02:15
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.11.2017, 02:15
Помогаю со студенческими работами здесь

Обход неориентированного графа в глубину
#include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;vector&gt; #include &lt;conio.h&gt; #include &lt;locale.h&gt;...

Из матрицы инцидентности неориентированного графа сделать матрицу смежности
Помогите сделать блок схему, которая из матрицы инцидентности делает матрицу смежности Добавлено...

По заданной матрице смежности простого графа построить каркас этого графа с использованием поиска в ширину
Задание: заданно матрицу смежности простого графа. Построить каркас этого графа с использованием...

Может ли данная матрица быть матрицей смежности простого неориентированного графа
По заданной квадратной матрице n×n из нулей и единиц определите, может ли данная матрица быть...

Проверка графа, заданного матрицей смежности, на двудольность
Здравствуйте!!! Подскажите пожалуйста алгоритм, с помощью которого можно проверить граф, заданный...

Из списка смежности в матрицу смежности. Выполнить обход графа глубину
Помогите пожалуйста с программой: Дан список смежности. Преобразовать в матрицу смежности....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru