返回列表 發帖

2/19 Graph Traversal DFS做法

本帖最後由 justtim 於 2011-2-19 21:44 編輯

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

以下是DFS做法
  1. #include<iostream>
  2. #include<fstream>
  3. #include<vector>

  4. using namespace std ;
  5. const int M = 9999 ;

  6. int main()
  7. {
  8.     ifstream fin( "a.in" ) ;
  9.     ofstream fout( "a.out" ) ;
  10.    
  11.     int x , y ;        
  12.     fin >> x >> y ;
  13.     int map[x][x] ;
  14.     int visit[x] ;
  15.     vector<int> vi ;   
  16.         
  17.     for( int i = 0 ; i < x ; i ++ )
  18.     {
  19.         for( int j = 0 ; j < x ; j ++ )
  20.         {
  21.             map[i][j] =  M ;
  22.         }
  23.         visit[i] = false ;
  24.     }
  25.    
  26.     for( int i = 0 ; i < y ; i ++ )
  27.     {
  28.          int u,v ;
  29.          fin >> u >> v ;
  30.          map[u][v] = 1 ;
  31.          map[v][u] = 1 ;
  32.     }
  33.    
  34. /*    for( int i = 0 ; i < x ; i ++ )
  35.     {
  36.         for( int j = 0 ; j < x ; j ++ )
  37.         {
  38.             cout << map[i][j] << "\t" ;
  39.         }
  40.         cout << endl ;
  41.     }   */

  42.     for( int i = 0 ; i < x ; i ++ )
  43.     {
  44.          if( !visit[i] )
  45.          {
  46.              vi.push_back( i ) ;
  47.              visit[i] = true ;
  48.              while( !vi.empty() )
  49.              {
  50.                  int t = vi.front() ;
  51.                  cout << vi.front() << "\t" ;
  52.                  vi.erase( vi.begin() ) ;
  53.                  for( int j = 0 ; j < x ; j ++ )
  54.                  {
  55.                      if( !visit[j] && map[t][j] != M )
  56.                      {
  57.                          vi.insert( vi.begin() , j ) ;   
  58.                          visit[j] = true ;
  59.                      }
  60.                  }      
  61.              }
  62.          }
  63.     }

  64.     system( "Pause" ) ;   
  65. }
複製代碼
輸入檔a.in
  1. 7 6
  2. 0 1
  3. 0 2
  4. 1 3
  5. 1 4
  6. 2 5
  7. 2 6
複製代碼

#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" ) ;   
}

TOP

#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" ) ;   
}
明明是我先做出來的((茶

TOP

先貼先贏

TOP

返回列表