2/19 Graph Traversal DFS做法

justtim

請回復並且修改出BFS的做法

以下是DFS做法

1. #include<iostream>
   
2. #include<fstream>
   
3. #include<vector>
   
4. 
   
5. using namespace std ;
   
6. const int M = 9999 ;
   
7. 
   
8. int main()
   
9. {
   
10.     ifstream fin( "a.in" ) ;
    
11.     ofstream fout( "a.out" ) ;
    
12.    
    
13.     int x , y ;        
    
14.     fin >> x >> y ;
    
15.     int map[x][x] ;
    
16.     int visit[x] ;
    
17.     vector<int> vi ;   
    
18.         
    
19.     for( int i = 0 ; i < x ; i ++ )
    
20.     {
    
21.         for( int j = 0 ; j < x ; j ++ )
    
22.         {
    
23.             map[i][j] =  M ;
    
24.         }
    
25.         visit[i] = false ;
    
26.     }
    
27.    
    
28.     for( int i = 0 ; i < y ; i ++ )
    
29.     {
    
30.          int u,v ;
    
31.          fin >> u >> v ;
    
32.          map[u][v] = 1 ;
    
33.          map[v][u] = 1 ;
    
34.     }
    
35.    
    
36. /*    for( int i = 0 ; i < x ; i ++ )
    
37.     {
    
38.         for( int j = 0 ; j < x ; j ++ )
    
39.         {
    
40.             cout << map[i][j] << "\t" ;
    
41.         }
    
42.         cout << endl ;
    
43.     }   */
    
44. 
    
45.     for( int i = 0 ; i < x ; i ++ )
    
46.     {
    
47.          if( !visit[i] )
    
48.          {
    
49.              vi.push_back( i ) ;
    
50.              visit[i] = true ;
    
51.              while( !vi.empty() )
    
52.              {
    
53.                  int t = vi.front() ;
    
54.                  cout << vi.front() << "\t" ;
    
55.                  vi.erase( vi.begin() ) ;
    
56.                  for( int j = 0 ; j < x ; j ++ )
    
57.                  {
    
58.                      if( !visit[j] && map[t][j] != M )
    
59.                      {
    
60.                          vi.insert( vi.begin() , j ) ;   
    
61.                          visit[j] = true ;
    
62.                      }
    
63.                  }      
    
64.              }
    
65.          }
    
66.     }
    
67. 
    
68.     system( "Pause" ) ;   
    
69. }

複製代碼

輸入檔a.in

1. 7 6
   
2. 0 1
   
3. 0 2
   
4. 1 3
   
5. 1 4
   
6. 2 5
   
7. 2 6

複製代碼

蔡昀修

先貼先贏

a3218290

#include<iostream>
#include<fstream>
#include<vector>

using namespace std ;
const int M = 9999 ;

int main()
{
    ifstream fin( "a.in" ) ;
    ofstream fout( "a.out" ) ;
   
    int x , y ;        
    fin >> x >> y ;
    int map[x][x] ;
    int visit[x] ;
    vector<int> vi ;   
        
    for( int i = 0 ; i < x ; i ++ )
    {
        for( int j = 0 ; j < x ; j ++ )
        {
            map[i][j] =  M ;
        }
        visit[i] = false ;
    }
   
    for( int i = 0 ; i < y ; i ++ )
    {
         int u,v ;
         fin >> u >> v ;
         map[u][v] = 1 ;
         map[v][u] = 1 ;
    }

    for( int i = 0 ; i < x ; i ++ )
    {
         if( !visit[i] )
         {
             vi.push_back( i ) ;
             visit[i] = true ;
             while( !vi.empty() )
             {
                 int t = vi.front() ;
                 cout << vi.front() << "\t" ;
                 vi.erase( vi.begin() ) ;
                 for( int j = 0 ; j < x ; j ++ )
                 {
                     if( !visit[j] && map[t][j] != M )
                     {
                         visit[j] = true ;
                         vi.insert( vi.end() , j ) ;   
                     }
                 }      
             }
         }
    }

    system( "Pause" ) ;   
}
明明是我先做出來的((茶

蔡昀修

#include<iostream>
#include<fstream>
#include<vector>

using namespace std ;
const int M = 9999 ;

int main()
{
    ifstream fin( "a.in" ) ;
    ofstream fout( "a.out" ) ;
   
    int x , y ;        
    fin >> x >> y ;
    int map[x][x] ;
    int visit[x] ;
    vector<int> vi ;   
        
    for( int i = 0 ; i < x ; i ++ )
    {
        for( int j = 0 ; j < x ; j ++ )
        {
            map[i][j] =  M ;
        }
        visit[i] = false ;
    }
   
    for( int i = 0 ; i < y ; i ++ )
    {
         int u,v ;
         fin >> u >> v ;
         map[u][v] = 1 ;
         map[v][u] = 1 ;
    }
   
/*    for( int i = 0 ; i < x ; i ++ )
    {
        for( int j = 0 ; j < x ; j ++ )
        {
            cout << map[i][j] << "\t" ;
        }
        cout << endl ;
    }   */

    for( int i = 0 ; i < x ; i ++ )
    {
         if( !visit[i] )
         {
             vi.push_back( i ) ;
             visit[i] = true ;
             while( !vi.empty() )
             {
                 int t = vi.front() ;
                 cout << vi.front() << "\t" ;
                 vi.erase( vi.begin() ) ;
                 for( int j = 0 ; j < x ; j ++ )
                 {
                     if( !visit[j] && map[t][j] != M )
                     {
                        
                         vi.insert( vi.end() , j ) ;
                         visit[j] = true ;
                     }
                 }      
             }
         }
    }

    system( "Pause" ) ;   
}