Depth-First Search using matrices

This is a discussion on Depth-First Search using matrices within the C++ Programming forums, part of the General Programming Boards category; Hello all, I need help with this assignment I am doing for my data structures class. I need to make ...

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    92

    Depth-First Search using matrices

    Hello all,
    I need help with this assignment I am doing for my data structures class. I need to make a Depth-First Search Algorithm.
    In order to do this, I have thought of a clever(well, maybe not that clever but hey I am still a student so gimme a break) way to take care of this. I have decided to use a 2 dimensional array and make a adjacency list. So, suppose we have the nodes, {0,1,2,3,4,5} and we have the following connections:
    {(0,1)(0,2)(0,5)(1,3)(2,5)(3,4)} that would mean that we have an adjacency list like so:

    012345
    0 |011001|
    1 |000100|
    2 |000101|
    3 |000010|
    4 |000000|
    5 |000000|

    According to the adjacency list and assuming that our start is 0 and our goal is 4, one possible path might be [0, 1, 3, 4]
    Now, here's the problem: I am having trouble populating this 2-dimensional array. Here's the code I have so far. The explanation of the code is after the code itself

    Code:
    #include <iostream.h>
    
    void printArray( int a[5][5] );
    
    int main(){
      int num1, num2;
      const int delim = -1;
      int array_test[5][5];
    
      while (num1 != delim){
        cin >> num1;
        cin >> num2;
        for ( int i = 0; i <= 5; i++ ){
          array_test[num1][num2] = 1;
        }
        printArray(array_test);
    
        return 0;
      }
      
    }
    void printArray( int a[ 5 ][ 5 ] )
    {
      for ( int i = 0; i <= 5; i++ ){
        for ( int j = 0; j <= 5; j++ )
          cout << a[ i ][ j ] << ' ';
        
        cout << endl;
      }
    }
    The input is supposed to the program is as follows:
    //the first two numbers are the start and the goal
    //i.e - start at node 0 and end at node 4
    04
    //the rest are connections from node - to - node
    01
    02
    05
    13
    23
    25
    34
    //when user wants to end edge input type in -1 for both nodes
    -1-1
    First of all, I have no idea how to give the user this kind of flexibility in input(isn't it easier to put into a regular text file and then read from the text file?). Second of all, if anyone would run my code, they would see that my array does not get printed up right. I will be eternally grateful to whomever can help me. Thank you.
    Last edited by supaben34; 10-31-2002 at 07:14 PM.

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    Remember C++ uses 0 based counting.

    Code:
    void printArray( int a[ 5 ][ 5 ] )
    {
      for ( int i = 0; i <= 5; i++ ){
        for ( int j = 0; j <= 5; j++ )
          cout << a[ i ][ j ] << ' ';
       
        cout << endl;
      }
    }
    Here, when i = 6, you are accessing the 6th row, but there are only 5 rows, so bad stuff happens.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  3. #3
    Registered User
    Join Date
    Sep 2002
    Posts
    92
    ...but i will never equal 6. Maybe I am missing something but could you explain this a little further? Thanks

  4. #4
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    Doh .

    Replace that 6 with a 5, and it all makes sense. Here are the rows,

    0,1,2,3,4

    Notice there are 5 of them. However, when i =5, you access the 6th row, and bad stuff happens.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  5. #5
    I lurk
    Join Date
    Aug 2002
    Posts
    1,361
    Code:
    #include <iostream>
    
    void printArray( int a[5][5] );
    
    int main()
    {
      using namespace std;
      int num1 = 0;
      int num2;
      const int delim = -1;
      int array_test[5][5];
    
      while (num1 != delim){
        cin >> num1;
        cin >> num2;
        for ( int i = 0; i < 5; i++ ){
          array_test[num1][num2] = 1;
        }
        printArray(array_test);
    
        return 0;
      }
      
    }
    void printArray( int a[ 5 ][ 5 ] )
    {
      using namespace std;
      for ( int i = 0; i < 5; i++ ){
        for ( int j = 0; j < 5; j++ )
          cout << a[ i ][ j ] << ' ';
        
        cout << endl;
      }
    }
    1) Use iostream, not iostream.h
    2) When you declare a 5 element array, you may access elements 0-4, not element 5, I changed i <= 5 to i < 5
    3) Don't compare variables before they're initilized. You're comparing num1 to delim and you have no idea what num1 holds.
    Last edited by Eibro; 11-01-2002 at 08:22 PM.

  6. #6
    Registered User
    Join Date
    Sep 2002
    Posts
    92
    It still has not worked for me guys. Am I placing the elements in the array wrong?

  7. #7
    Registered User
    Join Date
    Sep 2002
    Posts
    92

    Declaring new 2-d array

    Hey all,
    Side-question for ya'll... What is the syntax for declaring a new multi-dimensional array? Is it like this?
    Code:
    array = new int([Size][Size]);
    Thanks

  8. #8
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Your confusing an adjacency list with an adjacency matrix.
    Most representations of a graph use an adjacency list
    since for storage it's O(V + E) while an adjacency matrix
    is O(V^2). Only when E = O(V^2) or graph is small
    do you want to use an adjacency matrix.

    This is an adjacency list for
    {0,1,2,3,4,5}
    {(0,1)(0,2)(0,5)(1,3)(2,5)(3,4)}
    0 ->1->2->5
    1->3
    2->5
    3->4
    -> is links in a link list.

  9. #9
    Registered User
    Join Date
    Sep 2002
    Posts
    92

    Got the matrix... now what?

    Hey all,
    I need your help with something. I need to make a depth-first search algorithm. I finally got the adjacency list finished. I was wondering if someone could help me write the depth-first search algorithm.. here's what I have so far
    Code:
    #include <iostream>                                                                             
                                                                                                    
    int main(){                                                                                     
      int num1 = 0;                                                                                 
      int num2 = 0;                                                                                 
      int array_test[10][10] = { 0 };                                                               
      int start, goal;                                                                              
                                                                                                    
      cin >> start >> goal;                                                                         
      cout << "Start Node:" << start << "\n";                                                       
      cout << "Goal Node:" << goal << "\n";                                                         
      for (int i = 0; i < 10; i++){                                                                 
        cin >> num1 >> num2;                                                                        
        if ((num1 != -1) && (num2 != -2))                                                           
          array_test[num1][num2] = 1;                                                               
      }                                                                                             
                                                                                                    
      for (int j = 0; j < 10; j++){                                                                 
        cout << "\n";                                                                               
        for (int k = 0; k < 10; k++)                                                                
          cout << array_test[j][k] << " ";                                                          
      }                                                                                             
                                                                                                    
      cout << "\n";                                                                                 
                                                                                                    
      return 0;                                                                                     
    }
    Any help would be appreciated. Thank you.

  10. #10
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Easiest way is to call dfs recursivly on all of the nodes
    adjacent to a vertex. You will also have to keep track
    of which nodes you have allready visted.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21