图的遍历的演示.txt

进行图的遍历的演示,（c 语言 数据结构课程设计题）,绝对有用,可以运行

图的遍历的演示（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"); 
    } 
} 
数据结构课程设计_图的遍历的演示