tu.c

本程序用于数据结构中关于图部分的广度优先搜索和深度优先搜索。

#include "stddef.h"
#include "stdlib.h"
#include "stdio.h"
#include "alloc.h"
/*#include*/
#define FALSE 0
#define TRUE 1
#define MAX  100
 
typedef struct node_e            /*定义表边结点类型*/
{
   int index;                   /*定义表边结点的顶点序号*/
    struct node_e *next_e;       /*指向下一个表边结点的指针*/
}node_e;
typedef struct node_v            
{
   char data;                   /*顶点的数据信息*/
    struct node_e *first_e;      /*指向第一个表结点*/
}node_v;
typedef struct{
   int n,e;                     /*顶点数和边数*/
    node_v adjlist[MAX];         /*邻接表*/
}ALGraph;                        /*ALGraph是以邻接表方式存储的图的类型*/
typedef struct
{
   char vexs[MAX];              /*顶点表*/
    int edges[MAX][MAX];         /*邻接矩阵*/
    int n, e;                    /*顶点数和边数*/
}MGraph;                         /*MGraph是以邻接矩阵存储的图的类型*/
 
int visited[MAX];                /*全局数组*/
 
void CreateMGraph(MGraph *G);    /*图的邻接矩阵的建立*/
void DEG(MGraph *G);             /*求图中每个顶点的度*/
void DFSTraverseM(MGraph *G);    /*图的深度优先遍历*/
void DFSM(MGraph *G, int i);     
void BFSTraverseM(MGraph *G);    /*图的广度优先遍历*/
void BFSM(MGraph *G, int i);              
void MDelVex(MGraph *G);         /*删除图的一个顶点*/
void CUGSM(MGraph *G);           /*判断图的连通性*/
void change(MGraph *G);          /*将图的邻接矩阵存储变为邻接表存储*/
void FirstTree(MGraph *G);       /*图的深度和广度优先生成树*/
 
typedef struct
{
   int front;                   /*队头指针*/
    int rear;                    /*对尾指针*/
    int count;                   /*队中元素的个数*/
    char data[MAX];              /*数据的存储区*/
}CirQueue;                       /*循环队列*/
void InitQueue(CirQueue *Q)      /*置空队*/
{
   Q->front=Q->rear=0;
    Q->count=0;
}
int QueueEmpty(CirQueue *Q)      /*队空*/
{
   return Q->count==0;
}
int QueueFull(CirQueue *Q)       /*队满*/
{
   return Q->count==MAX;
}
void EnQueue(CirQueue *Q,char x) /*入队*/
{ 
   if(QueueFull(Q))
     printf("Queue overflow");
   else{
     Q->count++;
        Q->data[Q->rear]=x;
        Q->rear=(Q->rear+1)%MAX;
   }
}
int DeQueue(CirQueue *Q)         /*出队*/
{
   int temp;
    if(QueueEmpty(Q)){
   printf("Queue underflow");
     return NULL;
   }else
   {
     temp=Q->data[Q->front];
        Q->count--;
        Q->front=(Q->front+1)%MAX;
        return temp;
   }
}
 
void main()
{
   MGraph *G,a;
   char ch1;
    int i,j,ch2;
    G=&a;
 
    printf("\n\t\t建立邻接矩阵\n");
    CreateMGraph(G);
    printf("\n\t\t已建立\n\t\t");
    for(i=0; in;i++){
     for(j=0;j n;j++)
        printf("%5d",G->edges[i][j]);
            printf("\n\t\t");
   }
   getchar();
    ch1='y';
   while(ch1=='y'||ch1=='Y'){
     printf("\n\n\n\n\n\t\t菜单选项\n");
        printf("\t\t                                            \n");
       
    
     printf("\t\t*1*************新建一个邻接矩阵*************\n");
     printf("\t\t*2*************求图的每个顶点的度***********\n");
        printf("\t\t*3*************深度优先遍历*****************\n");
     printf("\t\t*4*************广度优先遍历*****************\n");
     printf("\t\t*5*************删除图的一个顶点*************\n");
     printf("\t\t*6*************判断该图是否连通*************\n");
    printf("\t\t*7*************将邻接矩阵转换为邻接表*******\n"); 
     printf("\t\t*8*************图G的深度和广度优先生成树****\n");
     printf("\t\t*9*************退出************************\n");   
    
     printf("\t\t                                            \n");
        printf("\t\t请选择菜单号(1--9):");
     scanf("%d", &ch2);
     getchar();
     switch(ch2){
             case 1: CreateMGraph(G);
             printf("\t\t\建立完毕.\n");
                break;
                case 2: DEG( G );       break;
                case 3: DFSTraverseM(G);break;
          case 4: BFSTraverseM(G);break;
                 case 5: MDelVex(G);     break;
                 case 6: CUGSM(G);       break;
          case 7: change(G);      break;
             case 8: FirstTree(G);   break;
          case 0: ch1='n';        break;
                default: printf("\t\t输入错误！请重新输入！\n");
     }
   }
}
 
