数据结构实验报告无向图邻接矩阵存储结构

附录（可包括源程序清单或其它说明）#include <stdio.h>#include <string>#define MAX_NAME 10#define MAX_INFO 80typedef char InfoType;typedef char V ertexType[MAX_NAME]; // 字符串类型#define MAX_VERTEX_NUM 20typedef enum{unvisited,visited}VisitIf;typedef struct EBox{VisitIf mark; // 访问标记int ivex,jvex; // 该边依附的两个顶点的位置struct EBox *ilink,*jlink; // 分别指向依附这两个顶点的下一条边InfoType *info; // 该边信息指针}EBox;typedef struct{V ertexType data;EBox *firstedge; // 指向第一条依附该顶点的边}V exBox;typedef struct{V exBox adjmulist[MAX_VERTEX_NUM];int vexnum,edgenum; // 无向图的当前顶点数和边数}AMLGraph;typedef int QElemType;typedef struct QNode{// 单链表的链式存储结构QElemType data; //数据域struct QNode *next; //指针域}QNode,*QueuePtr;typedef struct{QueuePtr front,//队头指针，指针域指向队头元素rear; //队尾指针，指向队尾元素}LinkQueue;// 若G中存在顶点u,则返回该顶点在无向图中位置;否则返回-1int LocateV ex(AMLGraph G,V ertexType u){int i;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.adjmulist[i].data)==0)return i;return -1;}int CreateGraph(AMLGraph *G){ // 采用邻接表存储结构,构造无向图G int i,j,k,l,IncInfo;char s[MAX_INFO];V ertexType va,vb;EBox *p;printf("请输入无向图G的顶点数,边数: ");scanf("%d,%d",&(*G).vexnum,&(*G).edgenum);printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);for(i=0;i<(*G).vexnum;++i){ // 构造顶点向量scanf("%s",(*G).adjmulist[i].data);(*G).adjmulist[i].firstedge=NULL;}printf("请顺序输入每条边的两个端点(以空格作为间隔):\n");for(k=0;k<(*G).edgenum;++k){// 构造表结点链表scanf("%s%s%*c",va,vb); // %*c吃掉回车符i=LocateV ex(*G,va); // 一端j=LocateV ex(*G,vb); // 另一端p=(EBox*)malloc(sizeof(EBox));p->mark=unvisited; // 设初值p->ivex=i;p->jvex=j;p->info=NULL;p->ilink=(*G).adjmulist[i].firstedge; // 插在表头(*G).adjmulist[i].firstedge=p;p->jlink=(*G).adjmulist[j].firstedge; // 插在表头(*G).adjmulist[j].firstedge=p;}return 1;}V ertexType* GetVex(AMLGraph G,int v){ // 返回v的值if(v>=G.vexnum||v<0)exit(0);return &G.adjmulist[v].data;}// 返回v的第一个邻接顶点的序号。

实验日期：_______________ 实验指导老师：
实验4 无向图的深度优先搜索
一、实验目的和实验环境
【实验目的】
1、了解图的定义、特点，区分无向图和有向图的概念；
2、了解图的数据结构和搜索方法；
3、掌握无向图的邻接矩阵、邻接表的表示方法；
4、写出无向图的深度优先搜索程序。

【实验环境】ＶＣ＋＋６.０
二、理论依据
邻接多重表是无向图的一种很有效链式存储结构，在邻接表中容易求得顶点和边的各种信息。

除了在边结点中增加一个标志域外，邻接多重表所需的存储量和邻接表相同。

三、实验内容
设无向图G有n个点e条边，写一算法建立G的邻接多表，并按照深度优先搜索输出顶点，要求该算法时间复杂性为O（n+e），且除邻接多表本身所占空间之外只用O（1）辅助空间。

四、实验步骤
1、了解图的定义、特点，区分无向图和有向图的概念；
2、了解图的数据结构和搜索方法；
3、掌握无向图的邻接矩阵、邻接表的表示方法；
４、写出无向图的深度优先搜索程序
五、实验结果
1.源代码如下：
实验日期：_______________ 实验指导老师：
2.运行界面截图如下：
六、小结
1、在创建邻接多重表时，由于邻接多重表的数据类型为字符型，键盘输入总是很难控制。

这时可以通过人为设置函数过滤去键盘输入中的空格。

2、在邻接多重表上，各种基本操作的实现和邻接表相似。

3、在邻接多重表中，所有依附于同一顶点的边串联在同一链表中。

