Алгоритм поиска в глубину

#include <fstream>
#include <stack>
#include <vector>
#include <iostream>
#include <clocale>
#define N 10
using namespace std;
 
void designing(int* , int, int, ofstream&); // êîíñòðóèðîâàíèå ìàðøðóòà
 
int main()
{
    setlocale(LC_ALL, "Russian");
    ofstream o("result.txt");
    ifstream in("A.txt");
    if (!in) return 1;
    // ------------------------------èíèöèàëèçàöèÿ------------------------------
    stack <int> st; // ñòåê äëÿ õðàíåíèÿ íîìåðîâ âåðøèí
    bool visited[N]; //false - âåðøèíà íå ðàññìîòðåíà, true - ðàññìîòðåíà
    bool instack[N]; //false - âåðøèíà íå â ñòåêå, true - â ñòåêå
    bool DUG[N][N]; // ìàòðèöà ñìåæíîñòè
    int start, end; // íîìåð ñòàðòîâîé è êîíå÷íîé âåðøèí
    int rang[N]; // äëèíà ïóòè
    int VON_PUNKT[N]; // íîìåð âåðøèíû, èç êîòîðîé ïîïàëè â òåêóùóþ
    cout<< "Ââåäèòå íà÷àëüíóþ âåðøèíó: ";
    do{ cin>> start;} while (start < 0 || start > 9);
    cout<< "Ââåäèòå êîíå÷íóþ âåðøèíó: ";
    do{ cin>> end;} while (end < 0 || end > 9 || end == start);
    for (int i = 0; i < N; i++)
    {
        VON_PUNKT[i] = start;
        rang[i] = 999;
        visited[i] = instack[i] = false;
        for (int j = 0; j < N; j++)
            in>> DUG[i][j];
    }
    // çàïèñûâàåì íà÷àëüíóþ âåðøèíó â î÷åðåäü
    st.push (start);
    visited[start] = instack[start] = true;
    VON_PUNKT[start] = -1;
    rang[start] = 0;
    // --------------------------------îáùèé øàã--------------------------------
    while (!st.empty())
    {
          int besuch = st.top();
          visited[besuch] = true;
          st.pop();
          for (int i = 0; i < N; i++)
          {
              if (!instack[i] && DUG[besuch][i])
              {
                  st.push (i);
                  instack[i] = true;
                  rang[i] = rang[besuch] + 1;
                  VON_PUNKT[i] = besuch;
              }
          }
    }
    // --------------------------çàïèñü ïóòè â ôàéë ----------------------------
    designing(VON_PUNKT, rang[end], end, o);
    in.close();  o.close();
    return 0;
}
 
void designing(int *p, int rang, int end, ofstream &o)
{
    vector <int> v;
    vector <int>::iterator cur;    
    for (int i = end; i != -1; i = p[i])
        v.push_back(i);
    o<< "Êîëè÷åñòâî ïåðåõîäîâ: "<< rang<< endl;
    for (cur = v.end() - 1; cur >= v.begin(); cur--)
        o<< *cur<< " ";
}

//  Поиск маршрута.
#include <iostream>
#include <strack>
#include <string>
#include <vector>
 
using namespace std;
 
// Информация о рейсе.
struct FlightInfo {
string from;  // пункт отправления
string to;  // пункт назначения
int distance;  // расстояние от и до…
bool skip;  // используется при возврате или откате
 
FlightInfo() {
from = “ ”;
to = “ ”;
distance = 0;
skip = false;
}
FlightInfo(string f, string t, int d) {
from = f;
to = t;
distance = d;
skip = false;
}
};
 
// Поиск маршрутов между городами с помощью поиска в глубину.
class Search {
//  Этот вектор содержит информацию о рейсах.
vector<FlidgtInfo> flights;
 
//Этот стек используется для возврата.
stask<FlightInfo> btStack;
 
// Если есть рейс от from и to,
// то в dist запоминается расстояние.
// Возвращает true, если рейс существует, и
// false – в противном случае.
bool match(string from, string to, int &dist);
 
// При заданном from ищет любой прямой рейс (соединение).
// Возвращает true, если рейс найден,
// и false – в противном случае.
bool find(string from, FightInfo &f);
public:
 
// Помещает рейсы в базу данных.
void addflight (string from, string to, int dist) {
flights.push_back(FlightInfo(from, to, dish));
}
 
// Показывает маршрут и общее расстояние.
void route();
 
//Опредиляет, есть ли маршрут между from и to.
void findroute(string from, string to);
 
// Возвращает trueб если маршрут был найден.
bool routefound() {
return !btStack.empty();
}
};
 
//Отображает маршрут и его длину.
void Search::route()
}
stack<FlightInfo> rev;
int dish = 0;
FlightInfo f;
 
//Для отображения маршрута меняет порядок стека на противоположный.
while(!btStack.empty()) {
f = btStack.top();
rev.push(f);
btStack.pop();
}
 
//Отображает маршрут.
while(!rev.empty()) {
f = rev.top();
rev.pop();
cout << f.from << “ to “;
dist += f.distance;
}
 
cout << f.to << endl;
cout << “Distance is “ << dist << endl;
}
 
// Если существует прямой рейс между from и to, 
// запоминает длину рейста в dist.
// Возвращает true, если рейс сществует, и
// false – в противном случае.
bool Search::match(string from, string to, int &dist)
{
for(unsigned i=0; i < flights[i].skip)
{
}
 
return false; // не найден
}
 
//Для заданного from находит любой прямой рейс.
//Возвращает true, если рейс найден, и 
// false – в противном случае.
bool Search::find(string from, FlinghtInfo &f)
{
for(unsigned i=0; i < flights.size(); i++) {
if(flights[i].skip = true; // препятствует повторному использованию
 
return true;
}
}
 
return false;
}
 
// Способ поиска в глубину.
// Определяет, есть ли маршрут между from и to.
void Search::findroute(string from, string to)
{
int dist;
FlightInfo f;
 
// Проверяет, не достигнута ли цель.
if(match(from, to, dist)) {
btStack.push(FlightInfo(from, to, dist));
return;
}
 
// Пробует другой маршрут.
if(find(from. f)) {
btStack.push(FlightInfo(from, to, f.distance));
findroute(f.to, to);
}
else if(!btStack.empty()) {
// Поднимается на уровень вверх и пробует другой маршрут.
f = btStack.top();
btStack.pop();
findroute(f.from, f.to);
}
}
 
int main() {
char to[40], from[40];
Search ob;
 
// Добавлет рейсы в бау данных.
ob.addflight(“New York”, “Chicago”, 900);
ob.addflight(“Chicago”, “Denever”, 1000);
ob.addflight(“New York”, “Toronto”, 500);
ob.addflight(“New York”, “Denever”, 1800);
ob.addflight(“Toronto”, “Calgary”, 1700);
ob.addflight(“Toronto”, “Los Angeles”, 2500);
ob.addflight(“Toronto”, “Chicago”, 500);
ob.addflight(“Denever”, “Urbana”, 1000);
ob.addflight(“Denever”, “Houston”, 1000);
ob.addflight(“Houston”, “Los Angeles”, 1500);
ob.addflight(“Denever”, “Los Angeles”, 1000);
 
// Получает пункты отправления и назначения.
cout << “From? “;
 
cin.getline(from, 40);
cout << “To? “;
 
cin.getline(to, 40);
 
// Проверяет есть ли маршрут между from и to.
ob.findroute(from, to);
 
// Если маршрут существует, отображает его.
if(ob.routefound())
ob.route();
 
return 0;
}