CPrograms/graphs.cpp at master · rodo117/CPrograms · 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
#include <iostream>
#include <vector>
#include <list>
#include <cstdlib>
#define graphSize 7
using namespace std;


vector < vector< int > > adjList(graphSize);


class Graph{

private:
 //create an array to check what vertice was visited
 bool visited [graphSize];
 // Create a queue for BFS
 list <int> Queue;
 bool checkVisited(int vertice);
public:
  void BFS(int inicio);

  Graph(){

   adjList[0].push_back(1);

   adjList[1].push_back(0);
   adjList[1].push_back(4);
   adjList[1].push_back(5);

   adjList[2].push_back(3);
   adjList[2].push_back(4);
   adjList[2].push_back(5);

   adjList[3].push_back(2);
   adjList[3].push_back(6);

   adjList[4].push_back(1);
   adjList[4].push_back(2);

   adjList[5].push_back(1);
   adjList[5].push_back(2);
   adjList[5].push_back(6);

   adjList[6].push_back(3);
   adjList[6].push_back(5);

  }

};


bool Graph::checkVisited(int vertice){


   return visited[vertice];


}


void Graph::BFS(int vertice){

 // Mark all the vertices as not visited
   for(int i =0;i<graphSize;i++){

    this->visited[i]=false;

   }

   int i=0;

   visited[vertice]=true;

   while(i<graphSize){

    vector<int> adjacency = adjList[vertice];
     for(int j=0;j<adjacency.size();j++){
       if(visited[adjacency[j]]!=true){
        this->Queue.push_back(adjacency[j]);
        this->visited[adjacency[j]]=true;
        cout<<adjacency[j]<<endl;
       }
     }

     if(!Queue.empty()){
     vertice = this->Queue.front();
     Queue.pop_front();
     cout<<""<<endl;
     }
     i++;
   }


}


int main(){

int verticeInicio;
cout<<"En que vertice quieres iniciar"<<endl;
cin>>verticeInicio;
cout<<endl;


    Graph graph;
    graph.BFS(verticeInicio);

 system("PAUSE");


return 0;


}