Advertisement
apl-mhd

BFSMy technique

Apr 13th, 2017
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <string.h>
  4. /****************************/
  5. /* (A)------------(B)*/
  6. /*  |              |      input like AB (vertices 4, edges4)
  7.  *  |              |                 AC
  8.  * (C)------------(D)                CD
  9.  *                                   BD
  10. /*                    */
  11.  
  12.  
  13.  
  14. using namespace std;
  15.  
  16. queue<int> number;
  17.  
  18.  
  19. int graph[50][50] = {0};
  20.  
  21. int edges, vertices;
  22.  
  23. int visited[100] = {0};
  24.  
  25. void graphInput(){
  26.        
  27.     cout<<"Input number of vertices"<<endl;
  28.     cin>>vertices;
  29.     cout<<"Input number of edges"<<endl;
  30.     cin>>edges;
  31.     char v1, v2;
  32.    
  33.    
  34.     for(int i=0; i<edges; i++){
  35.            
  36.             cin>>v1>>v2;
  37.             graph[v1-65][v2-65]=1;
  38.             graph[v2-65][v1-65]=1;
  39.        
  40.         }
  41.    
  42.     }
  43.    
  44. bool isVisited(int v){
  45.    
  46.     for(int i=0; i<100; i++){
  47.     if(visited[i] == v)
  48.         return true;
  49.    
  50.    
  51.     }
  52. return false;
  53. }
  54. void BFS(){
  55.     number.push(0);
  56.     int t,index=0;
  57.     while(!number.empty()){
  58.        
  59.         t = number.front();
  60.         number.pop();
  61.         for(int i =0; i<26; i++){
  62.            
  63.             if(graph[t][i]){
  64.                
  65.                 if(isVisited(i) == false ){
  66.                     number.push(i);
  67.                     //cout<<i;
  68.                     }          
  69.                 }
  70.                        
  71.             }
  72.            
  73.         if(isVisited(t) == false){
  74.             visited[index++] = t;
  75.             //cout<<t;
  76.         }      
  77.     }
  78.    
  79. }  
  80.  
  81.  
  82. void displayGraph(){   
  83.     for(int i=0; i<vertices; i++){
  84.             printf("%c->", i+65);
  85.         for(int j=0; j<26; j++){
  86.                 if(graph[i][j])
  87.                     printf("%c", j+65);
  88.             }
  89.            
  90.             cout<<endl;
  91.        
  92.         }
  93.    
  94. }
  95.  
  96. int main(int argc, char **argv)
  97. {
  98.     for(int i =0; i<100; i++)
  99.         visited[i] =-1;
  100.    
  101.     graphInput();
  102.    
  103.    
  104.    
  105.    
  106.     displayGraph();
  107.     BFS();
  108.    
  109.     for(int i=0; i<100; i++){
  110.    
  111.         if(visited[i] !=-1){
  112.             printf("%c", 65+visited[i]);
  113.            
  114.         }
  115.     }
  116.    
  117.    
  118.    
  119.     return 0;
  120. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement