图的深度和广度遍历 BFS DFS

时间：2009-08-22 来源：ubuntuer

广度遍历,其实与树的层次遍历一样,先遍历每个节点的所有有关系的节点(就是有边连着的)!!每遍历这么一个节点都需要把这个节点入队列....再从队列里取节点,重复上面的所有过程!!!! 深度遍历,大概就是回溯了,先一个节点走到底,在回溯!!!!

#include <stdio.h>
#include <stdlib.h>

#define QUEUE_MAX 10

int count = 0;

typedef struct list
{
  int num;//1-7

  struct list* next;
}LIST;

typedef struct queue
{
  int front;
  int rear;
  int num[QUEUE_MAX];
}QUEUE;

void init_queue(QUEUE* Q)
{
  Q->front = 0;
  Q->rear = 0;
}

int IS_EMPTY(QUEUE* Q)
{
  if(Q->rear==Q->front)
    return 1;
  else
    return 0;
}

int IS_FULL(QUEUE* Q)
{
  if((Q->rear+1)%QUEUE_MAX==Q->front)
    return 1;
  else
    return 0;
}

void en_queue(QUEUE* Q, int num)
{
  if(IS_FULL(Q))
    return;

  Q->num[Q->rear] = num;
  Q->rear = (Q->rear+1)%QUEUE_MAX;
}

int de_queue(QUEUE* Q)
{
  if(IS_EMPTY(Q))
    return -1;

  int num;
  num = Q->num[Q->front];
  Q->front = (Q->front+1)%QUEUE_MAX;

  return num;
}

void init_list_head(LIST** L)
{
  *L = (LIST*)malloc(sizeof(LIST));
  (*L)->num = 0;
  (*L)->next = NULL;
}

LIST* create_new_node()
{
  LIST* p = (LIST*)malloc(sizeof(LIST));
  p->num = 0;
  p->next = NULL;

  return p;
}

void add_new_node(LIST* L, LIST* p)
{
  p->next = L->next;
  L->next = p;
}

int create_adjacency_matrix( LIST* L[7], int A[7][7])
{
   int i;
   int j;

  for(i=0;i<7;i++)
   {
    init_list_head(&L[i]);
    for(j=0;j<7;j++)
     {
       if(A[i][j]!=0)
       {
         LIST* p = create_new_node();
         p->num = j+1;
         add_new_node(L[i], p);
       }
     }
   }
}

void print_adjacency_matrix(LIST* L[7])
{
  int i;
  LIST* p = NULL;
  for(i=0;i<7;i++)
   {
     p = L[i]->next;

     if(p!=NULL)
       printf("%d:\t",i+1);
     else
      {
       printf("%d:\n",i+1);
       continue;
      }

     while(p!=NULL)
      {
       if(p->next!=NULL)
        printf("%d->",p->num);
       else
        printf("%d\n",p->num);

        p = p->next;
      }
   }
}

int* bfs(LIST* L[7], int num)
{
  QUEUE* Q = (QUEUE*)malloc(sizeof(QUEUE));
  init_queue(Q);
  en_queue(Q,num);
  int currdist = 0;
  int flag = 0;
  int i = 0;
  int ret = 0;
  int* bfs = (int*)malloc(sizeof(int)*7);

  int known[7];
  for(i=0;i<7;i++)
   {
    bfs[i] = 0;
    known[i] = 0;
    }

  bfs[flag++] = num;
  for(i=0;i<7;i++)
  {

   ret = de_queue(Q);
   LIST* p = L[ret-1]->next;
   if(p == NULL)
    continue;

   while(p!=NULL)
   {
     en_queue(Q,p->num);
     if(known[p->num-1] == 0)
      {
       bfs[flag++] = p->num;
       known[p->num-1] = 1;
      }
     p = p->next;
     if(flag == 7)
      return bfs;
    }
  }
}

int count_dfs(LIST* L[7], int visit[7], int dfs[7], int num)
{
  //printf("num is %d, start is %d\n", num, count);

  //printf("visited %d\n", num);


  if(count>=7)
    return 0;

  visit[num-1] = 1;
  dfs[count++] = num;

  LIST* p = L[num-1]->next;
  while(p!=NULL)
   {
     if(visit[p->num-1]==0)
      count_dfs(L, visit, dfs, p->num);

     p = p->next;
   }
}

void print_array(int dist[], int n)
{
  int i;
  for(i=0;i<n;i++)
   {
     printf("%d\n", dist[i]);
   }
}

int main(int argc, char *argv[])
{
  int A[7][7] = {
                  {0,1,0,1,0,0,0},
                  {0,0,0,1,1,0,0},
                  {1,0,0,0,0,1,0},
                  {0,0,1,0,1,1,1},
                  {0,0,0,0,0,0,1},
                  {0,0,0,0,0,0,0},
                  {0,0,0,0,0,1,0}
                 };

  LIST** L = (LIST**)malloc(sizeof(LIST)*7);

  create_adjacency_matrix( L, A);
  print_adjacency_matrix(L);


  int* dist = bfs(L, 3);
  printf("graph bfs is:\n");
  print_array(dist, 7);

  int visit[7] = {0,0,0,0,0,0,0};
  int dfs[7] = {0,0,0,0,0,0,0};
  count_dfs(L, visit, dfs, 3);
  printf("graph dfs is:\n");
  print_array(dfs, 7);

  system("PAUSE");
  return 0;
}