图实验一，邻接矩阵的实现1.实验目的（1）掌握图的逻辑结构（2）掌握图的邻接矩阵的存储结构（3）验证图的邻接矩阵存储及其遍历操作的实现2.实验内容（1）建立无向图的邻接矩阵存储（2）进行深度优先遍历（3）进行广度优先遍历3．设计与编码#ifndef MGraph_H#define MGraph_Hconst int MaxSize = 10;template<class DataType>class MGraph{public:MGraph(DataType a[], int n, int e);~MGraph(){}void DFSTraverse(int v);void BFSTraverse(int v);private:DataType vertex[MaxSize];int arc[MaxSize][MaxSize];int vertexNum, arcNum;};#endif#include<iostream>using namespace std;#include ""extern int visited[MaxSize];template<class DataType>MGraph<DataType>::MGraph(DataType a[], int n, int e){int i, j, k;vertexNum = n, arcNum = e;for(i = 0; i < vertexNum; i++)vertex[i] = a[i];for(i = 0;i < vertexNum; i++)for(j = 0; j < vertexNum; j++)arc[i][j] = 0;for(k = 0; k < arcNum; k++){cout << "Please enter two vertexs number of edge: ";cin >> i >> j;arc[i][j] = 1;arc[j][i] = 1;}}template<class DataType>void MGraph<DataType>::DFSTraverse(int v){cout << vertex[v];visited[v] = 1;for(int j = 0; j < vertexNum; j++)if(arc[v][j] == 1 && visited[j] == 0)DFSTraverse(j);}template<class DataType>void MGraph<DataType>::BFSTraverse(int v){int Q[MaxSize];int front = -1, rear = -1;cout << vertex[v];visited[v] = 1;Q[++rear] = v;while(front != rear){v = Q[++front];for(int j = 0;j < vertexNum; j++)if(arc[v][j] == 1 && visited[j] == 0){cout << vertex[j];visited[j] = 1;Q[++rear] = j;}}}#include<iostream>using namespace std;#include ""extern int visited[MaxSize];template<class DataType>MGraph<DataType>::MGraph(DataType a[], int n, int e){int i, j, k;vertexNum = n, arcNum = e;for(i = 0; i < vertexNum; i++)vertex[i] = a[i];for(i = 0;i < vertexNum; i++)for(j = 0; j < vertexNum; j++)arc[i][j] = 0;for(k = 0; k < arcNum; k++){cout << "Please enter two vertexs number of edge: ";cin >> i >> j;arc[i][j] = 1;arc[j][i] = 1;}}template<class DataType>void MGraph<DataType>::DFSTraverse(int v){cout << vertex[v];visited[v] = 1;for(int j = 0; j < vertexNum; j++)if(arc[v][j] == 1 && visited[j] == 0)DFSTraverse(j);}template<class DataType>void MGraph<DataType>::BFSTraverse(int v){int Q[MaxSize];int front = -1, rear = -1;cout << vertex[v];visited[v] = 1;Q[++rear] = v;while(front != rear){v = Q[++front];for(int j = 0;j < vertexNum; j++)if(arc[v][j] == 1 && visited[j] == 0){cout << vertex[j];visited[j] = 1;Q[++rear] = j;}}}4.运行与测试5.总结与心得通过该实验的代码编写与调试，熟悉了邻接矩阵在图结构中的应用，在调试过程中遇到很多的问题，在解决问题过程中也使我的写代码能力得到提升二，邻接表的实现1.实验目的（1）掌握图的逻辑结构（2）掌握图的邻接表存储结构（3）验证图的邻接表存储及其遍历操作的实现2.实验内容（1）建立一个有向图的邻接表存储结构（2）对建立的有向图进行深度优先遍历（3）对建立的有向图进行广度优先遍历3.设计与编码#ifndef ALGraph_H#define ALGraph_Hconst int MaxSize = 10;struct ArcNode{int adjvex;ArcNode * next;};template<class DataType>struct VertexNode{DataType vertex;ArcNode * firstedge;};template<class DataType>class ALGraph{public:ALGraph(DataType a[], int n, int e);~ALGraph();void DFSTraverse(int v);void BFSTraverse(int v);private:VertexNode<DataType> adjlist[MaxSize];int vertexNum, arcNum;};#endif#include<iostream>using namespace std;#include""extern int visited[MaxSize];template<class DataType>ALGraph<DataType>::ALGraph(DataType a[], int n, int e) {ArcNode * s;int i, j, k;vertexNum = n; arcNum = e;for(i = 0; i < vertexNum; i++){adjlist[i].vertex = a[i];adjlist[i].firstedge = NULL;}for(k = 0; k < arcNum; k++){cout << "Please enter the edge of the serial number of two vertices: ";cin >> i >> j;s = new ArcNode; s->adjvex = j;s->next = adjlist[i].firstedge;adjlist[i].firstedge = s;}}template<class DataType>ALGraph<DataType>::~ALGraph(){ArcNode * p = NULL;for(int i = 0; i < vertexNum; i++){p = adjlist[i].firstedge;while(p != NULL){adjlist[i].firstedge = p->next;delete p;p = adjlist[i].firstedge;}}}template<class DataType>void ALGraph<DataType>::DFSTraverse(int v){ArcNode * p = NULL; int j;cout << adjlist[v].vertex;visited[v] = 1;p = adjlist[v].firstedge;while(p != NULL){j = p->adjvex;if(visited[j] == 0) DFSTraverse(j);p = p->next;}}template<class DataType>void ALGraph<DataType>::BFSTraverse(int v){int Q[MaxSize];int front = -1, rear = -1;ArcNode * p = NULL;cout << adjlist[v].vertex; visited[v] = 1; Q[++rear] = v;while(front != rear){v = Q[++front];p = adjlist[v].firstedge;while(p != NULL){int j = p->adjvex;if(visited[j] == 0){cout << adjlist[j].vertex; visited[j] = 1; Q[++rear] = j;}p = p->next;}}}#include<iostream>using namespace std;#include""int visited[MaxSize] = {0};int main(){char ch[] = {'A','B','C','D','E'};int i;ALGraph<char> ALG(ch, 5, 6);for(i = 0; i < MaxSize; i++)visited[i] = 0;cout << "Depth-first traverse sequence is: ";(0);cout << endl;for(i = 0; i < MaxSize; i++)visited[i] = 0;cout << "Breadth-first traverse sequence is: ";(0);cout << endl;return 0;}4.运行与调试5.总结与心得通过该实验，掌握了图的邻接表存储结构。

