sy7_3.c

数据结构实验与学习指导

#include "cg.h"   /*引入包含图的存储实现的头文件，文件内容见本章实验一*/
int visited[VERTEX_MAX]={0};   /*标志向量*/
/*====存储结构为邻接矩阵的无向图的深度优先和广度优先遍历====*/
void  DFSTraverseM(MGraph *G,int i)
 /*从i结点开始深度优先遍历以邻接矩阵存储的图G*/
{ int j;
   printf("->%s",G->vexs[i]);
   visited[i]=1;           /*标志向量初始化*/
   for (j=0;j<G->vexnum;j++)
    if ((G->arcs[i][j]==1)&&(!visited[j]))
     DFSTraverseM(G,j);      /*Vj未访问，从Vj开始DFS搜索*/
}
void Bfs_TraverseM(MGraph *G ,int k)  /* 从k结点开始广度优先遍历图*/
{
  int qu[20],f=0,r=0,i,j;    /*由qu[20]、f和r组成队列*/
  printf("->%s",G->vexs[k]);     /*访问Vk*/
  visited[k]=1;
  qu[r]=k; r++;           /*结点Vk入队*/
  while(r!=f)
  {
    i=qu[f];f++;   /*出队操作*/
    for (j=0;j<G->vexnum;j++) /*依次搜索Vi的邻接点Vj*/
    if (G->arcs[i][j]==1 && !visited[j]) /*若Vj未访问*/
    {  printf("->%s",G->vexs[j]);
       visited[j]=1;
       qu[r]=j; r++;
     } /*访问过的Vj入队列*/
  }
}
/*====存储结构为邻接表的无向图的深度优先和广度优先遍历====*/
void DFSTraverseAL(ALGraph *G,int i)  /*从i结点开始图的深度优先遍历*/
{ EdgeNode *p;
  printf("->%s",G->adjlist[i].vertex);
  visited[i]=1;
  p=G->adjlist[i].firstedge;
  while(p!=NULL)
  { if(visited[p->adjvex]==0)
      DFSTraverseAL(G,p->adjvex);
        /*v[p->adjvex]未访问，从v[p->adjvex]开始DFS搜索*/
    p=p->next;
   }
 }
void BFSTraverseAL(ALGraph *G ,int k)  /*从k结点开始广度优先遍历图*/
{
  int qu[20],f=0,r=0,i,j;
  EdgeNode *p;
  printf("->%s",G->adjlist[k].vertex);     /*访问Vk*/
  visited[k]=1;
  qu[r]=k; r++;           /*结点Vk入队*/
  while(r!=f)
  {
    i=qu[f];f++;    /*出队操作*/
    p=G->adjlist[i].firstedge;
    while(p)
    {
       if(visited[p->adjvex]==0)
       {
         printf("->%s",G->adjlist[p->adjvex].vertex);
         visited[p->adjvex]=1;
         qu[r]=p->adjvex; r++;   /*访问过的v[p->adjvex]入队列*/
       }
       p=p->next;
    }
  }
}
void intvisited()   /*置visited数组为0*/
{
   int i;
   for (i=0;i<VERTEX_MAX;i++)
     visited[i]=0;
   }
main()
{
  MGraph *g;
  ALGraph *g2;
  int i,fg1,fg2;
  do
  {
   printf("请选择存储结构  1:MGraph（邻接矩阵）  2:ALGraph（邻接表）  0:退出程序\n");
       /*选择存储结构*/
   printf("请选择操作0~2: ");
   scanf("%d",&fg1);
   if(fg1==1 ||fg1==2)     /*图的不同存储结构实现 */
   {
     if(fg1==1)
       {
         g=(MGraph *)malloc(sizeof(MGraph));   
         creat_MGraph1(g);  /*创建图的邻接矩阵*/
       }
      else
      {
         g2=(ALGraph *)malloc(sizeof(ALGraph));
         CreateALGraph1(g2);     /*创建图的邻接表*/
      }
     do
     {
       printf("请选择遍历方式：0:退出程序  1:DFS（深度优先）  2:BFS（广度优先）\n");  /*选择遍历方式*/
       printf("请选择操作0~2: ");
       scanf("%d",&fg2);
       switch(fg2)
        {
          case 0:break; /*退出*/
          case 1:printf("请输入开始结点: "); /*深度优先遍历*/
            scanf("%d",&i);
            intvisited();  /*置visited数组为0*/
            if (fg1==1)
              DFSTraverseM(g,i);
            else DFSTraverseAL(g2,i);
            printf("\n");
            break;
          case 2:printf("请输入开始结点: ");    /*广度优先遍历*/
            scanf("%d",&i);
            intvisited();
            if(fg1==1)
               Bfs_TraverseM(g,i);
            else BFSTraverseAL(g2,i);
            printf("\n");
            break;
          default:printf("输入错误，请重新选择操作!\n");
            break;
      } /*end switch*/
     }while(fg2!=0);
   }
 } while (fg1!=0);
}