Hmmm, can anyone help with Depth First Search?

[bgbnbigben]

So, this is what ive got.
Im trying to create a depth first search algorithm, but the problem is ive never been taught this - i dont do programming at school or uni, i try to teach myself
but i need help sometimes.
Im using a fairly simple iterated method of a DFS. Also, sorry about the lack of comments - this is all an informatics solution,so the code is throwaway and doesnt really need comments when im coding it, so i leave them out.
There are a few of them in there though.

#include <cstdio>
#include <vector>
#include <cstdlib>
#include <list>
using namespace std;
int main () {
    FILE* in = fopen("sculptin.txt", "r");
    FILE* out = fopen("sculptout.txt", "w");
    int n; //number of apples.
    fscanf(in,"%d", &n);
    int a, x, b, y;
    int z;
    z = n*4;
    vector<int> applearray(z);
    int f;
    f = 0; 
    for (;f<applearray.size();f = f+4){
        fscanf(in, "%d %d %d %d", &applearray[f], &applearray[f+1], &applearray[f+2], &applearray[f+3]);}   
    int c, d, g, h;
    int  t, u; // NOT USED
    vector<int> treesize(n);
    list<int> dfs_unvisited;
    list<int> dfs_visited;
    g = 0; 
    c = 0;
    f = 0;
// this loop is for the top half of the tree (Tracking stage)    
    while (applearray[f] != 0){                
          d = applearray[f];
          dfs_unvisited.push_back(d);
          f = applearray[f]*3 - (4 - d); }
    if (applearray[f] == 0){
       while (applearray[f] !=0) {
             f = d;
             f += 2;
             d = f;
             dfs_unvisited.push_back(d);
             f = applearray[f]*3 - (4 - d);}
             }
    f = 2;
   // this loop is for the second half of the tree.    
   while (applearray[f] != 0){                 
          d = applearray[f];
          dfs_unvisited.push_back(d);
          f = applearray[f]*3 - (4 - d);}
    if (applearray[f] == 0){
       while (applearray[f] !=0) {
             f = d;
             f += 2;
             d = f;
             dfs_unvisited.push_back(d);
             f = applearray[f]*3 - (4 - d);}}
    printf("%d", dfs_unvisited.size());
    system("pause");
               // I NEED TO ADD STUFF TO MY LIST.
                 
                 
// this loop is after tracking - its supposed to total up the length to the end of the graph from each tree    
        for (f = 1; f<=applearray.size(); f +=2 ){      
        if (f == 1||3){
           treesize[g] = applearray[f]; }
        c = treesize[g];
        d = applearray[f];                                         
        f--;
        f = applearray[f]*3 - (4 - d);
        f++;  
        treesize[g] = c + applearray[f];
        g++;
        } //end of the for loop         
            
            // ADD EVERY NODE ON EACH LINE TO A LIST AND GO THROUGH EACH  NODE.
            
return 0;    
}

and if anyone was wondering, the input file is in the format
n - there are going to be n lines proceeding this, each describing the links to and from a node. the first line below describes the first node, the second describes the second, etc.
a x b y - a is the node it links to with a length of x. It also links to b with a length of y.

The graph is directed and weighted, for further information.
I have managed to implement a BFS in this, but i know that it is not optimal for this sort of search, and so want to learn how to do a DFS (iterated). I guess i would like to learn the recursive version, too, but i currently dont even know the difference between the iterated and recursive versions.
And please dont tell me that you refuse to do my homework for me.
because its not my homework.
Many thanks in advance for any help,
Ben

[Salem]

> if (f == 1||3)
This doesn't do what you think it does.
It's actually if (f == 1 || 3 != 0 ) The latter being trivially true all the time.

Second, a DFS search may be simplified by using a recursive function. I notice that you just have a sprawling mass in main().
Each loop which performs a specific task (read your comments) could easily be made into a separate function.

Half a dozen functions, each at most 20 lines long would allow you to focus on specific details of what works and what doesn't.

Third, if you're learning C++ then drop all the 'C' methods for reading files - fopen, fscanf etc.

[bgbnbigben]

yeah, i know what you mean about dropping the c habits
just a bad habit that WILL be fixed.....

It's actually
if (f == 1 || 3 != 0 )
The latter being trivially true all the time.

actually, the f will always start at 1, making it true.
it then runs through all the input untill it finds a 0, at which point it ends.
the
if == 1 || 3 means, in plain english, if f is equal to one or three, which it will be, twice. then it should run until it comes across a zero, at which point its supposed to backtrack.
But forgive me if that was/sounded condescending/ungrateful/i've missed the point entirely.

Now, about a recursive version...i dont actually know what the difference between the iterated and recursive versions are. in fact, i dont even know how to implement the iterated version, let alone the recursive one.
True, the sprawling mass can be recreated into functions.
but this isnt me trying to be a genius for a programming class, its just throwaway informatics. i dont want to spend too long programming this easy to read, easy to modify masterpiece so i can just shelf it once i submit it.
although my code is far from easy to read and a masterpiece......

Thanks for the help, though.

[mitrmkar]

I think you might be missing the point 'The latter being trivially true all the time.' i.e. you have to write the if statement like: if (f == 1 || f == 3) If you write it like:

if (f == 1||3)
// or
if (f == 1 || 3 != 0 )

then the condition will always be true, regardless of the f's value, because 3 simply is not equal to 0.

[tesuji]

the
if == 1 || 3 means, in plain english, if f is equal to one or three, which it will be, twice. then it should run until it comes across a zero ...

Always true as Salem already stated. Because 3 != false is true, || 3 always evaluates true! You don' t believe that? try if(false||3) cout "???" and if(true||3) cout "???". What do you see? Possibly you want this: if (f==1 || f == 3) ...

[bgbnbigben]

but either way, that wont solve the recursive/iterated dfs. i can now admit that it may help with the forward half of the search, but a DFS is supposed to backtrack. I can not get it to backtrack. I can easily manage a BFS, because thats always a LIFO queue that you put vertices into. But i cant manage a working FIFO list.
Im not worried about the syntax atm, because i can always fix that if i stuff up later. But i cant fix the DFS because i can not create it.