数据结构实验五实验报告记录————————————————————————————————作者：————————————————————————————————日期：数据结构实验报告实验五图子系统实验题目：图的遍历问题专业班级：网络工程 1002班组长：王星（2010100230）组员：郭坤铭（2010100243）张磊（2010100244）2012年 5月 18日实验报告实验类型__综合__实验室_软件实验室二__一、实验题目图的遍历问题二、实验目的和要求1、掌握图的存储思想及其存储实现2、掌握图的深度、广度优先遍历算法思想及其程序实现3、掌握图的常见应用算法的思想及其程序实现三、需求分析本演示程序用c++6.0编写，完成用户用键盘输入以下结点数据：太原、成都、北京、上海、天津、大连、河北。

（1）建立一个有向图或无向图（自定）的邻接表并输出该邻接表。

（2）在图的邻接表的基础上计算各顶点的度，并输出。

（3）以有向图的邻接表为基础实现输出它的拓扑排序序列。

（4）采用邻接表存储实现无向图的深度优先遍历。

（5）采用邻接表存储实现无向图的广度优先遍历。

（6）采用邻接矩阵存储实现无向图的最小生成树的 PRIM 算法。

最后，在主函数中设计一个简单的菜单，分别调试上述算法。

四、概要设计为了实现上述程序功能，需要定义如下内容基本数据类型定义如下：typedef struct node{ //边表结点int adj; //边表结点数据域struct node *next;}node;typedef struct vnode //顶点表结点{ char name[20];node *fnext;}vnode,AList[20];typedef struct{ AList List; //邻接表int v,e; //顶点树和边数}*Graph;Graph CreatDG(){ } //建立无向邻接表Graph CreatAG(){ } //有向邻接图void Print(Graph G){} //输出图的邻接表void CreateAN(AGraph *G1){} //构造邻接矩阵结构的图G void Du(Graph G){} //输出各顶点的度数void DFSTravel(Graph G){} //深度优先遍历void BFSTravel(Graph G){} //广度优先遍历五、详细设计#include<stdio.h>#include<stdlib.h>#include<string.h>typedef struct node{//边表结点int adj;//边表结点数据域struct node *next;}node;typedef struct vnode{//顶点表结点char name[20];node *fnext;}vnode,AList[20];typedef struct{AList List;//邻接表int v,e;//顶点树和边数}*Graph;//建立无向邻接表Graph CreatDG(){Graph G;int i,j,k;node *s;G=malloc(20*sizeof(vnode));printf("请输入图的顶点数和边数(空格隔开)：");scanf("%d%d",&G->v,&G->e);//读入顶点数和边数for(i=0;i<G->v;i++){printf("请输入图中第%d元素：",i+1);scanf("%s",G->List[i].name);//读入顶点信息G->List[i].fnext=NULL;//边表置为空表}for(k=0;k<G->e;k++){printf("请请输入第%d条边的两顶点序号(空格隔开)：",k+1);scanf("%d%d",&i,&j);//读入边（Vi,Vj）的顶点对序号;s=(node *)malloc(sizeof(node));//生成边表结点s->adj=j;s->next=G->List[i].fnext;G->List[i].fnext=s;//将新结点*s插入顶点Vi的边表头部s=(node *)malloc(sizeof(node));s->adj=i;//邻接点序号为is->next=G->List[j].fnext;G->List[j].fnext=s;// 将新结点*s插入顶点Vj的边表头部}return G;}//有向邻接图Graph CreatAG(){Graph G;int i,j,k;node *q;G=malloc(20*sizeof(vnode));printf("请输入图的顶点数和边数【空格隔开】：");scanf("%d%d",&G->v,&G->e);for (i=0;i<G->v;i++){printf("请输入图中第%d元素：",i+1);scanf("%s",&G->List[i].name); //读入顶点信息G->List[i].fnext=NULL;}for (k=0;k<G->e;k++){printf("请请输入第%d边的两顶点序号【空格隔开】：",k+1);scanf("%d%d",&i,&j);q=(node *)malloc(sizeof(node)); //生成新边表结点sq->adj=j; //邻接点序号为jq->next=G->List[i].fnext;G->List[i].fnext=q;}return G;}//输出图的邻接表void Print(Graph G){int i;node *p;printf("\t=======邻接表========\n");for(i=0;i<G->v;i++){p=G->List[i].fnext;printf("%d | %3s",i,G->List[i].name);while(p){printf("->%3s",G->List[p->adj].name);printf("->%d",p->adj);p=p->next;}printf("\n");}}typedef struct {char vex[20];}Lists[20];typedef struct{Lists l;int edge[20][20];//邻接矩阵int v1,e1;//顶点数和弧数}AGraph;typedef struct{int data; /* 某顶点与已构造好的部分生成树的顶点之间权值最小的顶点 */int lowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值 */}ClosEdge[20]; /* 用普里姆算法求最小生成树时的辅助数组 */ void CreateAN(AGraph *G1){/* 构造邻接矩阵结构的图G */int i,j,k,w;printf("请输入图的顶点数和边数（空格隔开）：");scanf("%d%d",&G1->v1,&G1->e1);//读入顶点数和边数for(i=1;i<=G1->v1;i++){printf("请输入图%d号元素：",i);scanf("%s",&G1->l[i].vex);//读入顶点信息}for(i=1;i<=G1->v1;i++)//初始化邻接矩阵for(j=1;j<=G1->v1;j++)G1->edge[i][j] = 9;for(k=1;k<=G1->e1;k++){printf("请输入两顶点及边的权值（空格隔开）：");scanf("%d%d%d",&i,&j,&w);G1->edge[i][j]=w;G1->edge[j][i]=w;}}void PrintAN(AGraph *G1){int i,j;printf("\t=======邻接矩阵========\n");for(i=1;i<=G1->v1;i++){for(j=1;j<=G1->v1;j++)printf("%3d",G1->edge[i][j]);printf("\n");}}//输出各顶点的度数void Du(Graph G){int i,j;printf("\n<----各点度数---->\n");for(i=0;i<G->v;i++){p=G->List[i].fnext;printf("顶点%2s的度为：",G->List[i].name);j=0;while(p){j++;p=p->next;}printf("%d\n",j);}}//栈typedef struct stack{int x;struct stack *next;}stack;int push(stack *s,int i){stack *p;p=(stack *)malloc(sizeof(stack));p->x=i;p->next=s->next;s->next=p;return 1;}int pop(stack *s,int j){stack *p=s->next;//保存栈顶指针j=p->x;s->next=p->next; //将栈顶元素摘下free(p);//释放栈顶空间return j;}//拓扑排序void Topo(Graph G,stack *s){int i,k, count;int j=0;int indegree[20]={0};for(i=0;i<G->v;i++){p=G->List[i].fnext;;while(p!=NULL){indegree[p->adj]++;p=p->next;}}for(i=0;i<G->v;i++)if(indegree[i]==0)push(s,i);count=0;while(s->next!=NULL){i=pop(s,j);printf("%2s ",G->List[i].name);++count;for(p=G->List[i].fnext;p!=NULL;p=p->next){ k=p->adj;if(!(--indegree[k]))push(s,k);}}if(count<G->v) printf("有回路!");}void DFS(Graph G,int i,int flag[]){node *p;printf("%2s ",G->List[i].name);flag[i]=1;p=G->List[i].fnext;while(p){if(!flag[p->adj])DFS(G,p->adj,flag);p=p->next;}}//深度优先遍历void DFSTravel(Graph G){int i;int flag[20];//标志数组for(i=0;i<G->v;i++)flag[i]=0;for(i=0;i<G->v;i++)if(!flag[i])DFS(G,i,flag);}//建立队列typedef struct{int *elem;int front, rear;}*Queue;//队列初始化void InitQueue(Queue Q){Q->elem=(int *)malloc(20*sizeof(int));if(!Q->elem)exit(0);Q->front=Q->rear=0;}//入队void Enter(Queue Q, int e){if((Q->rear + 1)%20!= Q->front)Q->elem[Q->rear ]=e;elseprintf("队列满!\n");Q->rear=(Q->rear+1)%20;}//出队void Leave(Queue Q, int e){if(Q->rear != Q->front)e=Q->elem[Q->front];elseprintf("队列空!\n");Q->front=(Q->front+1)%20;}//广度优先遍历void BFSTravel(Graph G){Queue Q;node *p;int i,j=0;int flag[20];//标志数组Q=malloc(sizeof(20));InitQueue(Q);for(i=0;i<G->v;i++)flag[i]=0;for(i=0;i<G->v;i++)if(flag[i]==0){flag[i]=1;printf("%2s",G->List[i].name);Enter(Q,i);while(Q->front!=Q->rear){Leave(Q,j);//队头元素出队并置为jp=G->List[j].fnext;while(p!=NULL){if(flag[p->adj]==0){printf("%2s ",G->List[p->adj].name);flag[p->adj]=1;Enter(Q,p->adj);}p=p->next;}}}}int minimum(ClosEdge cl,int vnum){int i;int w,p;w=1000;for(i=1;i<=vnum;i++)if(cl[i].lowcost!=0&&cl[i].lowcost<w){w=cl[i].lowcost;p=i;}return p;}void Prim(AGraph *G1,int u){ClosEdge closedge;int i,j,k;for(j=1;j<=G1->v1;j++) /* 辅助数组初始化 */if(j!=u){closedge[j].data=u;closedge[j].lowcost=G1->edge[u][j];}closedge[u].lowcost=0; /* 初始，U={u} */for(i=1;i<G1->v1;i++){k=minimum(closedge,G1->v1); /* 求出生成树的下一个顶点*/printf("%d-----%d\n",closedge[k].data,k); /* 输出生成树的边 */closedge[k].lowcost=0; /* 第k顶点并入U集 */for(j=1;j<=G1->v1;j++) /* 新顶点并入U后，修改辅助数组*/if(G1->edge[k][j]<closedge[j].lowcost){closedge[j].data=k;closedge[j].lowcost=G1->edge[k][j];}}}//菜单列表void menu(){printf("\t**********************图的遍历问题**********************\n");printf("\t\t------- 1.建立无向邻接图---------\n");printf("\t\t------- 2.建立有向邻接图---------\n");printf("\t\t------- 3.建立无向邻接矩阵---------\n");printf("\t\t------- 4.输出各顶点的度---------\n");printf("\t\t------- 5.拓扑排序---------\n");printf("\t\t------- 6.深度优先遍历---------\n");printf("\t\t------- 7.广度优先遍历---------\n");printf("\t\t------- 8.prim算法生成最小生成树---------\n");printf("\t\t------- 9-退出---------\n");printf("\t********************************************** **********\n");}//主函数void main(){Graph G;AGraph G1;int choice,u;stack *s=(stack *)malloc(sizeof(stack));s->next =NULL;while(1){menu();printf("请输入选择:");scanf("%d",&choice);switch(choice){case1:G=CreatDG();Print(G);printf("\n\n");break;case2:G=CreatAG();Print(G);printf("\n\n");break;case3:CreateAN(&G1);PrintAN(&G1);printf("\n\n");break; case4:Du(G);printf("\n\n");break;case5:printf("拓扑排序:");Topo(G,s);printf("\n\n");break;case6:printf("深度优先遍历:");DFSTravel(G);printf("\n\n");break;case7:printf("广度优先遍历:");BFSTravel(G);printf("\n\n");break;case 8:printf("请输入起点序号:");scanf("%d",&u);printf("Prim算法:\n");Prim(&G1,u);printf("\n");break;case 9: exit(0);default: printf("输入错误,请重新输入：\n\n ");}}}六、使用说明1、程序名为实验5.exe，运行坏境为DOS.程序执行后显示如图所示：2、建立无向邻接图3、输出各顶点的度4、进行深度优先遍历5、进行广度优先遍历6、建立有向邻接图7、拓扑排序8、建立无向邻接矩阵9、prim算法生成最小生成树七、实验总结本次实验对我们来说有不小的难度，花费了很长的时间，在大家的商量讨论和共同努力下，最终完成了实验的内容，组长在此过程中很认真负责，使组员一步一步前进。