首页 > 编程 > C++ > 正文

纯C语言:检索与周游广度深度遍历源码分享

2020-05-23 14:23:52
字体:
来源:转载
供稿:网友
这篇文章主要介绍了检索与周游广度深度遍历源码,有需要的朋友可以参考一下
 
 

 

复制代码代码如下:

#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);
}


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表