图子系统

图子系统

1.实验目的

（1）掌握图邻接矩阵的存储方法。

（2）掌握图深度优先遍历的基本思想。

（3）掌握图广度优先遍历的基本思想。

2.实验内容

（1）编写按键盘输入的数据建立图的邻接矩阵存储。

（2）编写图的深度优先遍历函数。

（3）编写图的广度优先遍历函数。

（4）设计一个选择式菜单如下：

图子系统

**************************************************

* 1---------更新邻接矩阵 *

* 2---------深度优先遍历 *

* 3---------广度优先遍历 *

* 0---------退出 *

**************************************************

请选择菜单号(0---3):

附C源程序如下：

  1 #include <stdio.h>
  2 #define GRAPHMAX 10
  3 #define Queuesize 30
  4 
  5 typedef struct
  6 {  char vexs[GRAPHMAX];
  7    int edges[GRAPHMAX][GRAPHMAX];
  8    int n,e;
  9 }MGraph;
 10 
 11 int visited[10];
 12 
 13 void CreateMGraph(MGraph *G);
 14 
 15 void DFSTraverseM(MGraph *G);
 16 void DFSM(MGraph *G,int i);
 17 
 18 void BFSTraverseM(MGraph *G);
 19 void BFSM(MGraph *G,int k);
 20 
 21 typedef struct
 22 {  int front;
 23    int rear;
 24    int count;
 25    int data[Queuesize];
 26 }CirQueue;
 27 
 28 void InitQueue(CirQueue *Q)
 29 {  Q->front=Q->rear=0;
 30    Q->count=0;
 31 }
 32 
 33 int QueueEmpty(CirQueue *Q)
 34 {
 35    return Q->count==0;
 36 }
 37 
 38 int QueueFull(CirQueue *Q)
 39 {
 40    return Q->count==Queuesize;
 41 }
 42 
 43 void EnQueue(CirQueue *Q,int x)
 44 {
 45    if(QueueFull(Q))
 46       printf("Error! Queue overflow.");
 47    else
 48    {  Q->count++;
 49       Q->data[Q->rear]=x;
 50       Q->rear=(Q->rear+1)%Queuesize;
 51    }
 52 }
 53 
 54 int DeQueue(CirQueue *Q)
 55 {  int temp;
 56    if (QueueEmpty(Q))
 57    {  printf("Error! Queue underflow.");
 58       return NULL;
 59    }
 60    else
 61    {  temp=Q->data[Q->front];
 62       Q->count--;
 63       Q->front=(Q->front+1)%Queuesize;
 64       return temp;
 65    }
 66 }
 67 
 68 void main() 
 69 {  MGraph *G,a;  //定义a 为一个MGraph 类型结构变量，则 a 的存储单元就确定下来
 70    char ch1;
 71    int ch2;
 72    G=&a;
 73 
 74    printf("
		 建立一个图的邻接矩阵存储结构:
");
 75    CreateMGraph(G);
 76    
 77 
 78    getchar();
 79    ch1='y';
 80    while (ch1=='y'|| ch1=='Y')
 81   {
 82      printf("
");
 83      printf("
		                   图  子  系  统                 ");
 84      printf("
		**************************************************");
 85      printf("
		*          1---------更新邻接矩阵                *");  
 86      printf("
		*          2---------深度优先遍历                *");  
 87      printf("
		*          3---------广度优先遍历                *");  
 88      printf("
		*          0---------退        出                *");      
 89      printf("
		**************************************************");
 90      printf("
		   请选择菜单号(0---3):            ");
 91      scanf("%d",&ch2);
 92      getchar();
 93      switch(ch2)
 94      {   case 1:
 95                CreateMGraph(G);
 96                printf("
		 图的邻接矩阵存储结构建立完毕.");
 97                break;
 98          case 2:
 99                DFSTraverseM(G);
100                break;
101          case 3:    
102                  BFSTraverseM(G);
103                break;  
104          case 0:
105                ch1='n';
106                break;
107          default:
108                printf("
		 输入错误！请重新输入  ");
109      }
110   }
111 }
112 
113 
114 void CreateMGraph(MGraph *G)  //建立图的邻接矩阵存储
115 { int i,j,k;
116   char ch1,ch2;
117 
118   printf("
		 请输入顶点数,边数并按回车(格式如：3,4):");
119   scanf("%d,%d",&(G->n),&(G->e));  //输入顶点数，边数
120 
121   for (i=0; i<G->n; i++) //输入各顶点符号
122   { 
123      getchar();
124      printf("
		 请输入第 %d 个顶点并按回车:  ",i+1);
125      scanf("%c", &(G->vexs[i]));
126   }
127   
128   for(i=0; i<G->n; i++)
129      for(j=0; j<G->n; j++)
130          G->edges[i][j]=0;
131 
132   for(k=0;  k<G->e; k++)
133   {  getchar();
134      printf("
		 请输入第 %d 条边的顶点符号(格式为：顶点符号,顶点符号):",k+1);
135      scanf("%c,%c",&ch1,&ch2);
136      for(i=0;ch1!=G->vexs[i];i++);
137      for(j=0;ch2!=G->vexs[j];j++);
138      G->edges[i][j]=1;
139   }
140 
141   printf("
		 已建立一个图的邻接矩阵存储结构!现输出此邻接矩阵如下：
");
142   for(i=0; i<G->n; i++)  //输出此邻接矩阵
143   {  printf("
		");
144      for(j=0; j<G->n; j++)
145         printf("%5d",G->edges[i][j]);
146   }
147 
148 }
149 
150 void DFSTraverseM(MGraph *G) //深度优先遍历
151 { int i;
152   for(i=0; i<G->n; i++)
153       visited[i]=0;
154 
155   for(i=0; i<G->n; i++)
156       if(!visited[i])
157           DFSM(G,i);
158 }
159 
160 void DFSM(MGraph *G,int i)  
161 { int j;
162   printf("
		 深度优先遍历序列：%c
", G->vexs[i]);
163   visited[i]=1;
164   for(j=0; j<G->n; j++)
165      if( G->edges[i][j]==1 && !visited[j])
166         DFSM(G,j); // 递归调用DFSM()，直到没有未被访问的相邻顶点，则访问后返回到上一层
167 }
168 
169 void BFSTraverseM(MGraph *G)
170 { int i;
171   for(i=0; i<G->n; i++)
172       visited[i]=0;
173 
174   for(i=0; i<G->n; i++)
175       if(!visited[i])
176         BFSM(G,i);
177 }
178 
179 void BFSM(MGraph *G, int k)
180 { int i,j;
181   CirQueue Q; //定义 Q 为一个循环队列结构变量
182 
183   InitQueue(&Q);
184 
185   printf("
		  广度优先遍历序列：  %c
", G->vexs[k]);  //访问此顶点
186   visited[k]=1;  // 将该顶点的访问标志置为已访问
187   EnQueue(&Q,k);  // 将该顶点的序号进对
188   
189   while( !QueueEmpty(&Q) )
190   {  i=DeQueue(&Q); //已访问顶点的序号从对首出对
191      for(j=0; j<G->n; j++)
192        if( G->edges[i][j]==1 && !visited[j] )  //如果 j 是 i 的邻接点并且 j 未被访问过
193        {  printf("
		  广度优先遍历序列：  %c
", G->vexs[j]); 
194           visited[j]=1;
195           EnQueue(&Q,j); // j 被访问后进对尾
196        }
197   }
198 }