《数据结构》实验报告五实验内容：图的邻接矩阵存储（数组表示）、简单输出学号：姓名：郑郑一、上机实验的问题和要求：阅读理解上面第一个关于图的邻接矩阵的程序，做下列题目。

（1）根据教科书P157页的G2图（无向图），输入数据运行程序。

（2）再适当修改上述程序，使它适用于G1图（有向图），输入数据运行程序。

二、程序设计的基本思想，原理和算法描述：无向图的邻接矩阵是对称的，而有向图的邻接矩阵是非对称的。

只需把无向图中G[i][j]=1;G[j][i]=1;改为g[i][j]=1;即可。

三、调试和运行程序过程中产生的问题及采取的措施：调试程序时未发现错误，得到了期望的结果。

四、源程序及注释程序名：28.cpp# include <stdio.h># include <stdlib.h># define MAX 20typedef int VexType;typedef VexType Mgraph[MAX][MAX]; /* Mgraph是二维数组类型标识符*//* 函数原形声明*/void creat_mg(Mgraph G);void out_mg(Mgraph G);Mgraph G1; /* G1是邻接矩阵的二维数组名*/ int n,e,v0;/* 主函数*//* main *//* 建立邻接矩阵*/void creat_mg(Mgraph G){ int i,j,k;printf("\n n,e=?");scanf("%d%d", &n,&e); /* 输入顶点数n，边数e */for(i=1; i<=n;i++)for(j=1;j<=n;j++) G[i][j]=0;/* 如果是网，G[i][j]=0该为G[i][j]=32767（无穷）*/ for(k=1;k<=e;k++) /* 组织边数的循环*/ { printf("\n vi,vj=?");scanf("%d%d", &i,&j); /* 输入一条边的两个顶点编号i,j */G[i][j]=1; G[j][i]=1; /* 无向图的邻接矩阵是对称矩阵*//* 如果是网，还要输入边的权值w，再让G[i][j]=w */}} /* creat_mg *//* 邻接矩阵简单输出，为了检查输入是否正确*/void out_mg(Mgraph G){ int i,j;char ch;for(i=1; i<=n;i++) /* 矩阵原样输出*/{ printf("\n ");for(j=1;j<=n;j++) printf("%5d",G[i][j]);}/* 输出所存在的边*/for(i=1; i<=n;i++)for(j=1;j<=n;j++)if(G[i][j]==1)printf("\n 存在边< %d,%d >",i,j);printf("\n\n 打回车键，继续。

数据结构实验报告20 10 ～20 11 学年第一学期2008级计算机专业班级：学号：姓名：实验四图的应用一、实验目的：1．掌握图的存储结构及其构造方法2．掌握图的两种遍历算法及其执行过程二、实验内容：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。

提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。

