ch6_2.c

本内容为清华大学严蔚敏版数据结构部分算法实现代码

#include <stdio.h>
#include <stdlib.h>
#define QUEUE_SIZE 10                        /* 队列的大小 */
typedef struct node                   /* 声明结点为结构变量 */
{
  int vertex;                                  /* 结点的编号 */
  struct node *nextnode;             /* 指向下一结点的地址 */
}Node;
Node head[9];                              /* 声明头结点数组 */
int visited[9];                                 /* 走访记录 */
int Q[QUEUE_SIZE];                        /* 声明队列为数组 */
int front=-1;                                  /* 队列的前端 */
int rear=-1;                                   /* 队列的后端 */
void Graph(int node[][2], int);
int ADDQ(int);
int DELETEQ(void);
void BFS(int);
void main( )
{
  Node *W;
                                           /* 记录所有边的数组 */
  int node[20][2]={{ 1, 2 }, { 2, 1},
                   { 1, 3 }, { 3, 1 },
                   { 2, 4 }, { 4, 2 },
                   { 2, 5 }, { 5, 2 },
                   { 3, 6 }, { 6, 3 },
                   { 3, 7 }, { 7, 3 },
                   { 4, 8 }, { 8, 4},
                   { 5, 8 }, { 8, 5 },
                   { 6, 8 }, { 8, 6 },
                   { 7, 8 }, { 8, 7 }};
  int i;
  for(i=1; i<=8; i++)
  {
    head[i].vertex=i;                         /* 建立首结点 */
    head[i].nextnode=NULL;
    visited[i]=0;
  }
  Graph(node, 20);                           /* 建立图形 */
  printf("图的邻接表内容如下:\n");
  for(i=1; i<=8; i++)
  {
    printf("V%d=>", head[i].vertex);
    W=head[i].nextnode;
    while(W != NULL)                     /* 走访至链表的最后面 */
    {
      printf("%d ", W->vertex);
      W=W->nextnode;
    }
    printf("\n");
  }
  printf("图广度优先搜索的顺序:\n");                /* 输出走访过程 */ 
  BFS(1);
  printf("\n");
}

void Graph(int node[][2], int num)                    /* 建立图形 */
{
  Node *newnode;                               /* 新结点指标 */
  Node *ptr;
  int from;                                           /* 起点 */
  int to;                                             /* 终点 */
  int i;
  for(i=0; i<num; i++)
  {
    from=node[i][0];
    to =node[i][1];
    newnode=(Node *)malloc(sizeof(Node));          /* 建立新结点 */
    newnode->vertex=to;
    newnode->nextnode=NULL;
    ptr=&(head[from]);
    while(ptr->nextnode != NULL)              /* 走访至链表的最后 */
    ptr=ptr->nextnode;                       /* 将边加到链表中 */
    ptr->nextnode=newnode;
  }
}

int ADDQ(int item)                             /* 加入数据 */
{
  if(rear >= QUEUE_SIZE)            /* 检查队列是否已满了 */ 
    return -1;
  rear++;                      /* 将rear指向数据加入的位置 */
  Q[rear]=item;                         /* 将数据存入队列中 */
}

int DELETEQ(void)                              /* 取出数据 */
{
  if(front == rear)                     /* 检查队列是否为空的 */
    return -1;
  front++;                  /* 将front指向数据被删除的位置 */
  return Q[front];                   /* 将被取出的数据返回 */
}

void BFS(int V)                              /* 广先搜寻法 */
{
  Node *W;
  ADDQ(V);                                 /* 将顶点存入队列 */
  visited[V]=1;                           /* 记录已遍历过的顶点 */
  printf("V%d ", V);
  while(front != rear)                        /* 检查队列是否为空 */
  {
    V=DELETEQ( );                       /* 将数据从队列取出 */
    W=head[V].nextnode;
    while(W != NULL)
    {
      if(visited[W->vertex] == 0)    /* 若未遍历过，则调用DFS子程序 */
      {
        ADDQ(W->vertex);
        visited[W->vertex]=1;
        printf("V%d ", W->vertex);
      }
      W=W->nextnode;
    }
  }
}