Перевод с Pascal на C++ - Turbo Pascal - Ответ 13561335

#include <iostream>
#include <ctime>
#include <vector>
#include <conio.h>
 
using namespace std;
 
const int n = 5;
int i, j;
//матрица смежности графа
int GM[n][n] =
{
    { 0,1,0,0,1 },
{ 1,0,1,0,0 },
{ 0,1,0,1,0 },
{ 0,0,1,0,1 },
{ 1,0,0,1,0 }
};
vector < vector <int> > g(n);
vector <int> used(n); //массив меток. в начале его нужно заполнить 0.
vector <int> tin, tout; //время входа и выхода для каждой вершины.
 
bool *visited = new bool[n];
//поиск в ширину(Breadth - first search, BFS)
void BFS(bool *passed, int unit)
{
    //очередь
    int *queue = new int[n];
    //указатели очереди
    int count, head;
    for (i = 0; i<n; i++) queue[i] = 0;
    count = 0; head = 0;
    queue[count++] = unit;
    passed[unit] = true; //помечаем исходную вершину
    while (head<count) //пока очередь не пуста
    {
        unit = queue[head++]; //извлекаем текущую вершину
        cout << unit + 1 << " ";
        for (i = 0; i<n; i++) //перебираем вершины
            if (GM[unit][i] && !passed[i]) //если i не помечена и смежна с i
            {
                queue[count++] = i; //и добавляем в очередь
                passed[i] = true; //помечаем ее
            }
    }
    delete[]queue;
}
 
//поиск в глубину (Depth-first search, DFS) 
void DFS(int st)
{
    int r; //вершины графа
    cout << st + 1 << " ";
    visited[st] = true; //помечаем вершину
    for (r = 0; r <= n; r++) //перебираем вершины
        if ((GM[st][r] != 0) && (!visited[r])) //если вершина не помечена, и смежна с текущей
            DFS(r); //рекурсивно запускаем от нее DFS
}
 
////функция принимает граф с количеством вершин n и выполняет обход во всем графе
int main()
{
    setlocale(LC_ALL, "Rus");
    int start;
    //массив посещенных вершин
    bool *vis = new bool[n];
    cout << "Матрица смежности графа: " << endl;
    int l, k;
    l = k = 0;
    for (i = 0; i<n; i++)
    {
        used[i] = 0;
        visited[i] = false;
        vis[i] = false;
        for (j = 0; j<n; j++)
        {
 
            cout << " " << GM[i][j];
        }
        cout << endl;
    }
    for (i = 0; i < n; ++i)
    {
        for (j = 0; j<n; j++)
            if (GM[i][j] == 1) k++;
        g[i].resize(k);
        for (j = 0; j<n; j++)
            if (GM[i][j] == 1)
            {
                g[i][l] = j + 1;
                l++;
            }
        l = 0; k = 0;
    }
    for (i = 0; i<n; i++)
    {
        for (j = 0; j<(int)g[i].size(); j++)
        {
 
            cout << " " << g[i][j];
        }
        cout << endl;
    }
    cout << "Стартовая вершина >> "; cin >> start;
    //массив посещенных вершин
    cout << "Порядок обхода в ширину: ";
    BFS(vis, start - 1);
    cout << "\n" << "Порядок обхода в глубину: ";
    DFS(start - 1);
    delete[]visited;
    delete[]vis;
    system("pause>>void");
}