三、实验要求：1．各班学号为单号的同学采用邻接矩阵实现，学号为双号的同学采用邻接表实现。

2．C/ C++完成算法设计和程序设计并上机调试通过。

3．撰写实验报告，提供实验结果和数据。

4．写出算法设计小结和心得。

四、程序源代码：#include<iostream.h>typedef char vextype;const MAXVER=21;typedef struct listnode {int adjvex;listnode* next;}listnode;//表结点typedef struct{vextype data;listnode *first;}headnode;//头结点typedef struct{headnode vexs[MAXVER];int vexnum,arcnum;} ALgraph;//图void createALgraph(ALgraph &G){int i, s, d;listnode *p,*q;cout<<"输入图的顶点数和边数："; cin>>G.vexnum>>G.arcnum;for(i=1;i<=G.vexnum;i++){cout<<"\n输入第"<<i<<"个顶点信息："; cin>>G.vexs[i].data;G.vexs[i].first=NULL;} //输入第i个结点值并初始化第i个单链表为空for(i=1; i<=G.arcnum; i++){cout<<"\n输入第"<<i<<"条边的始点和终点：";cin>>s>>d;//s为始点，d为终点p=new listnode;p->adjvex=d;p->next=G.vexs[s].first;G.vexs[s].first=p;//将新建的以d为信息的表结点p插入s 单链表的头结点后q=new listnode;q->adjvex=s;q->next=G.vexs[d].first;G.vexs[d].first=q;//将新建的以s为信息的表结点q插入d 单链表的头结点后}}int visited[MAXVER];//定义全局数组遍历visitedvoid dfs(ALgraph G, int v)//被遍历的图G采用邻接表作为存储结构，v为出发顶点编号{listnode *p;cout<<G.vexs[v].data;visited[v]=1;p=G.vexs[v].first;while(p!=NULL){if(visited[p->adjvex]==0)dfs(G,p->adjvex);//若p所指表结点对应的邻接顶点未访问则递归地从该顶点出发调用dfsp=p->next;}}void dfsTraverse(ALgraph G){int v;//遍历图之前初始化各未访问的顶点for(v=1; v<=G.vexnum; v++)visited[v]=0;//从各个未被访问过的顶点开始进行深度遍历for(v=1;v<=G.vexnum;v++)if(visited[v]==0) dfs(G,v);}void BFS(ALgraph G, int v)//从顶点编号v出发，广度遍历邻接表存储的图G{int queue[MAXVER], front ,rear;listnode* p;front=rear=0;cout<<G.vexs[v].data;visited[v]=1;queue[++rear]=v;while(front!=rear){v=queue[++front];p=G.vexs[v].first;while(p!=NULL){if(visited[p->adjvex]==0){v=p->adjvex;cout<<G.vexs[v].data;visited[v]=1;queue[++rear]=v;}p=p->next;}} }void BFSTraverse(ALgraph G){int v;//遍历G以前，初始化visited数组为0 for(v=1;v<=G.vexnum;v++)visited[v]=0;for(v=1;v<=G.vexnum;v++)if(visited[v]==0)BFS(G,v);}void main(){ALgraph g;createALgraph(g);cout<<endl<<"深度遍历结果为：";dfsTraverse(g);cout<<endl<<"广度遍历结果为：";BFSTraverse(g);cout<<endl;}五、程序运行情况（写出输入数据及运行结果）六、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）本次实验是对邻接表和邻接矩阵的应用，使用邻接表为存储结构实现无向连通图的深度优先和广度优先搜索遍历，通过本次实验，我对图的存储结构及其构造方法有了进一步了解，对深度遍历和广度遍历的实现有了更深的认识。

数据结构教程上机实验报告实验七、图算法上机实现一、实验目的：1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。

2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接矩阵和邻接表的类型定义。

3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方法及其基本思想。

