毕业论文论文范文课程设计实践报告法律论文英语论文教学论文医学论文农学论文艺术论文行政论文管理论文计算机安全
您现在的位置: 毕业论文 >> 课程设计 >> 正文

图的遍历的演示

更新时间:2007-10-20:  来源:毕业论文
C语言数据结构课程设计题-图的遍历的演示|数据结构课程设计

#define M 20
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
/*定义图*/
typedef struct{
  int V[M];
  int R[M][M];
  int vexnum;
}Graph;

/*创建图*/
void creatgraph(Graph *g,int n)
{
  int i,j,r1,r2;
  g->vexnum=n;
  /*顶点用i表示*/
  for(i=1;i<=n;i++)
  {
    g->V[i]=i;
  }
  /*初始化R*/
  for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
    {
      g->R[i][j]=0;
    }
  /*输入R*/
  printf("Please input R(0,0 END):\n");
  scanf("%d,%d",&r1,&r2);
  while(r1!=0&&r2!=0)
   {
    g->R[r1][r2]=1;
    g->R[r2][r1]=1;
    scanf("%d,%d",&r1,&r2);
   }
}

/*打印图的邻接矩阵*/
void printgraph(Graph *g)
{
int i,j;
for(i=1;i<=g->vexnum;i++)
{ for(j=1;j<=g->vexnum;j++)
   {
     printf("%2d ",g->R[i][j]);
   }
   printf("\n");
   }
}
/*全局变量:访问标志数组*/
int visited[M];
/*访问顶点*/
void visitvex(Graph *g,int vex)
{
printf("%d ",g->V[vex]);
}

/*获取第一个未被访问的邻接节点*/
int firstadjvex(Graph *g,int vex)
{
int w,i;
for(i=1;i<=g->vexnum;i++)
  {
   if(g->R[vex][i]==1&&visited[i]==0)
    {
      w=i;
      break;
    }
   else
    {
      w=0;
    }
  }
  return w;
}
/*获取下一个未被访问的邻接节点(深度遍历)*/
int nextadjvex(Graph *g,int vex,int w)
{
  int t;
  t=firstadjvex(g,w);
  return t;
}
/*深度递归遍历*/
  void dfs(Graph *g,int vex)
   {
    int w;
    visited[vex]=1;
    visitvex(g,vex);
    for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w))
      if(!visited[w])
       {
dfs(g,w);
       }
   }

   void dfstraverse(Graph *g)
   {
     int i;
     for(i=1;i<=g->vexnum;i++)
       visited[i]=0;
     for(i=1;i<=g->vexnum;i++)
       if(!visited[i])
  {dfs(g,i);}
   }
/*定义队列*/
typedef struct{
int V[M];
int front;
int rear;
}Queue;
/*初始化队列*/
initqueue(Queue *q)
{
  q->front=0;
  q->rear=0;
}
/*判断队列是否为空*/
int quempty(Queue *q)
{
  if(q->front==q->rear)
  {
   return 0;
  }
  else
  {
   return 1;
  }
}
/*入队操作*/
enqueue(Queue *q,int e)
{
  if((q->rear+1)%M==q->front)
   {
    printf("The queue is overflow!\n");
    return 0;
   }
   else
   {
    q->V[q->rear]=e;
    q->rear=(q->rear+1)%M;
    return 1;
   }
}
/*出队操作*/
dequeue(Queue *q)
{
  int t;
  if(q->front==q->rear)
   {
     printf("The queue is empty!\n");
     return 0;
   }
   else
   {
     t=q->V[q->front];
     q->front=(q->front+1)%M;
     return t;
   }
}
/*广度遍历*/
void BESTraverse(Graph *g)
{
  int i;
  Queue *q=(Queue *)malloc(sizeof(Queue));
  for(i=1;i<=g->vexnum;i++)
  {
   visited[i]=0;
  }
  initqueue(q);
  for(i=1;i<=g->vexnum;i++)
  {
    if(!visited[i])
     {
       visited[i]=1;
       visitvex(g,g->V[i]);
       enqueue(q,g->V[i]);
       while(!quempty(q))
 {
   int u,w;
   u=dequeue(q);
   for(w=firstadjvex(g,u);w>0;w=nextadjvex(g,u,w))
     {
       if(!visited[w])
        {
   visited[w]=1;
   visitvex(g,w);
   enqueue(q,w);
        }
     }
 }
     }
  }
}
/*主程序*/
main()
{
  int n;
  Graph *g=(Graph *)malloc(sizeof(Graph));
  char menu;
  printf("Please input the number of vertex:\n");
  scanf("%d",&n);
  creatgraph(g,n);
  printf("This is the linjiejuzhen of graph:\n");
  printgraph(g);
  input:
  printf("Please input b or d or q ,Breadth_first: b  Depth_first: d quit: q\n");
  while((menu=getchar())=='\n');
  if(menu=='b')
    {
      printf("Breadth_first:\n");
      BESTraverse(g);
      printf("\n");
      goto input;
    }
  else if(menu=='d')
    {
      printf("Depth_first:\n");
      dfstraverse(g);
      printf("\n");
      goto input;
    }
  else if(menu=='q')
    {
     exit(0);
    }
  else
    {
      printf("Input error!Please input b or d!\n");
    }}

[1] [2] 下一页

图的遍历的演示下载如图片无法显示或论文不完整,请联系qq752018766
设为首页 | 联系站长 | 友情链接 | 网站地图 |

copyright©751com.cn 辣文论文网 严禁转载
如果本毕业论文网损害了您的利益或者侵犯了您的权利,请及时联系,我们一定会及时改正。