数据结构-实验六讲义(1)-图的基本操作

数据结构与算法实验——图的基本操作图的基本操作实验报告图的基本操作实验报告实验名称图的基本操作实验目的1.掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表的存储结构；2.遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历的算法，复习栈和队列的应用；3.掌握以邻接矩阵作为存储结构的生成图的最小生成树的普利姆算法；实验内容编制一个演示图的邻接表的创建、深度遍历、广度遍历操作的程序。

问题描述用数据结构相关知识，实现邻接表的定义和操作。

该程序包括图的邻接表的结点类型定义以及对图操作的具体的函数定义（包括：建立图的邻接表、深度优先遍历图、广度优先遍历图）。

问题分析该实验是基于C语言和数据结构知识基础的对图的基本操作的检验，无需设计复杂的算法，程序语句也相对简单。

因此，我直接按要求定义了对图操作的具体函数，并于主函数中实现对应的功能调用。

实验步骤1．需求分析本演示程序用VC++编写，完成图的邻接表的生成、遍历基本操作。

输入的形式和输入值的范围：在输入邻接表顶点信息前，必须先确定该信息能正确创建邻接表。

②输出的形式：在所有三种操作中都显示操作是否正确以及操作后图的内容。

③程序所能达到的功能：完成图的邻接表的生成、深度优先遍历、广度优先遍历基本操作。

④测试数据：创建操作中依次输入7,7作为顶点数和边数，以（0,1）（0,2）（1,3）（1,5）（3,4）（3,6）（4,5）作为各顶点信息生成一个邻接表。

2．概要设计1）为了实现上述程序功能，需要定义二叉树的抽象数据类型：ADT Graph {数据对象：顶点的有穷非空集合和边的集合数据关系：结点具有相同的数据类型及层次结构基本操作：Void InitGraph(ALGraph *G)初始条件：无操作结果：初始化图Void DFSTraverse(ALGraph *G)初始条件：图Graph已存在操作结果：按深度优先遍历图的邻接表Void BFSTraverse(ALGraph *G)初始条件：图Graph已存在操作结果：按广度优先遍历图的邻接表2）本程序包含7个函数：①主函数main() ②建立一个图的邻接表函数CreateGraphAL ()③深度优先遍历图 DFS ()④广度优先遍历 BFS()函数说明#include <stdio.h>#include <stdlib.h>#define MaxVertexNum 100#define QueueSize 30typedef enum{FALSE,TRUE}Boolean;Boolean visited[MaxVertexNum];typedef char VertexType;typedef int EdgeType;typedef struct node //边表结点{int adjvex; //邻接点域struct node *next; //域链//若是要表示边上的权,则应增加一个数据域}EdgeNode;typedef struct vnode //顶点边结点{VertexType vertex; //顶点域EdgeNode *firstedge;//边表头指针}VertexNode;typedef VertexNode AdjList[MaxVertexNum];//AdjList是邻接表类型typedef struct{AdjList adjlist; //邻接表int n,e; //图中当前顶点数和边数}ALGraph;void CreateGraphAL (ALGraph *G){int i,j,k;EdgeNode * s;printf("请输入顶点数和边数(输入格式为:顶点数,边数)：\n");scanf("%d,%d",&(G->n),&(G->e));// 读入顶点数和边数printf("请输入顶点信息(输入格式为:顶点号<CR>)每个顶点以回车作为结束:\n");for (i=0;i<G->n;i++) //立有n个顶点的顶点表{scanf("\n%c",&(G->adjlist[i].vertex)); //读入顶点信息G->adjlist[i].firstedge=NULL; // 点的边表头指针设为空}printf("请输入边的信息(输入格式为:i,j)：\n");for (k=0;k<G->e;k++) // 建立边表{scanf("\n%d,%d",&i,&j); // 读入边<Vi,Vj>的顶点对应序号s=new EdgeNode; // 生成新边表结点ss->adjvex=j; // 邻接点序号为js->next=G->adjlist[i].firstedge; // 将新边表结点s插入到顶点Vi的边表头部 G->adjlist[i].firstedge=s;s=new EdgeNode;s->adjvex=i;s->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=s;}}/**************************************** ********************************//* 深度优先遍历*//**************************************** ********************************/void DFS(ALGraph *G,int i){//以vi为出发点对邻接表表示的图G进行深度优先搜索EdgeNode *p;printf("visitvertex:%c\n",G->adjlist[i].vertex); // 访问顶点vivisited[i]=TRUE; //标记vi已访问p=G->adjlist[i].firstedge; //取vi 边表的头指针while(p){ //依次搜索vi的邻接点vj，这里j=p->adjvexif (!visited[p->adjvex]) //若vi尚未被访问DFS(G,p->adjvex); //则以Vj为出发点向纵深搜索p=p->next; //找vi的下一邻接点}}void DFSTraverseM(ALGraph *G){int i;for(i=0;i<G->n;i++)visited[i]=FALSE;for(i=0;i<G->n;i++)if(!visited[i])DFS(G,i);}/**************************************** ********************************//* 广度优先遍历*//**************************************** ********************************/ typedef struct{int front;int rear;int count;int data[QueueSize];}CirQueue;void InitQueue(CirQueue *Q){Q->front=Q->rear=0;Q->count=0;}int QueueEmpty(CirQueue *Q){return Q->front==Q->rear;}int QueueFull(CirQueue *Q){return(Q->rear+1)%QueueSize==Q->front; }void EnQueue(CirQueue *Q,int x) {if (QueueFull(Q))printf("Queue overflow"); else{Q->count++;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize; }}int DeQueue(CirQueue *Q){int temp;if(QueueEmpty(Q)){printf("Queue underflow");return false;}else{temp=Q->data[Q->front];Q->count--;Q->front=(Q->front+1)%QueueSize; return temp;}}void BFS(ALGraph*G,int k){ // 以vk为源点对用邻接表表示的图G进行广度优先搜索int i;CirQueue Q; //须将队列定义中DataType改为intEdgeNode *p;InitQueue(&Q); //队列初始化printf("visitvertex:%c\n",G->adjlist[k].vertex); //访问源点vkvisited[k]=TRUE;EnQueue(&Q,k); //vk已访问，将其人队。

南京信息工程大学实验(实习)报告图的基本操作一、实验目的1、熟悉图的存储结构2、掌握图的基本操作二、实验准备1、奔腾2计算机或以上机型2、Microsoft Visual C++ 6.0三、实验内容1、建立一张图2、实现深度优先搜索、广度优先搜索遍历四、实验代码#include<stdio.h>#include<conio.h>#include<stdlib.h>typedef struct ArcNode{int adjVex;struct ArcNode *nextArc;}ArcNode;typedef struct VNode{int data;ArcNode *firstArc;}VNode;//创建一张图void CreatGraphic();//深度优先搜索遍历void DFSTraverse(int searchNode);//广度优先搜索遍历void BFSTraverse(int searchNode);//访问标志置零void ClearVisited();void Bound(char ch, int num);//邻接表VNode *adjList;//访问标记数组short *visited;//循环队列, 用于广度优先搜索遍历函数中int *queue;//图的结点数int graphicNode;//用于判断是否创建了图bool creatGraphic;int main(void){char choice;int searchNode;creatGraphic = false;while (true){if (!creatGraphic){system("CLS");printf(" 图的操作\n");Bound('-', 15);printf(" 1. 创建一张图\n");printf(" 0. 退出程序\n");Bound('-', 15);printf(" 请选择: ");fflush(stdin);choice = getchar();switch (choice){case '1':CreatGraphic();break;case '0':printf("\n");system("PAUSE");return 0;default:printf("\n 输入错误, 按任意键后重新输入!");getch();break;}}else{system("CLS");printf(" 图的操作\n");Bound('-', 20);printf(" 1. 深度优先搜索遍历\n");printf(" 2. 广度优先搜索遍历\n");printf(" 0. 退出程序\n");Bound('-', 20);printf(" 请选择: ");fflush(stdin);choice = getchar();switch (choice){case '1':ClearVisited();Lable1:printf("\n 请输入起始搜索的结点序号: ");fflush(stdin);scanf("%d", &searchNode);if (searchNode>=1 && searchNode <=graphicNode){printf(" 深度优先搜索遍历为: ");DFSTraverse(searchNode);}else{printf(" 序号输入错误, 按任意键后重新输入! \n");getch();goto Lable1;}printf("\n\n");system("PAUSE");break;case '2':ClearVisited();Lable2:printf("\n 请输入起始搜索的结点序号: ");scanf("%d", &searchNode);if (searchNode>=1 && searchNode <=graphicNode){printf(" 广度优先搜索遍历为: ");BFSTraverse(searchNode);}else{printf(" 序号输入错误, 按任意键后重新输入! \n");getch();goto Lable2;}printf("\n\n");system("PAUSE");break;case '0':printf("\n");system("PAUSE");return 0;default:printf("\n 输入错误, 按任意键后重新输入!");getch();break;}}}}void CreatGraphic(){int number;int localNode, linkNode;ArcNode *tempNode;Flag:printf("\n 请输入图的顶点数: ");fflush(stdin);scanf("%d", &graphicNode);if (graphicNode <= 0){printf(" 输入错误, 按任意键后重新输入!\n");getch();goto Flag;}if ((adjList=(VNode *)malloc(sizeof(VNode)*graphicNode)) == NULL){printf(" 内存空间不足, 无法创建图!\n");system("PAUSE");exit(0);}if ((visited=(short *)malloc(sizeof(short)*graphicNode)) == NULL){printf(" 内存空间不足, 无法创建访问记录表!\n");system("PAUSE");exit(0);}if ((queue=(int *)malloc(sizeof(int)*graphicNode)) == NULL){printf(" 内存空间不足, 无法创建队列!\n");system("PAUSE");exit(0);}for (number=0; number<graphicNode; ++number){adjList[number].data = number + 1;adjList[number].firstArc = NULL;}printf("\n 请输入所要创建的图中所有相关联的顶点, 格式( 图中一顶点与此顶点相关联的顶点)\n");do{printf(" 请输入( 注意: 输入0 0 结束输入): ");fflush(stdin);scanf("%d %d", &localNode, &linkNode);if (localNode>=1 && localNode<=graphicNode && linkNode>=1 && linkNode<=graphicNode){if ((tempNode = (ArcNode *)malloc(sizeof(ArcNode))) == NULL){printf(" 内存不足, 无法创建图!\n");exit(0);}tempNode->adjVex = linkNode;tempNode->nextArc = adjList[localNode - 1].firstArc;adjList[localNode - 1].firstArc = tempNode;}else{creatGraphic = true;return;}}while(true);}void DFSTraverse(int searchNode){ArcNode *tempNode;visited[searchNode - 1] = 1;printf("%d ", searchNode);tempNode = adjList[searchNode - 1].firstArc;while (tempNode != NULL){if (visited[tempNode->adjVex - 1] == 0){DFSTraverse(tempNode->adjVex);}tempNode = tempNode->nextArc;}}void BFSTraverse(int searchNode){ArcNode *tempNode;int nodeNum;int front = 0, rear = 0;printf("%d ", searchNode);visited[searchNode - 1] = 1;rear = (rear + 1) % graphicNode;queue[rear] = searchNode;while (front != rear){front = (front + 1) % graphicNode;nodeNum = queue[front];tempNode = adjList[nodeNum - 1].firstArc;while (tempNode != NULL){if (visited[tempNode->adjVex - 1] == 0){visited[tempNode->adjVex - 1] = 1;printf("%d ", tempNode->adjVex);rear = (rear + 1) % graphicNode;queue[rear] = tempNode->adjVex;}tempNode = tempNode->nextArc;}}}void ClearVisited(){int cnt;for (cnt=0; cnt<graphicNode; ++cnt){visited[cnt] = 0;}}void Bound(char ch, int num){while (num--){putchar(ch);}putchar('\n');}（本次实验中所用图示意图）（图1：按格式创建图）1876 5 4 3 2（图2：深度优先搜索遍历）（图3：广度优先搜索遍历）五、实验总结…。

printf("第%d个\n",i+1); scanf("%s",&G.vertices[i]); G.vertices[i].firstarc = NULL; } //这里开始构造边 printf("请输入边的信息\n"); printf("例如:v1 v2\n"); for(i = 0 ; i < G.arcnum ; i++) { printf("第%d条边\n",i+1); scanf("%s %s",&node1,&node2); j = LocateVex(G,node1); k = LocateVex(G,node2); p = (ArcNode *)malloc(sizeof(ArcNode)); q = (ArcNode *)malloc(sizeof(ArcNode)); p->adjvex = k; q->adjvex = j; p->nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = p; q->nextarc = G.vertices[k].firstarc; G.vertices[k].firstarc = q; } PrintUDG(G); return 1; } int DeleteUDG(ALGraph &G) { int i,j; ArcNode *p,*q; char node[2]; int LocateVex(ALGraph G,char node[2]); void PrintUDG(ALGraph G); if(G.arcnum == 0) { printf("请先生成图\n");

浙江大学城市学院实验报告课程名称数据结构实验项目名称实验十三/十四图的基本操作学生姓名专业班级学号实验成绩指导老师（签名）日期 2014/06/09一.实验目的和要求1、掌握图的主要存储结构。

2、学会对几种常见的图的存储结构进行基本操作。

二.实验内容1、图的邻接矩阵定义及实现：建立头文件test13_AdjM.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。

同时建立一个验证操作实现的主函数文件test13.cpp（以下图为例），编译并调试程序，直到正确运行。

2、图的邻接表的定义及实现：建立头文件test13_AdjL.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。

同时在主函数文件test13.cpp中调用这些函数进行验证（以下图为例）。

3、填写实验报告，实验报告文件取名为report13.doc。

4、上传实验报告文件report13.doc到BB。

注: 下载p256_GraphMatrix.cpp(邻接矩阵)和p258_GraphAdjoin.cpp(邻接表)源程序，读懂程序完成空缺部分代码。

三. 函数的功能说明及算法思路（包括每个函数的功能说明，及一些重要函数的算法实现思路）四. 实验结果与分析（包括运行结果截图、结果分析等）五.心得体会程序比较难写，但是可以通过之前的一些程序来找到一些规律（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。

）【附录----源程序】256://p-255 图的存储结构以数组邻接矩阵表示, 构造图的算法。

#include <iostream.h>#include <stdio.h>#include <stdlib.h>#include <string.h>typedef char VertexType; //顶点的名称为字符const int MaxVertexNum=10; //图的最大顶点数const int MaxEdgeNum=100; //边数的最大值typedef int WeightType; //权值的类型const WeightType MaxValue=32767; //权值的无穷大表示typedef VertexType Vexlist[MaxVertexNum]; //顶点信息，定点名称typedef WeightType AdjMatrix[MaxVertexNum][MaxVertexNum]; //邻接矩阵typedef enum{DG,DN,AG,AN} GraphKind; //有向图,有向网,无向图,无向网typedef struct{Vexlist vexs; // 顶点数据元素AdjMatrix arcs; // 二维数组作邻接矩阵int vexnum, arcnum; // 图的当前顶点数和弧数GraphKind kind; // 图的种类标志} MGraph;void CreateGraph(MGraph &G, GraphKind kd)// 采用数组邻接矩阵表示法，构造图G{//构造有向网Gint i,j,k,q;char v, w;G.kind=kd; //图的种类printf("输入要构造的图的顶点数和弧数：\n");scanf("%d,%d",&G.vexnum,&G.arcnum);getchar();//过滤回车printf("依次输入图的顶点名称ABCD...等等：\n");for (i=0; i<G.vexnum; i++) scanf("%c",&G.vexs[i]);//构造顶点数据getchar();//过滤回车for (i=0; i<G.vexnum; i++) //邻接矩阵初始化for (j=0; j<G.vexnum; j++)if(kd==DN||kd==AN)G.arcs[i][j]=MaxValue; //网，初始值为无穷大elseG.arcs[i][j]=0; //图，初始为0if(kd==DN||kd==AN)printf("按照：尾顶点名->头顶点名，权值输入数据:如A->B,23 \n");elseprintf("按照：尾顶点名->头顶点名输入数据:A->B\n");for (k=0; k<G.arcnum; k++){ //构造邻接矩阵if(kd==DN||kd==AN)scanf("%c->%c,%d",&v,&w,&q); //输入弧的两个定点及该弧的权重elsescanf("%c->%c",&v,&w);getchar();for(i=0;i<G.vexnum; i++)if(G.vexs[i]==v) break;//查找出v在vexs[]中的位置iif(i==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} for(j=0;j<G.vexnum; j++)if(G.vexs[j]==w) break;//查找出v在vexs[]中的位置jif(j==G.vexnum) {cerr<<"vertex ERROR!";exit(1);}if(kd==AN)//无向网{G.arcs[i][j]=q; //邻接矩阵对应位置置权值G.arcs[j][i]=q; //无向图为对称矩阵}else if(kd==DN)//有向网G.arcs[i][j]=q;else if(kd==AG)//无向图{G.arcs[i][j]=1; //对称矩阵G.arcs[j][i]=1;}else //有向图G.arcs[i][j]=1;// getchar();}}//CreateGraph/* 注意输入格式,按以下方式输入构造有向网输入要构造的网的顶点数和弧数：4,5依次输入网的顶点名称ABCD...等等：abcd按照：尾顶点名->头顶点名，权值输入数据:如A->B,23 a->b,5a->c,8c->b,7a->d,4d->c,3输出邻接矩阵∞ | 5 | 8 | 4 |∞ | ∞ | ∞ | ∞ |∞ | 7 | ∞ | ∞ |∞ | ∞ | 3 | ∞ |Press any key to continue*/void PrintMGraph(MGraph &G){int i,j;switch(G.kind){case DG:for (i=0; i<G.vexnum; i++){for (j=0; j<G.vexnum; j++)printf(" %2.d | ",G.arcs[i][j]);printf("\n");}break;case DN:for (i=0; i<G.vexnum; i++){for (j=0; j<G.vexnum; j++){if(G.arcs[i][j]!=MaxValue) printf(" %2.d | ",G.arcs[i][j]);else printf(" ∞ | ");}printf("\n");}break;case AG:for (i=0; i<G.vexnum; i++){for (j=0; j<G.vexnum; j++){printf(" %2.d | ",G.arcs[i][j]);}printf("\n");}break;case AN: //********完成构造无向网****************/* 请模仿编写无向网*/for (i=0; i<G.vexnum; i++){for (j=0; j<G.vexnum; j++){if(G.arcs[i][j]!=MaxValue) printf(" %2.d | ",G.arcs[i][j]);else printf(" ∞ | ");}printf("\n");}break;}}//*****************完成函数**********************************void countdig(MGraph G) //请完成计算图的入度或初度{if(G.kind==DG||G.kind==DN){//计算有向图或网的各个顶点的入度与出度int outD,inD;int i,j;for(i=0;i<G.vexnum;i++){outD=inD=0;for(j=0;j<G.vexnum;j++){if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MaxValue)outD++;}for(j=0;j<G.vexnum;j++){if(G.arcs[j][i]!=0&&G.arcs[j][i]!=MaxValue)inD++;}printf("%c：出度是%d,入度是%d\n",G.vexs[i],outD,inD);}}else{// 计算无向图或网的度int i,j;int Du;for(i=0;i<G.vexnum;i++){Du=0;for(j=0;j<G.vexnum;j++){if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MaxValue)Du++;}printf("%c的度是%d\n",G.vexs,Du);}}}//************参照p265设计深度有限搜索***********void DFSMatrix(MGraph G,int i,int n,bool*visited){cout<<G.vexs[i]<<' ';visited[i]=true;for(int j=0;j<n;j++)if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MaxValue&& !visited[j])DFSMatrix(G,j,n,visited);}//************参照p268设计广度有限搜索***********void BFSMatrix(MGraph G,int i, int n , bool*visited){const int MaxSize=30;int q[MaxSize]={0};int front=0,rear=0;cout<<G.vexs[i]<<' ';visited[i]=true;q[++rear]=i;while(front!=rear){front=(front+1)%MaxSize;int k=q[front];for(int j=0;j<n;j++){if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MaxValue&& !visited[j]){cout<<G.vexs[j]<<' ';visited[j]=true;rear=(rear+1)%MaxSize;q[rear=j];}}}}void main(){MGraph G;int k;printf("请选择图的种类：0:有向图,1:有向网,2:无向图,3:无向网. 请选择：");scanf("%d",&k);switch(k) { //DG,DN,AG,ANcase 0:printf("构造有向图\n");CreateGraph(G,DG); // 采用数组邻接矩阵表示法，构造有向图break;case 1:printf("构造有向网\n");CreateGraph(G,DN); // 采用数组邻接矩阵表示法，构造有向网AGGbreak;case 2:printf("构造无向图\n");CreateGraph(G,AG); // 采用数组邻接矩阵表示法，构造无向图AGGbreak;case 3:printf("构造无向网\n");CreateGraph(G,AN); // 采用数组邻接矩阵表示法，构造无向网AGGbreak;}PrintMGraph(G); //打印图的邻接矩阵bool*visited=new bool[G.vexnum];int i;cout<<"按图的邻接矩阵得到的深度优先遍历序列"<<endl;for(i=0;i<G.vexnum;i++) visited[i]=false;DFSMatrix(G,0,G.vexnum,visited);cout<<"按图的邻接矩阵得到的广度优先遍历序列"<<endl;for(i=0;i<G.vexnum;i++) visited[i]=false;BFSMatrix(G,0,G.vexnum,visited);cout<<"度："<<endl;countdig(G);}258://p-258 图的存储结构以邻接表表示, 构造图的算法。