二、实验内容：1.建立无向图的邻接矩阵2.图的深度优先搜索3.图的广度优先搜索三、实验步骤及结果：1.建立无向图的邻接矩阵：1)源代码：#include "stdio.h"#include "stdlib.h"#define MAXSIZE 30typedef structchar vertex[MAXSIZE];//顶点为字符型且顶点表的长度小于MAXSIZEint edges[MAXSIZE][MAXSIZE];//边为整形且edges为邻近矩阵}MGraph;//MGraph为采用邻近矩阵存储的图类型void CreatMGraph(MGraph *g,int e,int n){//建立无向图的邻近矩阵g->egdes，n为顶点个数，e为边数int i,j,k;printf("Input data of vertexs(0~n-1):\n");for(i=0;i<n;i++)g->vertex[i]=i; //读入顶点信息for(i=0;i<n;i++)for(j=0;j<n;j++)g->edges[i][j]=0; //初始化邻接矩阵for(k=1;k<=e;k++)//输入e条边{printf("Input edges of(i,j):");scanf("%d,%d",&i,&j);g->edges[i][j]=1;g->edges[j][i]=1;}void main(){int i,j,n,e;MGraph *g; //建立指向采用邻接矩阵存储图类型指针g=(MGraph*)malloc(sizeof(MGraph));//生成采用邻接举证存储图类型的存储空间printf("Input size of MGraph:"); //输入邻接矩阵的大小scanf("%d",&n);printf("Input number of edge:"); //输入邻接矩阵的边数scanf("%d",&e);CreatMGraph(g,e,n); //生成存储图的邻接矩阵printf("Output MGraph:\n");//输出存储图的邻接矩阵for(i=0;i<n;i++){for(j=0;j<n;j++)printf("%4d",g->edges[i][j]);printf("\n");}}2)运行结果：2.图的深度优先搜索：1)源代码：#include "stdio.h"#include "stdlib.h"#define MAXSIZE 30typedef struct node//邻接表结点{int adjvex;//邻接点域struct node *next;//指向下一个邻接边结点的指针域}EdgeNode; //邻接表结点类型typedef struct vnode//顶点表结点{int vertex;//顶点域EdgeNode *firstedge; //指向邻接表第一个邻接边节点的指针域}VertexNode;//顶点表结点类型void CreatAdjlist(VertexNode g[],int e,int n){//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点EdgeNode *p;int i,j,k;printf("Input data of vetex(0~n-1);\n");for(i=0;i<n;i++)//建立有n个顶点的顶点表{g[i].vertex=i; //读入顶点i信息g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针}for (k=1;k<=e;k++)//输入e条边{printf("Input edge of(i,j):");scanf("%d,%d",&i,&j);p=(EdgeNode*)malloc(sizeof(EdgeNode));p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点p->next=g[i].firstedge; //插入是在邻接表表头进行的g[i].firstedge=p;p=(EdgeNode*)malloc(sizeof(EdgeNode));p->adjvex=i; //在顶点vj的邻接表中添加邻接点为i的结点p->next=g[j].firstedge; //插入是在邻接表表头进行的g[j].firstedge=p;}}int visited[MAXSIZE]; //MAXSIZE为大于或等于无向图顶点个数的常量void DFS(VertexNode g[],int i){EdgeNode *p;printf("%4d",g[i].vertex); //输出顶点i信息，即访问顶点ivisited[i]=1;p=g[i].firstedge; //根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点while(p!=NULL){if(!visited[p->adjvex]) //如果邻接的这个边结点未被访问过DFS(g,p->adjvex); //对这个边结点进行深度优先搜索p=p->next; //查找顶点i的下一个邻接边结点}}void DFSTraverse(VertexNode g[],int n){//深度优先搜索遍历以邻接表存储的图，其中g为顶点数，n为顶点个数int i;for(i=0;i<n;i++)visited[i]=0; //访问标志置0for(i=0;i<n;i++)//对n个顶点的图查找未访问过的顶点并由该顶点开始遍历if(!visited[i]) //当visited[i]等于0时即顶点i未访问过DFS(g,i); //从未访问过的顶点i开始遍历}void main(){int e,n;VertexNode g[MAXSIZE]; //定义顶点表结点类型数组gprintf("Input number of node:\n");//输入图中节点个数边的个数scanf("%d",&n);printf("Input number of edge:\n");//输入图中边的个数scanf("%d",&e);printf("Make adjlist:\n");CreatAdjlist(g,e,n); //建立无向图的邻接表printf("DFSTraverse:\n");DFSTraverse(g,n); //深度优先遍历以邻接表存储的无向图printf("\n");}2)运行结果：3.图的广度优先搜索：1)源代码：#include "stdio.h"#include "stdlib.h"#define MAXSIZE 30typedef struct node1//邻接表结点{int adjvex; //邻接点域struct node1 *next;//指向下一个邻接边结点的指针域}EdgeNode; //邻接表结点类型typedef struct vnode//顶点表结点{int vertex;//顶点域EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域}VertexNode; //顶点表结点类型void CreatAdjlist(VertexNode g[],int e,int n){ //建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点EdgeNode *p;int i,j,k;printf("Input data of vetex(0~n-1):\n");for(i=0;i<n;i++) //建立有n个顶点的顶点表{g[i].vertex=i; //读入顶点i信息g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针}for(k=1;k<=e;k++) //输入e条边{printf("Input edge of(i,j):");scanf("%d,%d",&i,&j);p=(EdgeNode *)malloc(sizeof(EdgeNode));p->adjvex=j;//在定点vi的邻接表中添加邻接点为j的结点p->next=g[i].firstedge;//插入是在邻接表表头进行的g[i].firstedge=p;p=(EdgeNode *)malloc(sizeof(EdgeNode));p->adjvex=i; //在顶点vj的邻接表中添加邻接点为i的结点p->next=g[j].firstedge; //插入是在邻接表表头进行的g[j].firstedge=p;}}typedef struct node{int data;struct node *next;}QNode; //链队列结点的类型typedef struct{QNode *front,*rear; //将头、尾指针纳入到一个结构体的链队列}LQueue; //链队列类型void Init_LQueue(LQueue **q) //创建一个带头结点的空队列{QNode *p;*q=(LQueue *)malloc(sizeof(LQueue)); //申请带头、尾指针的链队列p=(QNode *)malloc(sizeof(QNode)); //申请链队列的头结点p->next=NULL;//头结点的next指针置为空(*q)->front=p; //队头指针指向头结点(*q)->rear=p; //队尾指针指向头结点}int Empty_LQueue(LQueue *q) //判队空{if(q->front==q->rear) //队为空return 1;elsereturn 0;}void In_LQueue(LQueue *q,int x) //入队{QNode *p;p=(QNode *)malloc(sizeof(QNode)); //申请新链队列结点p->data=x;p->next=NULL; //新结点作为队尾结点时其next 域为空q->rear->next=p; //将新结点*p链到原队尾结点之后q->rear=p; //使队尾指针指向新的队尾结点*p}void Out_LQueue(LQueue *q,int *x) //出队{QNode *p;if(Empty_LQueue(q))printf("Queue is empty!\n");//对空，出队失败else{p=q->front->next; //指针p指向链队列第一个数据结点（即对头结点）q->front->next=p->next;//头结点的next指针指向链队列第二个数据结点（即删除第一个数据结点）*x=p->data; //将删除的对头结点数据经由x返回free(p);if(q->front->next==NULL) //出队后队为空，则置为空队列q->rear=q->front;}}int visited[MAXSIZE]; //MAXSIZE为大于或等于无向图顶点个数的常量void BFS(VertexNode g[],LQueue *Q,int i){//广度优先搜索遍历邻接表存储的图，g为顶点表，Q为队指针，i为第i个顶点int j,*x=&j;EdgeNode *p;printf("%4d",g[i].vertex); //输出顶点i信息，即访问顶点ivisited[i]=1; //置顶点i为访问过标志In_LQueue(Q,i); //顶点i入队Qwhile(!Empty_LQueue(Q)) //当队Q非空时{Out_LQueue(Q,x); //对头顶点出队并送j（暂记为顶点j）p=g[j].firstedge;//根据顶点j的表头指针查找其邻接表的第一个邻接边结点while(p!=NULL){if(!visited[p->adjvex])//如果邻接的这个边结点未被访问过{printf("%4d",g[p->adjvex].vertex); //输出这个邻接边结点的顶点信息visited[p->adjvex]=1; //置该邻接边结点为访问过标志In_LQueue(Q,p->adjvex); //将该邻接边结点送人队Q}p=p->next;//在顶点j的邻接表中查找j的下一个邻接边结点}}}void main(){int e,n;VertexNode g[MAXSIZE];//定义顶点表结点类型数组g LQueue *q;printf("Input number of node:\n"); //输入图中结点个数scanf("%d",&n);printf("Input number of edge:\n");//输入图中边的个数scanf("%d",&e);printf("Make adjlist:\n ");CreatAdjlist(g,e,n);//建立无向图的邻接表Init_LQueue(&q);//队列q初始化printf("BFSTraverse:\n");BFS(g,q,0); //广度优先遍历以邻接表存储的无向图printf("\n");}2)运行结果：三、实验总结：1．通过本次试验让我对图的遍历以及图的深度和广度优先搜索有了更深刻的记忆和理解，将课本理论的知识得以实践。

