Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/15: Рейтинг темы: голосов - 15, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 15.11.2016
Сообщений: 23
1

Обход графа в глубину

10.12.2016, 11:17. Просмотров 2925. Ответов 1
Метки нет (Все метки)

Покажите кто-нибудь как работает "обход графа" в графе в консоле
А именно вывод глубины графа,сколько ребер обошел ,где был уже...
C++
1
2
3
4
5
6
7
8
9
10
11
vector < vector<int> > g; // граф
int n; // число вершин
 
vector<char> used;
 
void dfs (int v) {
    used[v] = true;
    for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
        if (!used[*i])
            dfs (*i);
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.12.2016, 11:17
Ответы с готовыми решениями:

Обход графа в глубину
Как сделать обход этого графа в глубину ?

Обход графа в глубину
Доброго времени суток, братцы! Есть такая задачка - обойти граф в глубину. Сам алгоритм примерно...

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

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

1
319 / 261 / 136
Регистрация: 08.04.2013
Сообщений: 1,141
10.12.2016, 13:54 2
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
/listing 1 из книги Шильд Г.
// Search for a route. 
#include <iostream> 
#include <stack> 
#include <string> 
#include <vector> 
 
using namespace std; 
  
// Flight information.  
struct FlightInfo {  
  string from;  // departure city 
  string to;    // destination city 
  int distance; // distance between from and to 
  bool skip;    // used in backtracking  
  
  FlightInfo() { 
    from = ""; 
    to = ""; 
    distance = 0; 
    skip = false; 
  } 
 
  FlightInfo(string f, string t, int d) {  
    from = f;  
    to = t;  
    distance = d;  
    skip = false;  
  }  
};  
 
// Find connections using a depth-first search.  
class Search {  
  // This vector holds the flight information.  
  vector<FlightInfo> flights; 
 
  // This statck is used for backtracking.  
  stack<FlightInfo> btStack;  
 
  // If there is a flight between from and to,  
  // store the distance of the flight in dist. 
  // Return true if the flight exists and, 
  // false otherwise. 
  bool match(string from, string to, int &dist); 
 
  // Given from, find any connection.  
  // Return true if a connection is found, 
  // and false otherwise. 
  bool find(string from, FlightInfo &f); 
 
public:  
 
  // Put flights into the database.  
  void addflight(string from, string to, int dist) {  
    flights.push_back(FlightInfo(from, to, dist));  
  }  
 
  // Show the route and total distance.  
  void route();  
 
  // Determine if there is a route between from and to.   
  void findroute(string from, string to); 
 
  // Return true if a route has been found. 
  bool routefound() { 
    return !btStack.empty(); 
  } 
};  
 
// Show the route and total distance.  
void Search::route()  
{  
  stack<FlightInfo> rev;  
  int dist = 0;  
  FlightInfo f;  
  
  // Reverse the stack to display route.  
  while(!btStack.empty()) { 
    f = btStack.top(); 
    rev.push(f); 
    btStack.pop(); 
  } 
  
  // Display the route. 
  while(!rev.empty()) { 
    f = rev.top(); 
    rev.pop();  
    cout << f.from << " to ";  
    dist += f.distance;  
  }  
  
  cout << f.to << endl;  
  cout << "Distance is " << dist << endl;  
}  
  
// If there is a flight between from and to,  
// store the distance of the flight in dist. 
// Return true if the flight exists and, 
// false otherwise. 
bool Search::match(string from, string to, int &dist)  
{  
  for(unsigned i=0; i < flights.size(); i++) {  
    if(flights[i].from == from &&  
       flights[i].to == to && !flights[i].skip)  
    {  
      flights[i].skip = true; // prevent reuse  
      dist = flights[i].distance; 
      return true; 
    }  
  }  
  
  return false; // not found   
}  
    
// Given from, find any connection.  
// Return true if a connection is found, 
// and false otherwise. 
bool Search::find(string from, FlightInfo &f)  
{  
  for(unsigned i=0; i < flights.size(); i++) {  
    if(flights[i].from == from && !flights[i].skip) {  
      f = flights[i]; 
      flights[i].skip = true; // prevent reuse  
  
      return true;  
    }  
  }  
  
  return false;  
}  
  
// Depth-first version. 
// Determine if there is a route between from and to. 
void Search::findroute(string from, string to)  
{  
  int dist;  
  FlightInfo f;  
  
  // See if at destination.  
  if(match(from, to, dist)) { 
    btStack.push(FlightInfo(from, to, dist));  
    return;  
  }  
  
  // Try another connection.  
  if(find(from, f)) { 
    btStack.push(FlightInfo(from, to, f.distance));  
    findroute(f.to, to);  
  }  
  else if(!btStack.empty()) {  
    // Backtrack and try another connection.  
    f = btStack.top(); 
    btStack.pop();  
    findroute(f.from, f.to);  
  }  
} 
 
int main() {  
  char to[40], from[40]; 
  Search ob; 
 
  // Add flight connections to database. 
  ob.addflight("New York", "Chicago", 900);  
  ob.addflight("Chicago", "Denver", 1000);  
  ob.addflight("New York", "Toronto", 500);  
  ob.addflight("New York", "Denver", 1800);  
  ob.addflight("Toronto", "Calgary", 1700);  
  ob.addflight("Toronto", "Los Angeles", 2500);  
  ob.addflight("Toronto", "Chicago", 500);  
  ob.addflight("Denver", "Urbana", 1000);  
  ob.addflight("Denver", "Houston", 1000);  
  ob.addflight("Houston", "Los Angeles", 1500);  
  ob.addflight("Denver", "Los Angeles", 1000);  
 
  // Get departure and destination cities.  
  cout << "From? ";  
 
  cin.getline(from, 40); 
  cout << "To? ";  
 
  cin.getline(to, 40); 
 
  // See if there is a route between from and to. 
  ob.findroute(from, to);  
  
  // If there is a route, show it. 
  if(ob.routefound())  
      ob.route();  
 
  return 0; 
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.12.2016, 13:54

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Многопоточный обход графа в глубину
Доброго времени суток. Подскажите многопоточный алгоритм обхода графа в глубину (нужно...

Обход вершин графа в глубину стеком
Применить стек для обхода вершин графа, заданного с помощью матрицы смежности, в глубину. Есть...

Паттерн Итератор. Обход графа в глубину
Имею данный алгоритм обхода графа в глубину. Необходимо реализовать данную задачу с помощью...

Обход графа в ширину для определения всех вершин графа, находящихся на фиксированном расстоянии от данной вершины
Реализуйте обход графа в ширину для определения всех вершин графа, находящихся на фиксированном...

Организовать обход в глубину
Искал код, не смог найти подходящий. Цель следующая - первым обходом ищем все шарниры, а вторым...

Обход в глубину(синтаксис)
#include &lt;bits/stdc++.h&gt; using namespace std; void dfs (int v) { visited = 1; ...


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

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

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