Depth-First Search using matrices

[supaben34]

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

#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.

[SilentStrike]

Remember C++ uses 0 based counting.

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.

[supaben34]

...but i will never equal 6. Maybe I am missing something but could you explain this a little further? Thanks

[SilentStrike]

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.

[Eibro]

#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.

[supaben34]

It still has not worked for me guys. Am I placing the elements in the array wrong?

[supaben34]

Hey all,
Side-question for ya'll... What is the syntax for declaring a new multi-dimensional array? Is it like this?

array = new int([Size][Size]);

Thanks

[Nick]

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.

[supaben34]

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

#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.

[Nick]

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.