// 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);
}
=========
reference: <Introduction to algorithms>
