tree search algorithms

// Breadth-First Search
// The tricky part is that we have to know the entire info. about
// the graph, which indicates in the link-matrix graphmatrix

struct node{
    int color;    // 0-white, 1-grey, 2-black
    int index;    // fount order
    int d;         // distance to the root
    struct node *parent;
};
typedef struct node* Node;

void buildBFS1(int *graphmatrix, Node graph, Node start){
    int i=0, n, head, tail;
    Node queue;    // used as stack to do BFS
    Node temp;

    while(graph[i]!=NULL){
        graph[i].color = 0;
        graph[i].index = i;
        graph[i].parent = NULL;
        graph[i].d = 0;
        i++;
    }
    n = i;
    start->color = 1;
    queue = (Node)malloc(n*sizeof(Node));    // not sure here...
    head = tail = 0;
    enqueue(queue, &tail, start);

    while(!isEmpty(head, tail)){
        temp = dequeue(queue, &head);
        for (i=0; i
            if(graphMatrix[temp->index][i]!=0){
                if(graph[i].color==0){
                    graph[i].color = 1;
                    graph[i].d = temp->d+1;
                    graph[i].parent = temp;
                    enqueue(queue, &tail, graph[i]);
                }
            }
        }
        temp->color = 2;
    }
}

void initQueue(int *head, int *tail){
    *head = *tail =0;
}

void enqueue(Node q, int *tail, Node element){
    q[(*tail)++]=element;
}

Node dequeue(Node q, int *head){
    return q[(*head)++];
}

int isEmpty(int head, int tail){
    return head==tail? 1:0;
}

int isFull(int tail, const int size){
    return tail==size? 1:0;
}


// Depth-First Search
// has more knowledge about the structure of the tree
// at the cost of a more complicated struct

struct node{
    int index;
    int color;
    int detected;
    int finished;
    struct node *parent;
}
typedef struct node* Node;

// the original algorithm in the textbook is a little bit wierd
// cause it is different from BFS by no need of starting point
// while it is obvious that starting with different points will
// generate trees with different structures, given the same link-matrix
void buildDFS(int *graphMatrx, Node graph, Node start){
    int i=0, n, time;
    Node temp;
    while(graph[i]!=NULL){
        graph[i].color = 0;
        graph[i].parent = NULL;
        graph[i].detected = graph[i].finished = 0;
        graph[i].index = i;
        i++;
    }
    n = i;
    time = 0;
    graph[1] = temp;
    graph[1] = start;
    start = temp;    // just want to start at the beginning of the array
    while(i>=0){
        if(graph[i].color == 0)
            visitDFS(graphMatrix, graph, i, &time, n);
        i--;
    }
}

void visitDFS(int *graphMatrix, Node graph, int i, int *time, int length){
    graph[i].color = 1;    // grey, begin to visit
    graph[i].detected = ++(*time);
    for (int j=0; j
        if(graphMatrix[graph[i].index][j]!=0){
            if(graph[j].color == 0){
                graph[j].parent = &graph[i];
                visitDFS(graphMatrix, graph, j, time, length);
            }
        }
    }
    graph[i].color = 2;    // black, conclude the visiting
    graph[i].finished = ++(*time);
}

(to be continued)        
=========

reference: <Introduction to algorithms>