yxCoding

I am a coder

深度优先搜索(DFS)和广度优先搜索(BFS)

yxjoey posted @ 2008年3月28日 09:15 in C语言 with tags c 程序 , 4357 阅读

简单来说

深度优先搜索用递归实现

  • 输出当前结点
  • 对于当前结点的所有子结点,依次递归运用深度优先搜索

广度优先搜索用队列实现

  • 将起始结点入队列
  • 循环(队列非空)
    • 取出一个结点
    • 输出结点内容
    • 将此结点的所有子结点入队列

代码:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct Node{
  5.   int value;
  6.   struct Node *left; 
  7.   struct Node *right;
  8. };
  9.  
  10. struct qNode{
  11.   struct Node *value;
  12.   struct qNode *next;
  13. };
  14.  
  15. struct Node *constructTree(int a[], int n){
  16.   struct Node *nodes = (struct Node *)malloc(n*sizeof(struct Node));
  17.   int i;
  18.   for(i=0; i<n; i++){
  19.     nodes[i].value = a[i] ;
  20.     nodes[i].left = (2*i+1<n)?&nodes[2*i+1]:NULL;
  21.     nodes[i].right = (2*i+2<n)?&nodes[2*i+2]:NULL;
  22.   }
  23.   return nodes;
  24. }
  25.  
  26. void dfs(struct Node *p){
  27.   printf("%d ", p->value);
  28.   if(p->left!=NULL)
  29.     dfs(p->left);
  30.   if(p->right!=NULL)
  31.     dfs(p->right);
  32. }
  33.  
  34. struct qNode* createqueue(){
  35.   struct qNode *p = (struct qNode*)malloc(sizeof(struct qNode));
  36.   p->value = NULL;
  37.   p->next = NULL;
  38.   return p;
  39. }
  40.  
  41. int isEmpty(struct qNode *queue){
  42.   return queue->next==NULL;
  43. }
  44.  
  45. void enqueue(struct qNode *queue, struct Node *node){
  46.   struct qNode *p = (struct qNode*)malloc(sizeof(struct qNode));
  47.   struct qNode *q = queue->next;
  48.   p->value = node;
  49.   p->next = q;
  50.   queue->next = p;
  51. }
  52.  
  53. struct Node* dequeue(struct qNode *queue){
  54.   if(isEmpty(queue))
  55.     return NULL;
  56.   struct qNode *p=queue,*q;
  57.   while(p->next!=NULL){
  58.     q = p;
  59.     p = p->next;
  60.   }
  61.   q->next =NULL;
  62.   return p->value;
  63. }
  64.  
  65. void bfs(struct Node *p){
  66.   struct qNode *queue = createqueue();
  67.   enqueue(queue, p);
  68.   while(!isEmpty(queue)){
  69.     struct Node *tmp = dequeue(queue);
  70.     printf("%d ", tmp->value);
  71.     if(tmp->left!=NULL)
  72.       enqueue(queue, tmp->left);
  73.     if(tmp->right!=NULL)
  74.       enqueue(queue, tmp->right);
  75.   }
  76. }
  77.  
  78. int main(int argc, char *argv[]){
  79.   int a[]={1,2,3,4,5,6,7,8,9,10};
  80.   struct Node *p = constructTree(a, sizeof(a)/sizeof(a[0]));
  81.   dfs(p);
  82.   printf("\n==================\n")
  83.   bfs(p);
  84.   printf("\n==================\n");
  85. }

其中还包含了一个用链表实现的队列,因为没有记录队列的尾结点,所有效率很低,每次出队列都要遍历真个链表。不过小程序用用可以了,哈哈

Avatar_small
bloody 说:
2011年4月22日 13:32

well coding, thanks...


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter