Alg_Lab_9 (lll semester)

#include "stdafx.h"
#include <iostream>
#include <ctime>

using namespace std;

//поиск в глубину
void DFS(int* graph[], int st, int size, bool visited[])
{
    cout << st + 1 << " ";
    visited[st] = true;
    for (int r = 0; r <= size; r++)
        if ((graph[st][r] != 0) && (!visited[r]))
            DFS(graph, r, size, visited);
}
//поиск в ширину
void BFS(int* graph[], bool *visited, int unit, int size)
{
    int *queue = new int[size];
    int count, head;
    for (int i = 0; i<size; i++) queue[i] = 0;
    count = 0; head = 0;
    queue[count++] = unit;
    visited[unit] = true;
    while (head<count)
    {
        unit = queue[head++];
        cout << unit + 1 << " ";
        for (int i = 0; i<size; i++)
            if (graph[unit][i] && !visited[i])
            {
                queue[count++] = i;
                visited[i] = true;
            }
    }
    delete[]queue;
}

int main()
{
    setlocale(LC_ALL, "Rus");
    srand(time(NULL));
    int size, option, start;
    cout << "Enter the size of the matrix: ";
    cin >> size;
    int **graph = new int*[size];
    for (int i = 0; i < size; i++)
        graph[i] = new int[size];
    cout << "1 - Random" << endl;
    cout << "2 - Manual" << endl;
    cout << "Your choice: ";
    cin >> option;
    switch (option)
    {
    case 1:
        for (int i = 0; i < size; i++)
            for (int j = 0; j < size; j++)
                graph[i][j] = 0 + rand() % 2;
        break;
    case 2:
        for (int i = 0; i < size; i++)
            for (int j = 0; j < size; j++)
            {
                cout << "[" << i << "][" << j << "->";
                cin >> graph[i][j];
            }
        break;
    }
    cout << "The adjacency matrix of a graph: " << endl;
    bool *visitedDFS = new bool[size];
    bool *visitedBFS = new bool[size];
    for (int i = 0; i < size; i++)
    {
        visitedDFS[i] = false;
        visitedBFS[i] = false;
        for (int j = 0; j < size; j++)
            cout << " " << graph[i][j];
        cout << endl;
    }
    cout << "Enter start top: ";
    cin >> start;
    //в глубину
    cout << "Search in depth" << endl;
    cout << "Bypass order: ";
    DFS(graph, start - 1, size, visitedDFS);

    //в ширину
    cout << "\nSearch in width" << endl;
    cout << "Bypass order: ";
    BFS(graph, visitedBFS, start - 1, size);

    delete[]visitedDFS;
    delete[]visitedBFS;
    delete[]graph;

    cout << endl;
    system("pause");
}