新建 文本文档.txt

图的相关操作：建立图

#define M 20 
#include <stdio.h> 
#include <stdlib.h> 
#include <malloc.h> 
/*定义图*/ 
typedef struct{ 
 int V
; 
 int R
; 
 int vexnum; 
}Graph; 
/*定义队列*/ 
typedef struct{ 
 int V
; 
 int front; 
 int rear; 
}Queue; 
/*全局变量：访问标志数组*/ 
int visited
; 
/*创建图*/ 
void creatgraph(Graph *g,int n); 
/* 打印图的邻接矩阵 */ 
void printgraph(Graph *g); 
/* 访问顶点 */ 
void visitvex(Graph *g,int vex); 
/* 获取第一个未被访问的邻接节点 */ 
int firstadjvex(Graph *g,int vex); 
/* 获取下一个未被访问的邻接节点(深度遍历) */ 
int nextadjvex(Graph *g,int vex,int w); 
/* 深度递归遍历 */ 
void dfs(Graph *g,int vex);
void dfstraverse(Graph *g); 
/* 初始化队列 */ 
initqueue(Queue *q); 
/* 判断队列是否为空 */ 
int quempty(Queue *q); 
/* 入队操作 */ 
enqueue(Queue *q,int e); 
/* 出队操作 */ 
dequeue(Queue *q); 
/* 广度遍历 */ 
void BESTraverse(Graph *g);
/* 主程序 */ 
main() 
{ 
 int n; 
 Graph *g=(Graph *)malloc(sizeof(Graph)); 
 char menu; 
 printf("请输入图的顶点个数:\n"); 
 scanf("%d",&n); 
 creatgraph(g,n); 
 printf("图的邻接矩阵如下:\n"); 
 printgraph(g); 
input: 
 printf("请输入您的选择(b-广度优先遍历，d-深度优先遍历，q-退出): \n"); 
 while((menu=getchar())=='\n'); 
 if(menu=='b') 
 { 
  printf("广度优先遍历结果如下:\n"); 
  BESTraverse(g); 
  printf("\n"); 
  goto input; 
 } 
 else if(menu=='d') 
 { 
  printf("深度优先遍历结果如下:\n"); 
  dfstraverse(g); 
  printf("\n"); 
  goto input; 
 } 
 else if(menu=='q') 
 { 
  exit(0); 
 } 
 else 
 { 
  printf("您的输入有误!\n"); 
 } 
}

/*创建图*/ 
void creatgraph(Graph *g,int n) 
{ 
 int i,j,r1,r2,weight; 
 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("请输入有关系的两个边及其权重，格式如(0,0,0 代表结束):\n"); 
  scanf("%d,%d,%d",&r1,&r2,&weight); 
  while(r1!=0&&r2!=0&&weight!=0) 
  { 
   g->R[r1][r2]=weight; 
   g->R[r2][r1]=weight;
   scanf("%d,%d,%d",&r1,&r2,&weight);
  } 
} 
/*打印图的邻接矩阵*/ 
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"); 
 } 
} 
/*访问顶点*/ 
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);} 
} 
/*初始化队列*/ 
initqueue(Queue *q) 
{ 
 q->fr; 
 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); 
     } 
    } 
   } 
  } 
 } 
}