void CreateMGraph(MGraph *G)
{
   int i,j,k;
    char ch1,ch2;
    printf("\t\t请输入顶点数,边数:\n\t\t");
    scanf("%d,%d",&(G->n),&(G->e));
    printf("\t\t请输入顶点信息:\n");
   for(i = 0;in;i++){
     getchar();
     printf("\t\t");
     scanf("%c",&(G->vexs[i]));
  }
  for(i=0;in;i++)
     for(j=0;jn;j++)
       G->edges[i][j]=0;                         /*初始化矩阵*/
     printf("\t\t请输入每条边对应的两个顶点的序号:\n");
     for(k=0;ke;k++)                           /*输入e条边，建立邻接矩阵*/
     {
       getchar();
       printf("\t\t请输入第%d条边的顶点序号：",k+1);
       scanf("%c,%c",&ch1,&ch2);
       for(i=0;ch1!=G->vexs[i];i++);
          for(j=0;ch2!=G ->vexs[j];j++);{
            G->edges[i][j]=1;
            G->edges[j][i]=1;
          }
     }
   
}
void DFSTraverseM(MGraph *G)
{
  int i;
  for(i=0;in;i++)
     visited[i]=FALSE;
  for(i=0;in;i++)
     if(!visited[i])
       DFSM(G,i);
}
void BFSTraverseM(MGraph *G)
{
  int i;
  for(i=0;in;i++)
     visited[i]=FALSE;
  for(i=0;in;i++)
     if(!visited[i])
       BFSM(G,i);
}
void DFSM(MGraph *G,int i)
{
  int j;
    printf("\t\t深度优先遍历结点: 结点%c\n",G->vexs[i]);
    visited[i]=TRUE;
  for(j=0; jn;j++)
     if(G->edges[i][j]==1&&!visited[j])
       DFSM(G,j);
}
void BFSM(MGraph *G,int k)//使用一个队列实现BFS
{
  int i,j;
    CirQueue Q;
    InitQueue(&Q);
    printf("\t\t广度优先遍历结点:结点%c\n", G->vexs[k]);
    visited[k]=TRUE;
    EnQueue(&Q,k);
  while (!QueueEmpty(&Q)){
     i=DeQueue(&Q);
     for(j=0;jn;j++)
       if(G->edges[i][j]==1&&!visited[j]){
         printf("\t\t广度优先遍历结点:结点%c\n",G->vexs[j]);
         visited[j]=TRUE;
         EnQueue(&Q,j);
       }
  }
}
void DEG(MGraph *G)/*求出每个顶点的度*/
{
  int i,j,k;
  for(i=0, k=0;in;i++){
     for(j=0;jn;j++)
       if(G->edges[i][j])
         k++;
       printf("\t\t顶点%c的度为: %d\n", G->vexs[i],k);
       k=0;
  }
}
 
