图 无向网 采用邻接矩阵存储结构 按深度优先搜索和广度优先搜索遍历图 （DFS,BFS）实验报告 数据结构

#include<stdio.h>
#include<stdlib.h>
#define MAXQSIZE 100//循环队列最大值 
#define OVERFLOW -2
#define FALSE 0
#define OK 1
#define MAX_VEX_NUM 20//图中最多20个顶点 
#define INFINITY 0 
typedef int Status;
typedef char ElemType;
typedef struct//图结构 
{
  ElemType vertex[MAX_VEX_NUM];//存顶点 
  Status arcs[MAX_VEX_NUM][MAX_VEX_NUM];//存边 
  Status vex_num,arc_num;// vex_num顶点数，arc_num边数 
}Mgraph;
typedef struct//循环队列结构 
{
  ElemType *base;
  int front;
  int rear;
}SqQueue;
//分配数组，将数组中的元素赋值为0 
bool visited[MAX_VEX_NUM];//深度优先搜索的辅助数组 
bool Qvisited[MAX_VEX_NUM];//广度优先搜索的辅助数组 
//定位边的节点 
Status LocateVex(Mgraph g,ElemType v)
// 从键盘中输入结点值，定位的作用是找到结点在 vertex数组中的下标 
{
  Status i;
  for(i=0;i<g.vex_num;++i)//把所有的顶点循环一次 
  {
    if(g.vertex[i]==v)
    {
      return i;//返回下标位置 
    }
  }
}
//创建图
void create_UDG(Mgraph &g)
{
  Status i,j,k;
  ElemType v1,v2;//顶点 
  Status cost;//权值 
  printf("请输入顶点数,边数：\n");
  scanf("%d,%d",&g.vex_num,&g.arc_num);
  getchar();//作用是将回车键吃掉 
  printf("请输入顶点信息：\n"); //读入顶点 
  for(i=0;i<g.vex_num;++i)
  {
    scanf("%c",&g.vertex[i]);
    getchar();
  } 
//初始化邻接矩阵（将二维邻接矩阵全部置为正无穷） 
  for(i=0;i<g.vex_num;++i)
  {
    for(j=0;j<g.vex_num;++j)
    {
      g.arcs[i][j]=INFINITY;
    }
  }
  //构造邻接矩阵
  printf("请输入边信息：\n");
  for(k=0;k<g.arc_num;++k)
  {
    //输入依附于两个顶点的边
    scanf("%c,%c,%d",&v1,&v2,&cost);
    getchar();
    i=LocateVex(g,v1);//找到v1顶点所在 vertex数组的位置 
    j=LocateVex(g,v2);//找到v2顶点所在vertex数组的位置 
    g.arcs[i][j]=cost;//在二维数组中将权值替换
    g.arcs[j][i]=g.arcs[i][j];  //无向网，对称矩阵
  } 
 }
  //输出图，检查图是否创建成功 
 void out_UDG(Mgraph g)
 {
  Status i,j;
  printf("图的顶点是：\n");
  for(i=0;i<g.vex_num;i++)//遍历 vertex数组 
  {
    printf("%8c",g.vertex[i]);
  }
  printf("\n");
  printf("图的邻接矩阵是：\n");
  for(i=0;i<g.vex_num;i++)//遍历 arcs数组 
  {
    for(j=0;j<g.vex_num;j++)
    {
      printf("%8d",g.arcs[i][j]);
    }
    printf("\n");
  }
  }
 //深度搜索 （递归）
void DFS(Mgraph g, Status v)
{
  printf("%8c",g.vertex[v]);//从数组下标为0的结点搜索 
  visited[v] = 1;//搜索过的标记为1 
  for(int w = 0; w < g.vex_num; w ++ )
    if( (g.arcs[v][w] != 0 ) && (!visited[w]))//权值不为0代表有边，visited为0代表没有扫过 
      DFS(g, w);
}
//创建空队列 
Status InitQueue (SqQueue &Q)
{
  Q.base=(ElemType*)malloc(MAXQSIZE * sizeof(ElemType));
  if(!Q.base)
  {
    exit(OVERFLOW);
  }
  Q.front=Q.rear=0;
  return OK;
}
//入队 
Status EnQueue(SqQueue &Q,ElemType e)
{
  if((Q.rear+1)%MAXQSIZE==Q.front)
  {
    return FALSE;
  }
  Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    return OK;
}
//出队 
Status DeQueue(SqQueue &Q)
{
  if(Q.front==Q.rear)
  {
    return FALSE;
  }
  Q.front=(Q.front+1)%MAXQSIZE;
  return Q.front-1;
} 
//广度搜索 
void BFS(Mgraph g,Status v)
{
  printf("广度优先搜索结果为：\n"); 
  Status w;
    printf("%8c",g.vertex[v]);//先将第一个顶点输出 
  Qvisited[v]=1;//将第一个顶点标记为1 
  SqQueue Q;
  InitQueue(Q);//创建队列 
  EnQueue(Q,g.vertex[v]);//将第一个顶点入队 
  while(!(Q.rear+1==Q.front))//循环条件是队列不为空 
  {
    v=DeQueue(Q);//出队，并将顶点的下标返回给v 
    for(w=0;w<g.vex_num;w++)//搜索二维数组中的每一行 
    {
      if(g.arcs[v][w]!=0&&Qvisited[w]==0)
      {
        Qvisited[w]=1;//将节点的每一个相邻结点标记为1 
        printf("%8c",g.vertex[w]);//将节点的每一个相邻结点输出 
        EnQueue(Q,g.vertex[w]);//将子节点入队列 
      }
    }
  }
}
int main()
{
  Mgraph g;
  create_UDG(g);//建图 
  out_UDG(g);//检验图 
  printf("深度优先搜索结果：\n"); 
  DFS(g,0);//深搜 
  printf("\n");
  BFS(g,0);//广搜 
  return 0;
}