#include <stdio.h> typedef  int  datatype;   /*假定线性表元素的类型为整型*/ #define  maxsize  1024    /*假定线性表的最大长度为1024*/ # define n 100            /* 图的顶点最大个数 */ typedef char VEXTYPE;  /* 顶点的数据类型 */ typedef float ADJTYPE;  /* 权值类型 */ typedef struct {  VEXTYPE vexs[n] ;  /* 顶点信息数组 */     ADJTYPE arcs[n][n] ; /* 边权数组 */     int num ;    /* 顶点的实际个数 */ }GRAPH; /***********************1。置空图**********************/ void GraphInit(GRAPH  *L) {  L->num=0; } /***********************2。求结点数**********************/ int GraphVexs(GRAPH  *L) {  return(L->num); } /***********************3。创建图**********************/ void GraphCreate(GRAPH  *L) {  int i,j;  GraphInit(L);  printf("请输入顶点数目：");  scanf("%d",&L->num);  printf("请输入各顶点的信息(单个符号）：");  for(i=0;i<L->num;i++)  {   fflush(stdin);   scanf("%c",&L->vexs[i]);  }  printf("请输入边权矩阵的信息：");  for(i=0;i<L->num;i++)  {   for(j=0;j<L->num;j++)   {    scanf("%f",&L->arcs[i][j]);   }  }  printf("图已经创建完毕！"); } /***********************4。图的输出**********************/ void GraphOut(GRAPH  L) {   int i,j;   printf("\n图的顶点数目为：%d",L.num);   printf("\n图的各顶点的信息为：\n");   for(i=0;i<L.num;i++)   printf("%c  ",L.vexs[i]);   printf("\n图的边权矩阵的信息为：\n");   for(i=0;i<L.num;i++)   {     for(j=0;j<L.num;j++)     {     printf("%6.2f ",L.arcs[i][j]);     }     printf("\n");   }   printf("图已经输出完毕！"); } /***********************5。图的深度周游**********************/ void DFS(GRAPH  g,int qidian,int mark[]) //从第qidian个点出发深度优先周游图g中能访问的各个顶点 {   int v1;   mark[qidian]=1;   printf("%c   ",g.vexs[qidian]);   for(v1=0;v1<g.num;v1++)   {    if(g.arcs[qidian][v1]!=0&&mark[v1]==0)    DFS(g,v1,mark);   } } /***********************6。图的深度周游**********************/ void GraphDFS(GRAPH  g) //深度优先周游图g中能访问的各个顶点 {  int qidian,v,v1,mark[maxsize];  printf("\n深度周游：");  printf("\n请输入起点的下标：");  scanf("%d",&qidian);  for(v=0;v<g.num;v++)  {   mark[v]=0;  }  for(v=qidian;v<g.num+qidian;v++)  {   v1=v%g.num;   if(mark[v1]==0)    DFS(g,v1,mark);  } } typedef  int DATATYPE;     //队列元素的数据类型 typedef  struct {   DATATYPE data[maxsize]; //队中元素    int front,rear;   //队头元素下标、队尾元素后面位置的下标 } SEQQUEUE; /*****************************************************************************/ void QueueInit(SEQQUEUE *sq) //将顺序循环队列sq置空（初始化） {    sq->front=0;    sq->rear=0; } /*****************************************************************************/ int QueueIsEmpty(SEQQUEUE sq) //如果顺序循环队列sq为空，成功返回1，否则返回0 {    if (sq.rear==sq.front)       return(1);    else       return(0); } /*****************************************************************************/ int QueueFront(SEQQUEUE sq,DATATYPE *e) //将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0 {  if (QueueIsEmpty(sq))     { printf("queue is empty!\n");return 0;}     else     { *e=sq.data[(sq.front)]; return 1;} } /*****************************************************************************/ int QueueIn (SEQQUEUE *sq,DATATYPE x) //将元素x入队列sq的队尾，成功返回1，失败返回0 {  if (sq->front==(sq->rear+1)%maxsize)  {    printf("queue is full!\n");   return 0;  }  else  {     sq->data[sq->rear]=x;   sq->rear=(sq->rear+1)%maxsize;   return(1);  } } /*****************************************************************************/ int QueueOut(SEQQUEUE *sq) //将队列sq队首元素出队列，成功返回1,失败返回0 {     if (QueueIsEmpty(*sq))     {    printf("queue is empty!\n");   return 0;  }     else     {          sq->front=(sq->front+1)%maxsize;   return  1;     } } /***********************7。图的广度周游**********************/ void BFS(GRAPH g,int v,int mark[]) //从v出发广度优先周游图g中能访问的各个顶点 {   int v1,v2;   SEQQUEUE q;   QueueInit(&q);   QueueIn(&q,v);   mark[v]=1;   printf("%c   ",g.vexs[v]);   while(QueueIsEmpty(q)==0)    {     QueueFront(q,&v1);     QueueOut(&q);     for(v2=0;v2<g.num;v2++)     {       if(g.arcs[v1][v2]!=0&&mark[v2]==0)       {      QueueIn(&q,v2);      mark[v2]=1;      printf("%c   ",g.vexs[v2]);       }      }   } } /***********************8。图的广度周游**********************/ void GraphBFS(GRAPH  g) //深度优先周游图g中能访问的各个顶点 {  int qidian,v,v1,mark[maxsize];  printf("\n广度周游：");  printf("\n请输入起点的下标：");  scanf("%d",&qidian);  for(v=0;v<g.num;v++)  {   mark[v]=0;  }  for(v=qidian;v<g.num+qidian;v++)  {   v1=v%g.num;   if(mark[v1]==0)    BFS(g,v1,mark);  } } /***********************主函数**********************/ void main() {  GRAPH tu;  GraphCreate(&tu);  GraphOut(tu);  GraphDFS(tu);  GraphBFS(tu); }