void MDelVex(MGraph *G)
{
    int i=-1;
  int j,k,m,p;
  char x;
  printf("\t\t请输入要删除的顶点: ");
  scanf("%c", &x);
    for(p=0;pn;p++)        
     if(x==G->vexs[p])
       i=p;
   if(i<0||i>=G->n)
     printf("\t\t顶点%c不存在!",x);
  m=0;
  for(j=0;jn;j++){
     if(G->edges[i][j])
       m++;
     if(G->edges[j][i])
       m++;
  }
  G->e=G->e-m/2;
  for(j=i+1;jn;j++)
     for( k=0; kn; k++){
       G->edges[j-1][k]=G->edges[j][k];
       G->edges[k][j-1]=G->edges[k][j];
     }
  for(j=i+1;jn;j++)
     G->vexs[j-1]=G->vexs[j];
  G->n--;
  if(i>=0&&in){
  printf("\t\t删除一个顶点后对图进行DFS的结果是:\n");
    DFSTraverseM(G);
  }
}
 
 
void CUGSM(MGraph *G)              /*判断图的连通性*/
{
  int i,count=0;                 /*计数变量，初值为0*/
  for(i=0;in;i++)
     visited[i]=FALSE;
  for(i=0;in;i++)            /*每调用一次DFS*/
     if(!visited[i]){           /*count加一*/
       count++;
          DFSM(G,i);
     }
     if(count==1){
       printf("\t\t%d次调用DFS\n",count);
       printf("\t\tOK!该图为连通图");
     }
     else{
       printf("\t\t%d次调用DFS",count);
       printf("\t\tNO!该图不连通");
     }
}
void MatTolist(MGraph *G, ALGraph * &g)
{
  int i,j,N=G->n;                               /*n为顶点数*/
    node_e *p;                  
  g=(ALGraph *)malloc(sizeof(ALGraph));
  for(i=0;i<>给邻接表中所有的头结点置初值
     g->adjlist[i].first_e=NULL;      
  for(i=0;i<>检查邻接矩阵的每个员素
     for(j=N-1;j>=0;j--)
       if(G->edges[i][j]!=0)                 /*邻接矩阵的当前元素不为0*/
       {
          p=(node_e*)malloc(sizeof(node_e));/*创建一个结点*p*/
         p->index=j;
         p->next_e=g->adjlist[i].first_e;  /*将*p链到链表后*/
         g->adjlist[i].first_e=p;
       }
       g->adjlist[i].data=G->vexs[i];        /*将邻接矩阵存储顶点信息存到邻接表中*/
  }
  g->n=N;
  g->e=G->e;
}
void DispAdj(ALGraph *g)
{
  int i;
    node_e *p;
 
  for(i=0;in;i++)
  {
     p=g->adjlist[i].first_e;
        if(p!=NULL)
       printf("\t\t%3c:",g->adjlist[i].data);//输出顶点Vi
        while(p)                    /*输出顶点心Vi的全部邻接顶点*/
     {
       printf("%3c,",g->adjlist[p->index].data);
            p=p->next_e;
     }
     putchar('\n');              /*换行*/
  }
}
void change(MGraph *G)                             
{
 
  ALGraph *g;
  g=(ALGraph *)malloc(sizeof(ALGraph));
  MatTolist(G,g);
  printf("\t\t图G的邻接表:\n");
  DispAdj(g);
}
void DFSTree(ALGraph *g, int v)   
{
  node_e *p;
  visited[v]=1;                   /*置已访问标记*/
  p=g->adjlist[v].first_e;        /*p指向顶点v的第一条边的头结点*/
 
  while(p!=NULL)
  {
     if(visited[p->index]==0)    /*若p->index顶点未访问，递归访问它*/
     {                           /*输出生成树的第一条边*/
       printf("<%c,%c>",g->adjlist[v].data,g->adjlist[p->index].data);
       DFSTree(g, p->index);
     }
     p=p->next_e;                /*p指向顶点v的下一条边的头结点*/
  }
}
void BFSTree(ALGraph *g, int v)
{
  node_e *p;
  int queue[MAX],front=0,rear=0;  /*定义循环队列并初始化*/
  int visited[MAX];               /*定义存放结点的标志性数组*/
  int w,i;
  for(i=0;in;i++)
     visited[i]=0;               /*访问标记初始化*/
  visited[v]=1;                   /*置已访问标记*/
  rear=(rear+1)%MAX;
  queue[rear]=v;                  /*v进队*/
    while(front!=rear)              /*若循环队列不空时循环*/ 
  {
     front=(front+1)%MAX;
     w=queue[front];             /*出队并赋给w*/
     p=g->adjlist[w].first_e;    /*找到与顶点w邻接的第一个顶点*/
     while(p!=NULL)
     {
       if(visited[p->index]==0)/*若当前邻接顶点未被访问*/
       {                       /*输出生成树的一条边*/
         printf("<%c,%c)",g->adjlist[w].data,g->adjlist[p->index].data);
         visited[p->index]=1;/*置该顶点已被访问*/
         rear=(rear+1)%MAX;  /*该顶点进队*/
         queue[rear]=p->index;
       }
       p=p->next_e;            /*找到下一个邻接顶点*/
     }
  }
}
void FirstTree(MGraph *G)
{
    int i;
  ALGraph *g;
  g=(ALGraph *)malloc(sizeof(ALGraph));
  MatTolist(G,g);
  for(i=0;in;i++)
     visited[i]=0;
  printf("\t\t深度优先生成树为:\n\t\t");
  DFSTree(g,0);
  printf("\n");
    for(i=0;in;i++)
     visited[i]=0;
  printf("\t\t广度优先生成树为:\n\t\t");
  }
 
 
 
 
 
 
    
 
输出结果：