《算法与数据结构》课程实验报告一、实验目的1.实现图的存储结构;2.通过图的相关算法实现，掌握其算法思想。

二、实验内容及要求1.无向带权图的存储结构(邻接矩阵、邻接表等自选)2.实现图的相关算法(1)计算指定顶点的度(2)图的深度优先遍历和广度优先遍历算法(3)分别使用Kruskal和Prim算法求解该图的最小生成树三、系统分析（1）数据方面：定义图的模板基类，在模板类定义中的数据类型参数表<class T,class E>中，T是定点数据的类型，E是边上所附数据的类型。

这个模板基类是按照带权无向图来定义的。

在该实验中定点的数据的类型为char型，边上所附数据的类型为int型。

且图的创建为无向图。

（2）功能方面：1.能够实现图的创建以及图的输出。

2.能够返回顶点在图中位置以及图中位置对应顶点的值。

3.返回当前图中的边数与顶点数。

4.返回输入边的权值。

5.能够插入一个顶点或插入顶点与之相关联的边。

6.删除边或删除顶点与之相关联的边。

7.计算顶点的度。

8.实现深度优先搜索、广度优先搜索遍历。

9.Kruskal算法、Prim算法生成最小生成树。

四、系统设计（1）设计的主要思路根据实验要求，首先确定图的存储结构，在根据存储结构编写模板类，并将需要实现的功能代码完善，再写出实现各个功能的菜单并进行调试。

