PTA 图的算法设计 1 图的存储和遍历

作者 张鏖烽

单位 湖南工程学院计算机与通信学院

从键盘输入图G的顶点数量n、边数量e，图的边（设图G是一个不带权值的无向图），编程实现以下函数：

（1）CreateAdLGrap(GL,GM):根据图G的邻接矩阵GM创建其邻接表GL；

（2）DisplayAdLGrap(GL):输出图G的邻接表；

（3）BFS_Tranv(GL,v)：从顶点v开始广度优先遍历（BFS）图G；

（4）DFS_Tranv(GL,v)：从顶点v开始深度优先遍历（DFS）图G；

函数接口定义：

void CreatAdLGrap(AdLGrap *&GL,MatGrap *GM); void DisplayAdLGrap(AdLGrap *GL); void BFS_Tranv(AdLGrap *GL,int v); void DFS_Tranv(AdLGrap *GL,int v);

其中GL为图G的邻接表存储结构，GM为其邻接矩阵存储结构，v为遍历开始顶点序号；

裁判测试程序样例：

在这里给出函数被调用进行测试的例子。例如： #include<stdio.h> #include<malloc.h> #define MaxNum 20 typedef struct { int edges[MaxNum][MaxNum]; int n,e; }MatGrap;//邻接矩阵 typedef struct ANode{ int vex; struct ANode *next; }ArcNode;//邻接表邻接点的结点类型 typedef struct vnode{ int data; ArcNode *first; }VNode;//邻接表头结点类型 typedef struct { VNode adjList[MaxNum]; int n,e; }AdLGrap;//邻接表 //定义两个全局变量，用来标记顶点是否已经被访问 int Bvisit[MaxNum],Dvisit[MaxNum]; void CreatAdLGrap(AdLGrap *&GL,MatGrap *GM); void DisplayAdLGrap(AdLGrap *GL); void BFS_Tranv(AdLGrap *GL,int v); void DFS_Tranv(AdLGrap *GL,int v); void BFS_Tranv1(AdLGrap *GL) { int i; for(i=0;i<GL->n;i++) Bvisit[i]==0; for(i=0;i<GL->n;i++) { if(Bvisit[i]==0) BFS_Tranv(GL,i); } } void DFS_Tranv1(AdLGrap *GL) { int i; for(i=0;i<GL->n;i++) Dvisit[i]==0; for(i=0;i<GL->n;i++) { if(Dvisit[i]==0) DFS_Tranv(GL,i); } } int main() { AdLGrap *GL; MatGrap *GM=(MatGrap *)malloc(sizeof(MatGrap)); int n,e; int i,j; int v1,v2;//边的两个顶点 printf("请输入顶点和边的数量："); scanf("%d%d",&n,&e); for(i=0;i<n;i++) { for(j=0;j<n;j++) GM->edges[i][j]=0; } GM->e=e; GM->n=n; printf("请输入%d条边：\n",e); for(i=0;i<e;i++) { scanf("%d%d",&v1,&v2); GM->edges[v1][v2]=1; GM->edges[v2][v1]=1; } CreatAdLGrap(GL,GM); DisplayAdLGrap(GL); printf("图的BFS遍历结果："); BFS_Tranv1(GL); printf("\n图的DFS遍历结果："); DFS_Tranv1(GL); return 0; } /* 请在这里填写答案 */

输入样例：边（m,n）的输入格式：m n

在这里给出一组输入。例如：

6 7 0 2 0 3 1 2 2 3 0 5 1 5 3 5

输出样例：

在这里给出相应的输出。例如：

请输入顶点和边的数量：请输入7条边： 顶点0:---> 2---> 3---> 5--->NULL 顶点1:---> 2---> 5--->NULL 顶点2:---> 0---> 1---> 3--->NULL 顶点3:---> 0---> 2---> 5--->NULL 顶点4:--->NULL 顶点5:---> 0---> 1---> 3--->NULL 图的BFS遍历结果：0 2 3 5 1 4 图的DFS遍历结果：0 2 1 5 3 4

参考代码：

void CreatAdLGrap(AdLGrap *&GL,MatGrap *GM) { GL=(AdLGrap *)malloc(sizeof(AdLGrap)); GL->n=GM->n; GL->e=GM->e; for (int i=0;i< GL->n;i++) GL->adjList[i].data=i,GL->adjList[i].first=NULL; for (int i=0;i<GM->n;i++) { for (int j=0;j<GM->n;j++) { if (GM->edges[i][j]==1) { ArcNode *newNode=(ArcNode *)malloc(sizeof(ArcNode)); newNode->vex=j; newNode->next=NULL; if (GL->adjList[i].first==NULL) { GL->adjList[i].first=newNode; } else { ArcNode *p=GL->adjList[i].first; while (p->next!=NULL) p=p->next; p->next=newNode; } } } } } void DisplayAdLGrap(AdLGrap *GL) { for (int i=0;i<GL->n;i++) { printf("顶点%d:--->",i); ArcNode *p=GL->adjList[i].first; while (p!=NULL) { printf("%3d--->",p->vex); p=p->next; } printf("NULL\n"); } } void BFS_Tranv(AdLGrap *GL, int v) { int queue[MaxNum],front=0,rear=0; Bvisit[v]=1; printf("%d ",v); queue[rear++]=v; while (front!=rear) { int c=queue[front++]; ArcNode *p= GL->adjList[c].first; while (p!=NULL) { int w=p->vex; if (!Bvisit[w]) { Bvisit[w]=1; printf("%d ",w); queue[rear++]=w; } p=p->next; } } } void DFS_Tranv(AdLGrap *GL,int v) { Dvisit[v]=1; printf("%d ",v); ArcNode *p=GL->adjList[v].first; while (p!=NULL) { int w=p->vex; if (!Dvisit[w]) DFS_Tranv(GL, w); p=p->next; } }