0

here is topological sorting using DFS in c++,which has bugs(out of bound error)

#include<iostream>
#include<stdio.h>
using namespace std;
int count=0;
 static int *a=new int[8];

void dfs(int u,bool v[],bool matrix[][8])
{
    v[u]=true;
    for(int  i=0;i<8;i++)
        if(!v[i]&& matrix[u][i])
            dfs(i,v,matrix);

    a[count++]=u;
}

int main()
{
    bool v[8];
    bool matrix[8][8];
    matrix[7][6]=true;
    matrix[0][1];
    matrix[1][2]=true;
    matrix[2][3]=true;
    matrix[3][4]=true;
    matrix[2][5]=true;
    for(int i=0;i<8;i++)
        if(!v[i])
            dfs(i,v,matrix);
    for(int i=0;i<8;i++)
    cout<<a[7-i]<<"  ";
}

please help me to fix this error,i think i should create matrix[8][2],but how to continue after that?

Improve this question
4
  • Here's one candidate for an out of range access a[count++]=u;. How do you know that count is always in range during the recursive calls? Commented Apr 28, 2012 at 11:05
  • What error are you experiencing? Is it related to the fact that many elements in v and matrix are uninitialized? Commented Apr 28, 2012 at 11:05
  • @BoPersson - the condition on calling dfs is that v[i] is false. There are only 8 elements in v and the current one is set to false immediately in dfs, so I don't think there will be overindexing due to recursion. Commented Apr 28, 2012 at 11:07
  • What error do you get exactly ? do you get a segmentation fault ? there is no such things as out of bound error with c arrays... Commented Apr 28, 2012 at 11:23

1 Answer 1

Reset to default
2

I have done a few changes and now your program finishes successfully on ideone The most significant change is that you did not initialize matrix and v(even without this change the program still finished successfully but the output was only 0-s). I did not see the error you are talking about. The reason for getting only 0-s when you did not initialize v is obvious - all the values where non-zero and so all nodes where considered not visited.

EDIT: I also changed line 27 where you seemed to have forgotten " = true;"

EDIT 2: you are not freeing the memory for a which is not good. Also I don't see why you need dynamic array for a. You know its size aforehand. And one last remark - if you make the arrays matrix and v global they will get zeroed automatically(I am not saying that this is good approach just pointing out), but as they are local they are not zeroed.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments