P.Linux Laboratory

本文内容遵从CC版权协议, 可以随意转载, 但必须以超链接形式标明文章原始出处和作者信息及版权声明
网址: http://www.penglixun.com/tech/program/bfs_programing.html

前些天被人问到BFS的递归怎么写，思维定式给想成DFS了，今天晚上正好有空练练手，多写代码，防止老年痴呆。
用递归，QUEUE，多线程都写了一遍。

#include 
#include 
#include 
#include 
#include 

/* For @RETURN */
#define TREE_FULL 2
#define TREE_ERROR 1
#define TREE_SUCCESS 0

/* For Tree */
#define TREE_LEVEL 4
#define IS_LEAF_NODE(A) (A->left_node== NULL ||  A->right_node== NULL)

/* For QUEUE */
#define QUEUE_LEN     64
#define QUEUE_INIT    (queue_front=0, queue_rear=0, memset(queue,0,QUEUE_LEN*sizeof(tree_t*)))
#define QUEUE_PUT(A)  queue[queue_front++ % QUEUE_LEN]= A
#define QUEUE_POP     queue[queue_rear++ % QUEUE_LEN]
#define QUEUE_FULL    ((queue_front-queue_rear)>= QUEUE_LEN-1)
#define QUEUE_EMPTY   (queue_front== queue_rear)

#define QUEUE_PUT_PTHREAD(A) pthread_mutex_lock(&queue_mtx);QUEUE_PUT(A);pthread_mutex_unlock(&queue_mtx);
#define QUEUE_POP_PTHREAD(A) pthread_mutex_lock(&queue_mtx);A= QUEUE_POP;pthread_mutex_unlock(&queue_mtx);

/* Binary Tree Struct */
typedef struct tree_struct tree_t;
struct tree_struct {
  int value;
  int level;
  tree_t* left_node;
  tree_t* right_node;
};

/* FIFO Queue */
tree_t* queue[QUEUE_LEN];
int queue_front= 0;
int queue_rear= 0;

/* Multi-Thread */
pthread_mutex_t queue_mtx= PTHREAD_MUTEX_INITIALIZER;  

/* Initialize Binary Tree using Recursion */
int recursion_init_node (tree_t *node, int level)
{
  if (node== NULL) 
    return TREE_ERROR;

  node->value= rand()%10;
  node->level= level;
  printf("Level: %d, Value: %d\n", level, node->value);
  if (level>= TREE_LEVEL) 
  {
    node->left_node= NULL;
    node->right_node= NULL;
    return TREE_FULL;
  }
  node->left_node= (tree_t *)malloc(sizeof(tree_t));
  node->right_node= (tree_t *)malloc(sizeof(tree_t));

  ++level;
  recursion_init_node(node->left_node, level);
  recursion_init_node(node->right_node, level);

  return TREE_SUCCESS;
}

/* Visit Tree of BFS using Recursion */
int recursion_visit_tree (int level) 
{
  if (level> TREE_LEVEL)
    return TREE_FULL;
  printf("Level%d: ", level);

  int i= 0;
  tree_t* tmp[QUEUE_LEN];
  while (!QUEUE_EMPTY) {
    tree_t* node= QUEUE_POP;
    printf("| Value: %d |", node->value);

    if (IS_LEAF_NODE(node))
      continue;

    tmp[i++]= node->left_node;
    tmp[i++]= node->right_node;
  }
  printf("\n");

  int j;
  for(j =0; jlevel) {
      level= node->level;
      printf("\nLevel%d: ", level);
    }
    printf("| Value: %d |", node->value);

    if (IS_LEAF_NODE(node)) 
      continue;
    QUEUE_PUT(node->left_node);
    QUEUE_PUT(node->right_node);
  }
  printf("\n");
  return TREE_SUCCESS;
}

/* Visit Tree of BFS using Multi-Thread */
void* visit_node_func(void* node)
{
  tree_t* tree_node= (tree_t *)node;
  printf("| Value: %d |", tree_node->value);
  if (!IS_LEAF_NODE(tree_node)) {
    QUEUE_PUT_PTHREAD(tree_node->left_node);
    QUEUE_PUT_PTHREAD(tree_node->right_node);
  }
}

int concurrency_visit_tree(tree_t* root_node) 
{
  pthread_t tid[QUEUE_LEN];
  tree_t* node;
  int level= 0;

  QUEUE_PUT(root_node);
  while (!QUEUE_EMPTY) {
    printf("Level%d: ", level++);

    pthread_mutex_lock(&queue_mtx);
    int count= 0;
    while (!QUEUE_EMPTY) {
      node= QUEUE_POP;
      pthread_create(&tid[count++], NULL, visit_node_func, (void *)node);
    }
    pthread_mutex_unlock(&queue_mtx);

    int i= 0;
    for(i=0; i< count; ++i)
      pthread_join(tid[i], NULL);

    printf("\n");
  }
}

/* Main */
int main(int argc, char *argv[])
{
  srand((unsigned)time(0));

  printf("== Init Tree ==\n");
  tree_t* tree= (tree_t *)malloc(sizeof(tree_t));
  recursion_init_node(tree, 0);

  printf("== Recursion Visit BFS Tree ==\n");
  QUEUE_INIT;
  QUEUE_PUT(tree); 
  recursion_visit_tree(0);

  printf("== Queue Visit BFS Tree ==\n");
  QUEUE_INIT;
  queue_visit_tree(tree);

  printf("== Multi-Thread Visit BFS ==\n");
  QUEUE_INIT;
  concurrency_visit_tree(tree);
}

== Init Tree ==
Level: 0, Value: 0
Level: 1, Value: 9
Level: 2, Value: 1
Level: 3, Value: 7
Level: 4, Value: 7
Level: 4, Value: 4
Level: 3, Value: 0
Level: 4, Value: 9
Level: 4, Value: 5
Level: 2, Value: 1
Level: 3, Value: 6
Level: 4, Value: 9
Level: 4, Value: 5
Level: 3, Value: 3
Level: 4, Value: 9
Level: 4, Value: 3
Level: 1, Value: 9
Level: 2, Value: 9
Level: 3, Value: 1
Level: 4, Value: 2
Level: 4, Value: 1
Level: 3, Value: 6
Level: 4, Value: 2
Level: 4, Value: 4
Level: 2, Value: 0
Level: 3, Value: 2
Level: 4, Value: 5
Level: 4, Value: 5
Level: 3, Value: 3
Level: 4, Value: 2
Level: 4, Value: 2
== Recursion Visit BFS Tree ==
Level0: | Value: 0 |
Level1: | Value: 9 || Value: 9 |
Level2: | Value: 1 || Value: 1 || Value: 9 || Value: 0 |
Level3: | Value: 7 || Value: 0 || Value: 6 || Value: 3 || Value: 1 || Value: 6 || Value: 2 || Value: 3 |
Level4: | Value: 7 || Value: 4 || Value: 9 || Value: 5 || Value: 9 || Value: 5 || Value: 9 || Value: 3 || Value: 2 || Value: 1 || Value: 2 || Value: 4 || Value: 5 || Value: 5 || Value: 2 || Value: 2 |
== Queue Visit BFS Tree ==
Level0: | Value: 0 |
Level1: | Value: 9 || Value: 9 |
Level2: | Value: 1 || Value: 1 || Value: 9 || Value: 0 |
Level3: | Value: 7 || Value: 0 || Value: 6 || Value: 3 || Value: 1 || Value: 6 || Value: 2 || Value: 3 |
Level4: | Value: 7 || Value: 4 || Value: 9 || Value: 5 || Value: 9 || Value: 5 || Value: 9 || Value: 3 || Value: 2 || Value: 1 || Value: 2 || Value: 4 || Value: 5 || Value: 5 || Value: 2 || Value: 2 |
== Multi-Thread Visit BFS ==
Level0: | Value: 0 |
Level1: | Value: 9 || Value: 9 |
Level2: | Value: 1 || Value: 1 || Value: 9 || Value: 0 |
Level3: | Value: 7 || Value: 6 || Value: 1 || Value: 6 || Value: 2 || Value: 3 || Value: 3 || Value: 0 |
Level4: | Value: 7 || Value: 4 || Value: 9 || Value: 5 || Value: 2 || Value: 1 || Value: 2 || Value: 4 || Value: 5 || Value: 5 || Value: 2 || Value: 2 || Value: 9 || Value: 3 || Value: 9 || Value: 5 |