Форум программистов, компьютерный форум CyberForum.ru

Графы - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.63
White Luna
 Аватар для White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
05.12.2010, 14:30     Графы #1
Задача:
По системе односторонних дорог определить, есть ли в ней город, из которого можно добраться до каждого из остальных городов, проезжая не более 100 км.

Я думаю, что тут надо использовать ориентируемые графы.
Почитала литературу, и google но конкретно как описываются графы не нашла, подскажите кто что может, хоя бы с чего тут можно начать
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.12.2010, 14:30     Графы
Посмотрите здесь:

C++ Графы
C++ Графы
C++ [C++] графы
C++ Графы
Графы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
White Luna
 Аватар для White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
13.12.2010, 19:22  [ТС]     Графы #21
я начала как бы делать и советовалась с преподом, он сказал что готовая матр вводится как текстовый файл. и советовал использовать алгоритм Флойда-Уоршелла
Алгоритм Флойда - Уоршелла

Добавлено через 2 минуты
а можешь показать реализацию проги а то у ми после ввода данных вышибало, точнее после ввода последнего веса
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
14.12.2010, 15:17     Графы #22
Решение с помощью алгоритма Флойда-Уоршелла:

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
//////////////////////////////////////////////////////////////////////////////////////
//По системе односторонних дорог определить, есть ли в ней город, из которого 
//можно добраться до каждого из остальных городов, проезжая не более 100 км.
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <limits>
#include <map>
#include <set>
#include <string>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string                    T_str;
typedef T_str                          T_vertice;
typedef std::set<T_vertice>            T_vertices_set;
typedef std::vector<T_vertice>         T_vertices;
typedef T_vertices                     T_arc;
typedef std::set<T_arc>                T_arcs_set;
typedef int                            T_weight;
typedef std::map<T_arc, T_weight>      T_arcs_weights;
typedef std::map<T_vertice, T_weight>  T_row;
typedef T_row::value_type              T_vert_weight;
typedef std::map<T_vertice, T_row>     T_adjacency_matr;
//////////////////////////////////////////////////////////////////////////////////////
void  print_matr
    (
        const T_adjacency_matr&  matr,
        const T_weight           INFINITE_WEIGHT,
        const T_str              INFINITY_NAME
    )
{  
    for(T_adjacency_matr::const_iterator  vert_row_it = matr.begin(); 
        vert_row_it != matr.end(); ++vert_row_it)
    {
        for(T_row::const_iterator  vert_weight_it = vert_row_it->second.begin();
            vert_weight_it != vert_row_it->second.end(); ++vert_weight_it)
        {
            if(vert_weight_it->second == INFINITE_WEIGHT)
            {
                std::cout << '\t'
                          << INFINITY_NAME;
            }
            else
            {
                std::cout << '\t'
                          << vert_weight_it->second;
            }
        }
        std::cout << std::endl
                  << std::endl
                  << std::endl;
    }
}
//////////////////////////////////////////////////////////////////////////////////////
T_vertices  get_vertices(const T_arcs_set&  arcs_set)
{
    T_vertices_set  vertices_set;
    for(T_arcs_set::const_iterator  arc_it = arcs_set.begin(); arc_it != arcs_set.end();
        ++ arc_it)
    {
        vertices_set.insert(arc_it->front());
        vertices_set.insert(arc_it->back());
    }
    return T_vertices(vertices_set.begin(), vertices_set.end()); 
}
//////////////////////////////////////////////////////////////////////////////////////
T_adjacency_matr  get_adjacency_matr
    (
        const T_vertices&      vertices, 
        const T_arcs_weights&  arcs_weights,
        const T_weight         INFINITE_WEIGHT
    )
{
    T_adjacency_matr  adjacency_matr;
    for(T_vertices::const_iterator  vert_i_it = vertices.begin();
        vert_i_it != vertices.end(); ++vert_i_it)
    {
        for(T_vertices::const_iterator  vert_j_it = vertices.begin();
            vert_j_it != vertices.end(); ++vert_j_it)
        {
            adjacency_matr[*vert_i_it][*vert_j_it] = INFINITE_WEIGHT;
        }
    }
 
    for(T_arcs_weights::const_iterator   arc_weigh_it = arcs_weights.begin(); 
        arc_weigh_it != arcs_weights.end(); ++arc_weigh_it)
    {
        adjacency_matr[arc_weigh_it->first.front()]
                      [arc_weigh_it->first.back() ] = arc_weigh_it->second;
    }
    return  adjacency_matr;
}
//////////////////////////////////////////////////////////////////////////////////////
T_adjacency_matr  floyd_warshall
    (
        const T_vertices&        vertices,
        const T_adjacency_matr&  adjacency_matr,
        const T_weight           INFINITE_WEIGHT        
    )
{
    T_adjacency_matr D = adjacency_matr;
    //Обнуляем диагональные элементы.
    for(T_vertices::const_iterator  vert_i_it = vertices.begin();
        vert_i_it != vertices.end(); ++vert_i_it)
    {
        D[*vert_i_it][*vert_i_it] = T_weight();
    }
 
    for(T_vertices::const_iterator  vert_k_it = vertices.begin();
        vert_k_it != vertices.end(); ++vert_k_it)
    {
        for(T_vertices::const_iterator  vert_i_it = vertices.begin();
            vert_i_it != vertices.end(); ++vert_i_it)
        {
            for(T_vertices::const_iterator  vert_j_it = vertices.begin();
                vert_j_it != vertices.end(); ++vert_j_it)
            {
                if(   D[*vert_i_it][*vert_k_it] != INFINITE_WEIGHT
                   && D[*vert_k_it][*vert_j_it] != INFINITE_WEIGHT)
                {
                    D[*vert_i_it][*vert_j_it] 
                        = std::min(D[*vert_i_it][*vert_j_it],
                                   D[*vert_i_it][*vert_k_it] + D[*vert_k_it][*vert_j_it]);                
                }
            }        
        }    
    }
    return  D;
}
//////////////////////////////////////////////////////////////////////////////////////
void  print_vertices_distant_not_further_than
    (
        const T_weight           path_weight_max,
        const T_vertices&        vertices,
        const T_adjacency_matr&  adjacency_matr,
        const T_weight           INFINITE_WEIGHT,
        const T_str              INFINITY_NAME
    )
{    
    T_adjacency_matr  D(floyd_warshall(vertices, adjacency_matr, INFINITE_WEIGHT));    
    //Очевидно, что город, из которого можно добраться до каждого из остальных городов, 
    //проехав не более path_weight_max километров, имеет в матрице D минимальных длин путей 
    //между вершинами максимальный элемент в своей строке не больший, чем path_weight_max.
 
    T_vertices  res_vertices;
 
    struct  T_weight_compare
    {        
        bool  operator() (T_vert_weight  vert_weight_A, T_vert_weight  vert_weight_B)
        {
            return  vert_weight_A.second < vert_weight_B.second;
        }
    };
 
    for(T_adjacency_matr::const_iterator  D_vert_row_it = D.begin();
        D_vert_row_it != D.end(); ++D_vert_row_it)
    {
        T_row::const_iterator  vert_weight_max_it 
            = std::max_element(D_vert_row_it->second.begin(), D_vert_row_it->second.end(),
                               T_weight_compare());
 
        if(vert_weight_max_it->second <= path_weight_max)
        {
            res_vertices.push_back(D_vert_row_it->first);
        }    
    }
 
    std::cout << std::endl
              << "Матрица кратчайших путей межу городами:"
              << std::endl;
    print_matr(D, INFINITE_WEIGHT, INFINITY_NAME);
 
    if(res_vertices.empty())
    {
        std::cout << "В данной системе дорог нет города, из которого можно добраться "
                  << std::endl
                  << "до каждого из остальных городов, проехав не более "
                  << path_weight_max 
                  << " км."
                  << std::endl;
    }
    else
    {
        std::cout << "В данной системе дорог существует "
                  << res_vertices.size()
                  << " городов, "
                  << std::endl
                  <<"из которых можно добраться до каждого из остальных городов, "
                  << std::endl
                  << "проехав не более "
                  << path_weight_max 
                  << " км: "
                  << std::endl;    
 
        std::copy(res_vertices.begin(), res_vertices.end(), 
                  std::ostream_iterator<T_vertice>(std::cout, " "));
        std::cout << std::endl;
    }
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    int n = 0;
    do
    {
        std::cout << "Введите количество дуг ориентированного взвешенного графа > 0: ";
        std::cin >> n;
    }while(n <= 0);
 
    T_arcs_set      arcs_set;
    T_arcs_weights  arcs_weights;
    const T_weight  INFINITE_WEIGHT = std::numeric_limits<T_weight>::max();
    const T_str     INFINITY_NAME = "INF";
    std::cout << "Введите "
              << n
              << " дуг ориентированного взвешенного графа."
              << std::endl
              <<"Вершины в дуге не должны быть одинаковыми.";
    do
    {
        std::cout << std::endl
                  << "дуга #"
                  << arcs_set.size() + 1
                  << ":"
                  << std::endl
                  << '\t'
                  << "начало: ";
        T_vertice  v1;
        std::cin >> v1;
        T_arc  arc_cur;
        arc_cur.push_back(v1);
        
        T_vertice  v2;
        std::cout << '\t'
                  << "конец : ";
        std::cin >> v2;        
        arc_cur.push_back(v2);        
        if(   arc_cur.size() == 2
           && arc_cur.front() != arc_cur.back())
        {
            if(arcs_set.insert(arc_cur).second)
            {
                T_weight  arc_weight;
                do
                {
                    std::cout << '\t'
                              << '\t'
                              << "вес >= 0"                              
                              << ": ";
                    std::cin >> arc_weight;
                }while(arc_weight < 0 || INFINITE_WEIGHT <= arc_weight);
                arcs_weights[arc_cur] = arc_weight;
            }
        }        
    }while(static_cast<int>(arcs_set.size()) < n);
 
    T_vertices  vertices = get_vertices(arcs_set);
 
    T_adjacency_matr  adjacency_matr 
        = get_adjacency_matr(vertices, arcs_weights, INFINITE_WEIGHT);
 
    std::cout << std::endl
              << "Матрица смежности графа ("
              << INFINITY_NAME 
              << " означает бесконечность):"
              << std::endl;
 
    print_matr(adjacency_matr, INFINITE_WEIGHT, INFINITY_NAME);
 
    std::cout << "Вершины графа:"
              << std::endl
              << '\t';
 
    std::copy(vertices.begin(), vertices.end(), 
              std::ostream_iterator<T_vertice>(std::cout, "\t"));
    std::cout << std::endl;
    
    const T_weight  path_weight_max = 100;
    
    print_vertices_distant_not_further_than
        (
            path_weight_max,
            vertices,
            adjacency_matr,
            INFINITE_WEIGHT,
            INFINITY_NAME
        );   
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.12.2010, 17:45     Графы
Еще ссылки по теме:

Графы C++
C++ Графы
графы C++

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

Или воспользуйтесь поиском по форуму:
White Luna
 Аватар для White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
14.12.2010, 17:45  [ТС]     Графы #23
Спасибо, но все таки свое написала в итоге, кому интересно то вот тут использовала другой алгоритм форда-беллмана, т к в том тока сама запуталась больше, вот
Всем спасибо за участие
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
133
134
135
136
137
138
139
140
141
142
143
144
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include "iostream"
 
#define P 60
#define MAX 1000    //машинный эквивалент бесконечности
 
using namespace std;
 
int m[P][P];    // матрица для вычисления кратчайшего пути и его длины
int D[P], G[P][P], W[P][P],Z[P];
int N,M,S,F;
int a,b,c, w=0;
int i,j,k,l,h,f;
 
void GRAF (int m[P][P])     // функция нахождения кратчайшего пути
{        
for (i=1; i<=N; i++ )
    D[i] = m[S][i];     // массив , содержащий расстояния от заданной вершины до всех остальных 
    D[S] = 0 ;
for (j=1; j<=2 ; j++)   // матрица , хранящая путь из заданной вершины до всех остальных  
   {        
    G[j][1]=S;
    G[S][j]=0;
   }
for (h=1; h<=N; h++)    // Алгоритм Форда-Беллмана 
    {
     i=0;
    for (j=2; j<=N; j++) 
    {
     for (k=1; k<=N; k++) 
     {
      if (D[k] > D[j]+m[j][k])
        D[k]=D[j]+m[j][k];
        i++;
      for (l=2; l<=N; l++) 
      {
        W[i][l]=D[l];       // преобразуем для удобства массив расстояний в матрицу  (i-ая строка матрицы - массив расстояний на i-ом шаге )
        if (W[i][l]<W[i-1][l])      // отслеживаем улучшение пути
         G[k][2]=j;     // запоминаем вершину через которую проходит этот путь
      }
     }
    }
   }
     printf("\n");
  if (D[F]<MAX)     // если путь существует , то ...
  {                                        
    printf("\n длина пути от города %d  до остальных %d городов = \n",S,F);
    w=0;
    for(i=1; i<(F+1); i++)
     {
      cout << S;
      cout << "от";
      cout << i;
      cout << " ";
      printf("%d \n",D[i]);   // выводим длину пути 
 
      if(w<=D[i]) w=D[i];
      if (w==1000) w=D[i-1];
     }
    
    printf (" \n Максимальная длина пути от данного города = ");
if (w==1000) cout << "пути нету!!!, данный город конечный";
    else cout << w;
         cout << "\n";
if(w<=6)
{
  cout<< " \n Из города ";
  cout <<S;
  cout << "  можно! добраться до каждого из остальных городов, проезжая не более 100 км.\n";
}
   else
   {
    cout <<" \n Из города ";
    cout <<S;
    cout <<"  !!нельзя!! добраться до каждого из остальных городов, проезжая не более 100 км. \n";}
   }
 
for(int as=1; as<(F+1); as++)
 {
  printf(" \n путь между %d u %d городами  : ",S,as);
 if (D[as]<MAX)     // если путь существует , то ...
 {                                       
    i=1;
    Z[0]=as;
    while (G[as][2] !=0)    // в массив Z записываем вершины , через которые проходит путь , в обратном порядке (от конечной к начальной вершине)
    {
     Z[i]=G[as][2];
     i++;
     G[as][2]=G[G[as][2]][2];
    }
     Z[i]=S;
    for (j=i ; j>=0 ;j--)
    printf(" %d",Z[j]);     // выводим вершины , через которые проходит путь , в правильном порядке
  }
   else   // если пути нет , то ...
   {
     printf("пути нет!");                 
   };
 }
}
 
int main () 
{
 setlocale (LC_ALL, "Russian");
 char fileName[256];
  FILE *inp;
   inp=fopen("text.txt", "r");      // открываем файл на чтение
   fscanf (inp,"%d %d",&N,&M);      // Читаем из файла первую строку, cодержащую число вершин N и число ребер M
 
   for ( i=1 ; i<=N ; i++)          // присваиваем элементам обоих матриц максимальные значения 
   {
    for ( j=1 ; j<=N ; j++) 
    {
     m[i][j]=MAX;
    }
   }
   for (i=1 ;i<=M ;i++ )            // Читаем из файла остальные M строк , 
   {
    fscanf(inp,"%d %d %d",&a,&b,&c);     // содержащие описание ребер (Пример строки файла :" 1 3 6 ": значит, что ребро из вершины 1 в вершину 3 имеет вес 6)  
    m[a][b]=c;                      // Заполняем матрицу смежностей для нашего графа , учитывая вес рёбер
   }
   fclose(inp);                     // закрываем файл
    printf("\n");
   int q=1;
   do{
      for (S=1; S<=N; S++)
       {
        F=7;
        GRAF(m);
        cout << "\n";   
        }
      printf ("Хотите повторить запрос нажмите 1, выйти нажмите 0 \n");
      scanf_s ("%d", &q);
     }
   while (q==1);
 
 system ("\n pause");
 exit (0);
 getch();
 return 0 ;
}
Yandex
Объявления
14.12.2010, 17:45     Графы
Ответ Создать тему
Опции темы

Текущее время: 03:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru