Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.0 kB
1
Indexable
Never
#include <iostream>
#include <list>
#include <queue>

using namespace std;

// Functia pentru parcurgerea grafului in latime
void BFS(int numberOfNodes, int startNode, int** graph)
{
    // Marcam toate nodurile ca nevizitate
    bool* visited = new bool[numberOfNodes];
    for (int i = 0; i < numberOfNodes; i++)
        visited[i] = false;

    // Cream o coada si adaugam nodul de start
    queue <int> q;
    q.push(startNode);
    visited[startNode] = true;

    // Parcurgem nodurile
    while (!q.empty())
    {
        // Luam primul element din coada
        int currentNode = q.front();
        cout << currentNode << " ";
        q.pop();

        // Adaugam in coada vecinii nodului
        for (int i = 0; i < numberOfNodes; i++)
        {
            if (graph[currentNode][i] == 1 && !visited[i])
            {
                q.push(i);
                visited[i] = true;
            }
        }
    }
    cout << endl;
}

int main()
{
    // Numarul de noduri
    int numberOfNodes;
    cout << "Introduceti numarul de noduri: ";
    cin >> numberOfNodes;

    // Initializam matricea de adiacenta
    int** graph = new int* [numberOfNodes];
    for (int i = 0; i < numberOfNodes; i++)
        graph[i] = new int[numberOfNodes];

    // Initializam cu 0
    for (int i = 0; i < numberOfNodes; i++)
        for (int j = 0; j < numberOfNodes; j++)
            graph[i][j] = 0;

    // Introducem muchiile
    cout << "Introduceti perechile de valori care reprezinta muchiile grafului: " << endl;
    int x, y;
    while (true)
    {
        cout << "x: ";
        cin >> x;
        cout << "y: ";
        cin >> y;

        if (x == 0 && y == 0)
            break;

        graph[x][y] = 1;
        graph[y][x] = 1;
    }

    // Exemplu: perechi de valori care se potrivesc problemei
    // 1 2
    // 2 3
    // 3 4
    // 3 5
    // 0 0

    int startNode;
    cout << "Introduceti nodul de start: ";
    cin >> startNode;

    BFS(numberOfNodes, startNode, graph);

    return 0;
}