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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.63
White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
#1

Графы - C++

05.12.2010, 14:30. Просмотров 3584. Ответов 22
Метки нет (Все метки)

Задача:
По системе односторонних дорог определить, есть ли в ней город, из которого можно добраться до каждого из остальных городов, проезжая не более 100 км.

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

Графы - C++
помогите с реализацией алгоритма Дейкстры для нахождения расстояния от узла 1 в каждый узел. матрица весов такая...

Графы - C++
Написать программу, реализующую алгоритм Беллмана-Форда.

Графы - C++
Прочитал про обход графа в глубину, посмотрел реализацию, и тут вопрос а как можно использовать этот обход в глубину?

Графы - C++
1) Построить граф, используя язык С++ (или Си), согласно данной схеме на рис.1. 2) По запросу пользователя должны удаляться: • все...

Графы - C++
Помогите написать программу: Модель работы некоторой системы представлена ориентированным графом, где вершины – это состояния системы,...

Графы - C++
Граф задан своей матрицей смежностей. Вывести на экран все связные вершины...очень скоро нужно...извините за срочность

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
13.12.2010, 15:55  [ТС] #16
Mr.X, а проще код никак нельзя сделать?
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
13.12.2010, 17:10 #17
Цитата Сообщение от White Luna Посмотреть сообщение
Mr.X, а проще код никак нельзя сделать?
В каком смысле проще?
slice
35 / 78 / 4
Регистрация: 04.11.2010
Сообщений: 249
13.12.2010, 17:15 #18
Цитата Сообщение от Mr.X Посмотреть сообщение
В каком смысле проще?
видимо, хуже
White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
13.12.2010, 17:28  [ТС] #19
Цитата Сообщение от Mr.X Посмотреть сообщение
В каком смысле проще?
в том что, код получается оч большим, и я половину переменных понять не могу
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
13.12.2010, 19:10 #20
Цитата Сообщение от White Luna Посмотреть сообщение
в том что, код получается оч большим, и я половину переменных понять не могу
Ну я сделал программу с максимально удобным интерфейсом, где граф вводится в естественном виде. Если вводить сразу готовую матрицу смежности, то программу можно сделать гораздо короче.
А имена в программе вроде бы все самодокументируемые. Слепых однобуквенных идентификаторов я не применял.
White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
13.12.2010, 19:22  [ТС] #21
я начала как бы делать и советовалась с преподом, он сказал что готовая матр вводится как текстовый файл. и советовал использовать алгоритм Флойда-Уоршелла
Алгоритм Флойда - Уоршелла

Добавлено через 2 минуты
а можешь показать реализацию проги а то у ми после ввода данных вышибало, точнее после ввода последнего веса
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
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
        );   
}
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 ;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.12.2010, 17:45
Привет! Вот еще темы с ответами:

Графы - C++
Имеется сеть автомобильных дорог. Известны расстояния всех участков дорог. Некоторые участки аварийноопасны. Требуется найти путь из пункта...

[C++] графы - C++
Алгоритм фронт фолны в графе Помогите.. Дана матрица Ag (Матрица смежности графа) И координаты начальной вершины i,j и кординаты...

Графы - C++
Люди скиньте пожалуйста какую нибудь программку на С++ по графам, или дайте ссылку на темку на форему...

Графы - C++
Помогите пожалуйста решить одну задачку. Буду очень благодарен! Спасибо заранее, огромное! Задана строка s. За один ход можно поменять...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
14.12.2010, 17:45
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru