PREFACE

redfer to UNSW COMP9024

• recursive
• non-recursive

Note it’s graph, not only tree!

recursive

static void DepthFirstSearch(struct Graph *pGraph, long u, int *visited) {
    visited[u] = 1;

    printf("visiting %s\n", pGraph->pNodes[u].name);

    // recursively visit the adjacent nodes of u, if they have not been visited yet
    for(long v = 0; v < pGraph->n; v++) {
        if (MatrixElement(pGraph, u, v) == CONNECTED && !visited[v]) {
            DepthFirstSearch(pGraph, v, visited);
        }
    }
}

void RecursiveDFS(struct Graph *pGraph, long u) {
    // Note visited is an array, not only an int
    int *visited = (int *) malloc(pGraph->n * sizeof(int));
    //memset(visited, 0, sizeof(int) * pGraph->n);
    for (long v = 0; v < pGraph->n; v++) {
        visited[v] = 0;
    }
    DepthFirstSearch(pGraph, u, visited);
    printf("\n");
    free(visited);
}

For example, search from node 3.

non-recursive

if use non-recursive algorithm, we must use a stack.

#if 1
/*
    Please complete the code in Q1-Q5:

    Q1:  create a data stack
    Q2:  push u onto the data stack
    Q3:  test whether the data stack is empty
    Q4:  push v onto the data stack
    Q5:  free the heap space occupied by the data stack

  */
void NonRecursiveDFS(struct Graph *pGraph, long u) {
    assert(IsLegalNodeNum(pGraph, u));
    static long cnt = 0;

    int *visited = (int *) malloc(sizeof(int) * pGraph->n);
    // struct Stack *pStack = ______Q1______;
    struct Stack *pStack = createStack();

    assert(visited && pStack);

    for (long i = 0; i < pGraph->n; i++) {
        visited[i] = 0;
    }

    printf("\n\t\t\t\tpush %ld\n", u);
    // ______Q2______;
    StackPush(pStack, u);

    // while (______Q3______) {
    while (!StackIsEmpty(pStack)) {

        printf("\n");

        // If visited the node, just Pop it!
        PrintStack(pStack);
        STACK_ITEM_T curNodeId = StackPop(pStack);
        printf("\t\t\t\tpop %ld\n", curNodeId);

        if (!visited[curNodeId]) {
            visited[curNodeId] = 1;
            printf("\t\t\t\t\t\tvisiting %s\n", pGraph->pNodes[curNodeId].name);

            // Put all the adjancient node into the stack
            for (long v = pGraph->n - 1; v >= 0; v--) {
                if (MatrixElement(pGraph, curNodeId, v) == CONNECTED && !visited[v]) {
                    // ______Q4______;
                    StackPush(pStack, v);
                    printf("\t\t\t\tpush %ld\n", v);
                }
            }            
        }
    }
    printf("\n");
    // ______Q5______;
    StackRelease(pStack);

    free(visited);    
}
#endif

---

Welcome to point out the mistakes and faults!