由于在编写由图生成最小生成树中采用了最小堆以及并查集的算法，故需要将这两个个类的代码完成并进行调试。

最后将此次实验所涉及的类全部整理完全后，通过之前编写的菜单对功能进行依次调试，完成此次实验。

（2）数据结构的设计图是非线性结构，它的每一个顶点可以与多个其他顶点相关联，各顶点之间的关系是任意的。

可以用很多方法来存储图结构。

在此采用邻接矩阵来存储图结构。

首先将所有顶点的信息组织成一个顶点表，然后利用一个矩阵来表示各顶点之间的邻接关系，称为邻接矩阵。

下面针对带权无向图的邻接矩阵作出说明。

其中有一个类型为顺序表的顶点表向量VerticesList，用以存储顶点的信息，还有一个作为邻接矩阵使用的二维数组Edge，用以存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关。

数据结构实验报告（实验五&&实验六）班级：软件121学号：201200834122姓名：程猛实验五图的基本操作1.问题描述：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。

以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。

2.算法设计：以邻接表存储图的结构，建立一个图的类，并且用数组visited[i]标记该节点是否被访问。

并由临接表建立邻接矩阵。

再由输入的k值确定访问的起始点。

报错机制，当输入的数据，不符合要求时，会提醒。

3.测试数据：图的点数：5图的总边数：5边的起点和终点序号：1 2 2 3 3 4 4 04.源代码：#include"stdafx.h"#include<iostream>#include<iomanip>using namespace std;#include<stdlib.h>const int MaxV=10;//最多顶点数//定义邻接表中的边节点类型struct edgenode{int adjvex; //邻接点域edgenode* next;//指向下一个边节点的链域};//定义邻接表的类型typedef edgenode** adjlist;//邻接矩阵类的定义class AdjMatrix{private:char g[MaxV]; //顶点信息数组int size; //当前顶点数int GA[MaxV][MaxV];//定义邻接矩阵GAint numE;//当前边数public://构造函数，初始化图的邻接矩阵AdjMatrix(int n);//判断图空否bool GraphEmpty() {return size==0;}//取当前顶点数int NumV() {return size;}//取当前边数int NumEdges() {return numE;}//取顶点i的值char GetValue(const int i);//取弧<v1,v2>的权int GetWeight(const int v1,const int v2);//在位置pos处插入顶点vvoid InsertV(const char &V,int pos);//插入弧<v1，v2>权为weightvoid InsertEdge(const int v1,const int v2,int weight);//建立弧的邻接矩阵void CreateMatrix(int n);//k1为则无向否则为有向k2为则有权，否则无权//从初始点vi出发深度优先搜索由邻接矩阵表示的图void dfsMatrix(bool * &visited,int i,int n);//从初始点vi出发广度优先搜索由邻接矩阵表示的图void bfsMatrix(bool * &visited,int i,int n);//由图的邻接矩阵的到图的邻接表void graphChange(adjlist &GL,int n);//检查输入的边序号是否越界，否则重新输入void check(int n,int & i,int & j);//由图的邻接矩阵建立图void Creategraph(int n);//对非连通图进行深度优先搜索void dfsMatrix(int n);//对非连通图进行广度优先搜索void bfsMatrix(int n);};AdjMatrix::AdjMatrix(int n){int i,j;for(i=0;i<n;i++)for(j=0;j<n;j++)GA[i][j]=0;size=numE=0;}//建立图的邻接矩阵void AdjMatrix::CreateMatrix(int n){int i,j,k,e;cout<<"输入图的总边数：";cin>>e;cout<<"输入"<<e<<"条无向无权边的起点和终点序号："<<endl;for(k=1;k<=e;k++){cin>>i>>j;check(n,i,j);GA[i][j]=GA[j][i]=1;}numE=e;cout<<"创建后的邻接矩阵："<<endl;for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<setw(4)<<GA[i][j];cout<<endl;}}void AdjMatrix::dfsMatrix(bool*& visited,int i,int n){cout<<g[i]<<':'<<i<<" ";visited[i]=true;for(int j=0;j<n;j++)if(i!=j&&GA[i][j]!=0&&!visited[j])dfsMatrix(visited,j,n);}void AdjMatrix::bfsMatrix(bool*& visited,int i,int n){const int MaxLength=30;int q[MaxLength]={0};int front=0,rear=0;cout<<g[i]<<':'<<i<<" ";visited[i]=true;q[++rear]=i;while(front!=rear){front=(front+1)%MaxLength;int k=q[front];for(int j=0;j<n;j++)if(k!=j&&GA[k][j]!=0&&!visited[j]){cout<<g[j]<<':'<<j<<" ";visited[j]=true;rear=(rear+1)%MaxLength;q[rear]=j;}}}void AdjMatrix::check(int n,int& i,int& j){while(1){if(i<0||i>=n||j<0||j>=n)cout<<"输入有误，请重输！";elsereturn;cin>>i>>j;}}void AdjMatrix::graphChange(adjlist &GL,int n) {int i,j;for(i=0;i<n;i++){for(j=0;j<n;j++)if(GA[i][j]!=0){edgenode*p=new edgenode;p->adjvex=j;p->next=GL[i];GL[i]=p;cout<<'('<<i<<','<<p->adjvex<<") ";}cout<<endl;}}void AdjMatrix::Creategraph(int n){int i,j,k,m=0;for(i=0;i<n;i++){k=i;for(j=0;j<n;j++)if(GA[i][j]!=0)if(k==i&&m<n){g[m]='A'+m;size++;cout<<g[m]<<'('<<i<<','<<j<<") ";m++;}}cout<<endl;g[n]='\0';}char AdjMatrix::GetValue(const int i){if(i<0||i>size){cerr<<"参数i越界"<<endl;exit(1);}return g[i];}int AdjMatrix::GetWeight(const int v1,const int v2) {if(v1<0||v1>size||v2<0||v2>size){cerr<<"参数v1或v2越界！"<<endl;exit(1);}return GA[v1][v2];}void AdjMatrix::InsertV(const char &V,int pos){int i;if(size==MaxV){cerr<<"表已满，无法插入！"<<endl;exit(1);}if(pos<0||pos>size){cerr<<"参数pos越界！"<<endl;exit(1);}for(i=size;i>pos;i--)g[i]=g[i-1];g[pos]=V;size++;}void AdjMatrix::InsertEdge(const int v1,const int v2,int weight) {if(v1<0||v1>size||v2<0||v2>size){cerr<<"参数v1或v2越界"<<endl;exit(1);}GA[v1][v2]=weight;numE++;}void AdjMatrix::dfsMatrix(int n){int i;bool *vis=new bool[NumV()];for( i=0;i<NumV();i++)vis[i]=false;for(i=0;i<NumV();i++)if(!vis[i])dfsMatrix(vis,i,n);delete []vis;}void AdjMatrix::bfsMatrix(int n){int i;bool *vis=new bool[NumV()];for( i=0;i<NumV();i++)vis[i]=false;for(i=0;i<NumV();i++)if(!vis[i])bfsMatrix(vis,i,n);delete []vis;}int _tmain(int argc, _TCHAR* argv[]) {int n,k,i;bool *vis;adjlist Al;cout<<"输入图的点数n=";cin>>n;Al=new edgenode*[n];vis=new bool[n];if(!vis){cout<<"申请堆内存失败！"<<endl;exit(1);}for(i=0;i<n;i++){vis[i]=false;}AdjMatrix A(n);A.CreateMatrix(n);cout<<"出发点vk的序号=";cin>>k;cout<<endl<<"输出邻接矩阵相应图的顶点"<<endl;A.Creategraph(n);cout<<"图的深度优先搜索顺序："<<endl;A.dfsMatrix(vis,k,n);for(i=0;i<n;i++)vis[i]=false;cout<<endl<<"图的广度优先搜索顺序："<<endl;A.bfsMatrix(vis,k,n);cout<<endl<<"输出邻接表的每个邻接点"<<endl;for(i=0;i<n;i++)vis[i]=false;A.graphChange(Al,n);delete []vis;return 0;}5.结果和分析：图的点数序列从零开始。