Estudos/algoritimoBFS.cpp at main · DestinyWolf/Estudos · GitHub

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
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#include <list>
using std::list; //evitar ter que digitar std::palavra

#include <iostream>
using std::cout; //evitar ter que digitar std::palavra
using std::cin;  //evitar ter que digitar std::palavra
using std::endl; //evitar ter que digitar std::palavra


#include <vector>
using std::vector;//evitar ter que digitar std::palavra

#include <queue>
using std::queue; //evitar ter que digitar std::palavra


list<int> BFS(int start, int end, vector<list<int>> graph, int v);

//função principal do codigo
int main(){

    //declaração de variaveis
    int v, e;
    int a, b;
    int start, end;

    //quantidade de vertices
    cout << "vertice: ";
    cin >> v;

    //quantidade de arestas
    cout << "aresta: ";
    cin >> e;

    //ponto de partida
    cout << "ponto de partida: ";
    cin >> start;

    //destino
    cout << "destino: ";
    cin >> end;

    //craição do grafo usando lista de
    vector<list<int>> graph;

    //criação de uma lista para guardar o caminho
    list<int> finded(v);
    //criação de uma fila
    queue<int>q;
    //criação de 2 vectores
    vector<int> past(v, -2); //cria o vetor com tamanho v e popula com o valor de -2
    vector<bool> visited(v, false); //cria um vetor de tamanho v e ja popula com o valor false


    //definindo o tamnho do vetor
    graph.resize(v);
    for (int i = 0; i < e; i++) {
        graph[i].resize(e);
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int j;
    for (int i = 0; i < v; i++)
    {
        cout << i << " " ;
        for(auto j: graph[i]){
            cout << j << " ,";
        }
        cout << endl;
    }

    /*
    finded = BFS(start, end, graph, v);

    for(auto v: finded)
        cout << v << " ";
*/
}


list<int> BFS(int start, int end, vector<list<int>> graph, int v){

    queue<int>q;
    vector<int> past(v, -2);
    vector<bool> visited(v, -2);

    int elements, count;


    visited[start] = true;
    past[start] = -1;
    q.push(start);
    while (!q.empty())
    {
        start = q.front();
        q.pop();
        list<int> aux(graph[start].size());
        aux = graph[start];

        for(auto i: aux){
            if(i == end){
                for (auto elements: past)
                {
                    if (past[elements] != -2)
                        count ++;
                }

                list<int> finded(count);
                int numbers = i;
                while(numbers != -1)
                {
                    finded.push_back(numbers);
                    numbers = past[numbers];
                }
                return finded;
            }
            else {
                q.push(i);

                if(!visited[i]){
                    if (past[i] == -2)
                    {
                        past[i] = start;
                    }
                    visited[i] = true;
                }
            }
        }
    }
}