ALGORITHM NOTE

001 #define MAX 1000
002 int size;
003 int adjMatrix[MAX][MAX]; // graph structure
004 bool visited[MAX];
005 int group[MAX];
006 
007 void visit( int currentNode, int id ){
008     visited[currentNode] = true;
009     group[currentNode] = id;
010     
011     for ( int nextNode = 0; nextNode < size; nextNode++ ){
012         if ( !adjMatrix[currentNode][nextNode] ) continue;
013         if ( !visited[nextNode] ){
014             visit( nextNode, id );
015         }
016     }
017 }
018 
019 void depthFirstSearch(){
020     for ( int i = 0; i < size; i++ ) visited[ i ] = false;
021     int number = 1;
022     for ( int startNode = 0; startNode < size; startNode++ ){
023         if ( !visited[startNode] ) visit( startNode, number++ );
024     }
025 }
026 
027 void inputGraph(){
028     cin >> size;
029     
030     for ( int i = 0; i < size; i++ ){
031         for ( int j = 0; j < size; j++ ){
032             adjMatrix[i][j] = 0;
033         }
034     }
035     
036     int source, target;
037     // input based on adjMatrix
038     for ( int source = 0; source < size; source++ ){
039         for ( int target = 0; target < size; target++ ){
040             cin >> adjMatrix[source][target];
041         }
042     }
043 }
044 
045 int main(){
046     inputGraph();
047     depthFirstSearch();
048     
049     for ( int i = 0; i < size; i++ ){
050         cout << i << " " << group[i] << endl;
051     }
052     return 0;
053 }

001 #define MAX 1000
002 int size;
003 int adjMatrix[MAX][MAX]; // graph structure
004 
005 void breadthFirstSearch( int source ){
006     queue< int > Q;
007     bool visited[MAX];
008     int dist[MAX];
009     int pi[MAX];
010     
011     for ( int i = 0; i < size; i++ ) {
012         visited[i] = false;
013         dist[i] = INT_MAX;
014     }
015     int currentNode = source;
016     
017     Q.push( currentNode );
018     visited[currentNode] = true;
019     dist[currentNode] = 0;
020     pi[currentNode] = -1;
021     
022     while ( !Q.empty() ){
023         currentNode = Q.front(), Q.pop();
024         
025         for ( int nextNode = 0; nextNode < size; nextNode++ ){
026             if ( !adjMatrix[currentNode][nextNode] ) continue;
027             if ( !visited[nextNode] ){
028                 visited[nextNode] = true;
029                 dist[nextNode] = dist[currentNode] + 1;
030                 pi[nextNode] = currentNode;
031                 Q.push( nextNode );
032             }
033         }
034     }
035 }

001 #define MAX 1000
002 int size;
003 int adjMatrix[ MAX ][ MAX ]; // graph structure
004 
005 void breadthFirstSearch(){
006     queue< int > Q;
007     bool visited[ MAX ];
008     for ( int i = 0; i < size; i++ ) visited[ i ] = false;
009     int currentNode = 0;
010     
011     Q.push( currentNode );
012     visited[ currentNode ] = true;
013     
014     while ( !Q.empty() ){
015         currentNode = Q.front(), Q.pop();
016         
017         cout << currentNode << endl;
018         
019         for ( int nextNode = 0; nextNode < size; nextNode++ ){
020             if ( !adjMatrix[ currentNode ][ nextNode ] ) continue;
021             if ( !visited[ nextNode ] ){
022                 visited[ nextNode ] = true;
023                 Q.push( nextNode );
024             }
025         }
026     }
027 }
028 
029 void inputGraph(){
030     cin >> size;
031     for ( int i = 0; i < size; i++ ){
032         for ( int j = 0; j < size; j++ ){
033             adjMatrix[i][j] = 0;
034         }
035     }
036     
037     int source, target;
038     for ( int i = 0; i < size; i++ ){
039         for ( int j = 0; j < size; j++ ){
040             cin >> adjMatrix[i][j];
041         }
042     }
043 }
044 
045 int main(){
046     inputGraph();
047     breadthFirstSearch();
048     
049     return 0;
050 }

001 #define MAX 1000
002 int size;
003 int adjMatrix[MAX][MAX]; // graph structure
004 bool visited[MAX];
005 
006 void dfs( int currentNode ){
007     visited[ currentNode ] = true;
008     
009     // perform some activities here
010     
011     for ( int nextNode = 0; nextNode < size; nextNode++ ){
012         if ( !adjMatrix[ currentNode ][ nextNode ] ) continue;
013         if ( !visited[ nextNode ] ){
014             dfs( nextNode );
015         }
016     }
017 }
018 
019 void depthFirstSearch(){
020     for ( int i = 0; i < size; i++ ) visited[ i ] = false;
021     int startNode = 0;
022     
023     dfs( startNode );
024 }
025 
026 void inputGraph(){
027     cin >> size;
028     
029     for ( int i = 0; i < size; i++ ){
030         for ( int j = 0; j < size; j++ ){
031             adjMatrix[i][j] = 0;
032         }
033     }
034     
035     int source, target;
036     // input based on adjMatrix
037     for ( int source = 0; source < size; source++ ){
038         for ( int target = 0; target < size; target++ ){
039             cin >> adjMatrix[source][target];
040         }
041     }
042 }
043 
044 int main(){
045     inputGraph();
046     depthFirstSearch();
047     
048     return 0;
049 }