f*****y
发帖数: 444 | 1 I am preparing algorithm, wrote the following algorithm. Share with you. Not
sure whether it is a duplicate post or not.
//---- Breadth Fast Search algorithm ---
// circular queue
int head = 0;
int tail = 0;
#define Q_EMPTY (head==tail)
#define Q_FULL ((tail-head+1)%SIZE==0)
#define SIZE 10
struct Node* q[SIZE];
void put(struct Node* x)
{
if (x==NULL) return;
if (Q_FULL) return; //queue full
q[tail] = x;
tail = (tail+1) % SIZE;
return;
}
struct Node* get()
{
if (Q_EMPTY) return NULL;
head %= SIZE;
return q[head++];
}
// breadth first search
void bfs(struct Node* root)
{
struct Node* n;
printf("breadth first search of tree:\t");
// get the ball rolling..
put(root);
while ( n=get()) {
// visit each node in queue
printf("%d ",n->i);
// push children to queue
put(n->left);
put(n->right);
}
printf("\n");
}
// push down stack
int top=0;
void push(struct Node* x)
{
if (x==NULL) return;
if (top
}
struct Node* pop()
{
if (top>0) return q[--top];
else return NULL;
}
// --- depth first search ---
void dfs(struct Node* root)
{
struct Node* n;
printf("depth first search of tree:\t");
// get the ball rolling..
push(root);
while ( n=pop()) {
// visit each node in stack
printf("%d ",n->i);
// push children to stack
push(n->right);
push(n->left);
}
printf("\n");
} |
y*******g
发帖数: 6599 | 2 bsf和dfs不是一般用来search graph嘛？
Not
【在 f*****y 的大作中提到】
: I am preparing algorithm, wrote the following algorithm. Share with you. Not
: sure whether it is a duplicate post or not.
: //---- Breadth Fast Search algorithm ---
: // circular queue
: int head = 0;
: int tail = 0;
: #define Q_EMPTY (head==tail)
: #define Q_FULL ((tail-head+1)%SIZE==0)
: #define SIZE 10
: struct Node* q[SIZE];
|
c******t
发帖数: 1500 | 3 BFS在CLRS上的解法就不是recursion呀
DFS是的，因为用到了stack |
i**********e
发帖数: 1145 | 4 DFS visits the leaf first before visiting its parent.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
Not
【在 f*****y 的大作中提到】
: I am preparing algorithm, wrote the following algorithm. Share with you. Not
: sure whether it is a duplicate post or not.
: //---- Breadth Fast Search algorithm ---
: // circular queue
: int head = 0;
: int tail = 0;
: #define Q_EMPTY (head==tail)
: #define Q_FULL ((tail-head+1)%SIZE==0)
: #define SIZE 10
: struct Node* q[SIZE];
|
f*****y
发帖数: 444 | 5 binary tree is graph, right? I was trying to demo the concept..
【在 y*******g 的大作中提到】
: bsf和dfs不是一般用来search graph嘛？
:
: Not
|
f*****y
发帖数: 444 | 6 thanks for pointing this out.
【在 i**********e 的大作中提到】
: DFS visits the leaf first before visiting its parent.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: Not
|
y*******g
发帖数: 6599 | 7 input表达完全不一样
【在 f*****y 的大作中提到】
: binary tree is graph, right? I was trying to demo the concept..
|
