课程设计6－－图的遍历

69 阅读 0 评论 46 点赞

我是靠谱客的博主爱听歌短靴，最近开发中收集的这篇文章主要介绍课程设计6－－图的遍历，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include "stdafx.h"

#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;
/*初始化队列*/
void initqueue(Queue *q)
{
q->front=0;
q->rear=0;
}
/*判断队列是否为空*/
int quempty(Queue *q)
{
if(q->front==q->rear)
{
   return 0;
}
else
{
   return 1;
}
}
/*入队操作*/
bool 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;
   }
}
/*出队操作*/
int 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);
               }
            }
        }
     }
}
}
/*主程序*/
void 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");
   }
}