第一篇：北化航天工业学院~数据结构~实验5图
实验五：图的应用
班级学号姓名
一、实验预备知识复习C++中的全局变量的概念。复习图的邻接矩阵和邻接表两种存储方式。复习图的两种遍历方法和求图的最小生成树的方法。
二、实验目的掌握图的邻接矩阵和邻接表两种存储方法。掌握有关图的操作算法并用高级语言实现。熟悉图的构造算法，了解实际问题的求解效率与采用何种存储结构与算法有着密切联系。掌握图的两种搜索路径的遍历算法。掌握求图的最小生成树的普里姆算法和克鲁斯卡尔算法。
三、实验内容创建给定的图，从邻接表和邻接矩阵两种存储方式中选择一种。对所创建的图进行深度和广度优先搜索遍历，给出遍历过程中的顶点序列。3 求图的最小生成树，按构造顺序输出边的序列。编写一个主函数，将上面函数连在一起，构成一个完整程序。将实验源程序调试并运行。
四、实验要求
所建立的图为：
用邻接表存储结构时，所创建的单链表以结点的从小到大排列。 注意标志数组visited[n+1] 的定义和赋值。
将顶点1作为起点。
五、实验结果
给出源程序及输入、输出结果。
六、实验总结
实验过程中遇到的问题及解决方法，收获。
第二篇：数据结构上机实验--图
数据结构上机实验六
实验内容:图的基本操作
实验要求:
1)图的遍历与基本操作要作为函数被调用.2)把自己使用的图结构明确的表达出来.3)基本上实现每个实验题目的要求.分组要求：可单独完成，也可两人一组。
实验目的:
1)熟悉C/C++基本编程,培养动手能力.2)通过实验,加深对图的理解.评分标准：
1)只完成第一和第二题，根据情况得4，5分；
2）完成前3题，根据情况得5至7分；
3）在2）基础上，选做四）中题目，根据情况得8至10分。
题目:
一)建立一个无向图+遍历+插入
(1)以数组表示法作为存储结构，从键盘依次输入顶点数、弧数与各弧信息建立一个无向图；
(2)对（1）中生成的无向图进行广度优先遍历并打印结果；
(3)向（1）中生成的无向图插入一条新弧并打印结果；
二)建立一个有向图+遍历+插入+删除
(1)以邻接表作为图的存储结构，从键盘输入图的顶点与弧的信息建立一个有向图；
(2)对（1）中生成的有向图进行深度优先遍历并打印结果；
(3)在（1）中生成的有向图中，分别插入与删除一条弧并打印其结果；
(4)在（1）中生成的有向图中，分别插入与删除一个顶点并打印结果；
(5)在（1）中生成的有向图中,各顶点的入度与出度并打印结果；
三）基本应用题
（1）编写算法，判断图中指定的两个顶点是否连通。
（2）编写算法，判断图的连通性。如果不连通，求连通分量的个数
（3）编写算法，判断图中任意两个顶点的连通性
（4）编写算法，判断图中是否存在回路。
（5）实现图的广度优先搜索算法。
四）高级应用题
（1）实现Prim算法
（2）实现Kruskal算法
（3）实现迪杰斯特拉算法
（4）实现拓扑排序算法
（5）实现关键路径算法
第三篇：数据结构 实验一 图[推荐]
北京邮电大学信息与通信工程学院
数据结构实验报告
实验名称： 实验二——图 学生姓名： 佘晨阳 班
级： 2014211117 班内序号： 20 学
号： 2014210491 日
期： 2015年12月05日
1．实验要求
根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能：
1、图的建立
2、图的销毁
3、深度优先遍历图
4、广度优先遍历图
5、使用普里姆算法生成最小生成树
6、使用克鲁斯卡尔算法生成最小生成树
7、求指定顶点到其他各顶点的最短路径
8、其他：比如连通性判断等自定义操作
编写测试main()函数测试图的正确性
2.程序分析
本实验要求掌握图基本操作的实现方法，了解最小生成树的思想和相关概念，了解最短路径的思想和相关概念，学习使用图解决实际问题的能力。
2.1 存储结构
存储结构：1.不带权值的无向图邻接矩阵
2.带权值的无向图邻接矩阵
3.带权值的有向图邻接矩阵
1．不带权值的无向图邻接矩阵
第1页 北京邮电大学信息与通信工程学院
2带权值的无向图邻接矩阵.3.带权值的有向图邻接矩阵
[备注]：
1.在使用打印元素、BFS、DFS 采用无权值的无向图邻接矩阵存储方式 2.在使用PRIM、KRUSKAL、3.在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式
2.2 关键算法分析
第2页 北京邮电大学信息与通信工程学院
一．图的邻接矩阵构造函数：
1.关键算法： template
//带权值的图的构造函数 { int i, j, k, height;f s1, s2;vnum = n;arcnum = e;for(k = 0;k < n;k++){ vertex[k] = a[k];}
//初始化顶点
for(k = 0;k for(i = 0;i < n;i++) { arc[k][i] =-1; if(i == k)arc[k][i] = 0; //初始化权值的大小 } visited[k] = 0;} cout << endl;for(k = 0;k //初始化边 { cout << “请输入线性链接节点:”; cin >> s1 >> s2 >> height; arc[convert(s1)][convert(s2)] = height; arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)];//采用无向图带权值的邻接矩阵 } cout << endl;cout << “所得邻接矩阵为：” << endl; for(k = 0;k for(i = 0;i < n;i++) { if(arc[k][i] ==-1) cout << “∞” << “ ”; else cout << arc[k][i] << “ ”; //打印邻接矩阵的格式 } cout << endl; } cout << endl 2.算法的时间复杂度 第3页 北京邮电大学信息与通信工程学院 有构造可知，初始化时其时间复杂度：O(n2) 二．深度优先便利DFS: 1.关键算法 ①从某顶点v出发并访问 ②访问v的第一个未访问的邻接点w，访问w的第一个未访问的邻接点u，…… ③若当前顶点的所有邻接点都被访问过，则回溯，从上一级顶点的下一个未访问过的顶点开始深度优先遍历 ④直到所有和v路径相通的顶点都被访问到； 2.代码图解： 深度优先遍历示意图 3.代码详解： template for(int j = 0;j < vnum;j++) //连通图 if((visited[j] == 0)&&(arc[v][j] >= 1))DFS(j);//当存在回路时，则连通深一层遍历 } 4.时间复杂度 时间复杂度：O(n2) 空间复杂度：栈的深度O(n) 辅助空间O(n) 第4页 北京邮电大学信息与通信工程学院 三．广度遍历BFS 1.关键算法 ①访问顶点v ②依次访问v的所有未被访问的邻接点v1,v2,v3… ③分别从v1,v2,v3…出发依次访问它们未被访问的邻接点 ④反复①②③，直到所有和v路径相通的顶点都被访问到； 2.代码图解 3.代码详解 1.初始化队列Q 2.访问顶点v，visited[v]=1 3.while(队列非空) 3.1 v=队头元素出队 3.2 访问队头元素的所有未访问的邻接点 4.时间复杂度 时间复杂度：O(n2) 空间复杂度：辅助空间O(n) 四.最小生成树——普里姆算法 1,关键思路 一般情况下，假设n个顶点分成两个集合：U(包含已落在生成树上的结点)和V-U(尚未落在生成树上的顶点)，则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。主数据结构： 邻接矩阵 辅助数据结构： int adjvex[MAXSIZE];// U集中的顶点序号 第5页 北京邮电大学信息与通信工程学院 int lowcost[MAXSIZE]; // U(V-U)的最小权值边 2.代码图解 第6页 北京邮电大学信息与通信工程学院 第7页 北京邮电大学信息与通信工程学院 3;代码详解 template //辅助数组存储所有到的V0边 { adjvex[i] = 0;lowcost[i] = arc[0][i]; } lowcost[0] = 0;for(int j = 1;j < vnum;j++) //循环n-1次 { int k = Mininum(lowcost); //求下一个顶点 cout << vertex[adjvex[k]] << “->” << vertex[k] << endl; lowcost[k] = 0; //U=U+{Vk} for(int j = 0;j < vnum;j++) //设置辅助数组 { if((lowcost[j]!= 0 && arc[k][j] < lowcost[j])) { lowcost[j] = arc[k][j]; adjvex[j] = k; } } 第8页 北京邮电大学信息与通信工程学院 } } 4,时间复杂度： 时间复杂度O(n2)，适合稠密图 五.最小生成树----克鲁斯卡尔算法 1,关键思路 先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。2.代码图解： 3.代码详解 template //最小生成树—kruskal算法 { cout<<“Krusal算法结果为：”< int k = 0, j = 0; while(k < vnum-1){ int m = vedgelist[j].fromv, n = vedgelist[j].endv; int sn1 = vset[m]; int sn2 = vset[n]; //两个顶点分属 第9页 北京邮电大学信息与通信工程学院 不同的集合 if(sn1!= sn2) { cout << vertex[m] << “->” << vertex[n] << endl; k++; for(int i = 0;i < vnum;i++) { if(vset[i] == sn2) vset[i] = sn1; //集合sn2全部改成sn1 } } j++;} } 4.时间复杂度 时间复杂度O(nlogn)，适合稀疏图 六．最短路径——Dijkstra算法 1.关键代码 • 按路径长度递增的次序产生源点到其余各顶点的最短路径。• 1)设置集合s存储已求得的最短路径的顶点，• 2)初始状态：s=源点v • 3)叠代算法： • 直接与v相连的最近顶点vi,加入s • 从v经过vi可以到达的顶点中最短的，加入s …… 2.代码图解 第10页 北京邮电大学信息与通信工程学院 3.代码详解 emplate //关于最短路径的初始化 { int v=convert(x); for(int i = 0;i < vnum;i++) //初始化路径和点 { s[i]=0; disk[i] = arc[v][i]; if(disk[i]!= maxs)path[i] = v; else path[i] =-1;} s[v] = 1;disk[v] = 0;path[v]=-1;for(int i = 0;i < vnum;i++) //反复经过从该点到其他点的路径 { if((v = FindMin())==-1)continue; s[v] = 1; for(int j = 0;j < vnum;j++) if(!s[j] &&(disk[j]>arc[v][j] + disk[v])) { 第11页 北京邮电大学信息与通信工程学院 disk[j] = arc[v][j] + disk[v]; path[j] = v; } } Print(); //打印路径长度和遍历 } 4.时间复杂度 时间复杂度为：n^2 七．判断连通图算法 template { cout<<“该图为连通图！*******输入成功！”< return false; } else { cout<<“该图不为连通图！*******请重新输入”< return true; } } 时间复杂度：n^2 3.程序运行结果 1.测试主函数流程： 第12页 北京邮电大学信息与通信工程学院 函数流程图： 1.输入图的连接边并打印 构造下面所示图的邻接矩阵： 第13页 北京邮电大学信息与通信工程学院 2.判断图连通是否成功 3.BFS DFS PRIM算法的实现 第14页 北京邮电大学信息与通信工程学院 4.克鲁斯卡尔算法实现过程 4.有向图邻接矩阵的构建 第15页 北京邮电大学信息与通信工程学院 插入V0位置后打印距离并开始回溯 总结 1.调试时出现的问题及解决的方法 问题一：prim算法中 解决方法：调整循环条件，修正函数体注意有无Next的区别 第16页 北京邮电大学信息与通信工程学院 问题二：BFS和DFS同时在一个类里作用时会输出错误 解决方案：每次BFS/DFS使用时都把visited数组初始化一遍 问题三：在最短路径，经常出现了停止输入的情况 解决方法：改return为continue，并修改打印算法 2.心得体会 通过本次实验，基本熟练掌握了c++基本语句，尤其对图的结构及应用有了较深了解；调试代码时尽量做到完成一个代码段调试一次，可以最快检测出错误所在；类的封装和调用，类的共有成员和私有成员的设置。 3.下一步的改进 第一，设置增加图节点和边的函数 第二，实现图形化输出图的路径的功能 第三，主函数设计简单，不要过于累赘 4.程序中出现的亮点 1)利用dfs算法衍生生成判断是否为连通图的连通算法 2)采用graph类实现所有图的所有算法，所需的数据类型均在私有成员内，封装 3)利用convert函数采取象意输入，采用ABCD的节点输入方式而并非转化成01234再输入。 4)BFS中采用c++标准库的。 5)打印邻接矩阵时，打印出非链接的∞符号和与自身路径的0距离 6)判断图为非连通图后，提示输入错误，重新输入图元素 第17页 “数据结构和算法II”课程实验报告 实验名称：图及其应用 班级 姓名 学号 实验日期： 实验机时：2 学时 实验成绩： -----------------一.实验目的： 1.熟练掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法 2.掌握图的基本运算及应用 3.加深对图的理解，逐步培养解决实际问题的编程能力 二.实验内容：（1）基本实验内容： 采用邻接表或邻接矩阵方式存储图，实现图的深度遍历和广度遍历； 用广度优先搜索方法找出从一顶点到另一顶点边数最少的路径。三.程序及注释： #include “stdio.h” #include “limits.h” //INT_MAX头文件 #include “windows.h” //boolean头文件 #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 #define OVERFLOW-1 #define OK 1 #define ERROR 0 typedef int Status;typedef enum {DG,DN,UDG,UDN} GraphKind;typedef int VRType;typedef char VertexType;typedef char* InfoType;typedef int QElemType;//边信息 typedef struct ArcCell{ VRType adj;//1或0表示是否邻接,对带权图，则为权值类型 InfoType *info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//图结构 typedef struct { VertexType vexs[MAX_VERTEX_NUM];//定点向量 AdjMatrix arcs; //邻接矩阵，为一二维数组 //图的当前顶点数和弧数 int vexnum,arcnum;GraphKind kind; //图的种类标志 }MGraph;//辅助队列 typedef struct QNode{ QElemType data;//数值域 struct QNode *next;//指针域 }QNode, *QueuePtr;typedef struct{ QueuePtr front;//队头 QueuePtr rear;//队尾 }LinkQueue;//初始化队列 Status InitQueue(LinkQueue &Q){ Q.front = Q.rear =(QueuePtr)malloc(sizeof(QNode));if(!Q.front){ printf(“内存分配失败!”);exit(OVERFLOW);} Q.front->next = NULL;return OK;} //插入元素到队尾 Status EnQueue(LinkQueue &Q,QElemType e){ QueuePtr p =(QueuePtr)malloc(sizeof(QNode));if(!p){printf(“n内存分配失败!”);exit(OVERFLOW);} p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK;} //队列判空 Status QueueEmpty(LinkQueue Q){ return Q.front == Q.rear;} //销毁队列 Status DestroyQueue(LinkQueue &Q){ while(Q.front){Q.rear = Q.front->next;free(Q.front);Q.front = Q.rear;} return OK;} //删除队头元素 Status DeQueue(LinkQueue &Q,QElemType &e){ if(QueueEmpty(Q)){printf(“n队列为空！”);return ERROR;} QueuePtr p = Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear==p)Q.rear = Q.front;free(p);return OK;} //对顶点v定位，返回该顶点在数组的下标索引，若找不到则返回-1 int LocateVex(MGraph G,char v){ for(int i=0;i G.kind = UDN;printf(“输入顶点个数和边数(如：4,3):”);int vexnum,arcnum;scanf(“%d,%d”,&vexnum,&arcnum);G.vexnum=vexnum;G.arcnum=arcnum;//判断是否超过顶点最大个数 while(G.vexnum>MAX_VERTEX_NUM){printf(“最大顶点为20，重新输入(如：4,3):”);scanf(“%d,%d”,&G.vexnum,&G.arcnum);} printf(“n依次输入顶点向量值n”);int i;for(i=0;i //清空缓冲区 fflush(stdin);printf(“第%d个:”,i+1);scanf(“%c”,&G.vexs[i]);} //初始化邻接矩阵 for(i=0;i int values;printf(“n输入依附两个顶点的边及其权值<如，a,b,1>n”);for(i=0;i printf(“第%d条：”,i+1);//清空缓冲区 fflush(stdin);scanf(“%c,%c,%d”,&rear,&front,&values);int m,n;//定位两顶点在vexs数组中的索引 m = LocateVex(G,rear);n = LocateVex(G,front);if(m==-1||n==-1){ printf(“输入顶点或不在此图中，请重新输入！n”);i--;continue;} //赋予对应矩阵位置的权值，以及对称弧的权值 G.arcs[m][n].adj = values;G.arcs[n][m].adj = values;} return OK;} //CreateUDG //矩阵输出 void printArcs(MGraph G){ int i;printf(“ ”);//输出第一行的顶点向量 for(i=0;i for(int j=0;j else printf(“ %d”,G.arcs[i][j].adj);}} printf(“ ∞”); printf(“n”);} //访问顶点v输出 Status printAdjVex(MGraph G,int v){ printf(“%c ”,G.vexs[v]);return OK;} //查找v顶点的第一个邻接点 Status FirstAdjVex(MGraph G,int v){ //查找与顶点v的第一个邻接点，找到后立即返回其索引，若找不到，则返回-1 for(int i=1;i return i;} return-1;} //查找基于v顶点的w邻接点的下一个邻接点 Status NextAdjVex(MGraph G,int v,int w){ //查找基于顶点v的w邻接点的下一个邻接点，找到之后立即返回其索引，若找不到，则返回-1 for(int i=w+1;i boolean visited[MAX_VERTEX_NUM];//函数指针变量 Status(* VisitFunc)(MGraph G,int v);//DFS,从第v个顶点出发递归深度优先遍历图G void DFS(MGraph G,int v){ visited[v] = TRUE;//访问第v个顶点 VisitFunc(G,v);for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){if(!visited[w]) DFS(G,w);}} //深度优先遍历 void DFSTraverse(MGraph G,Status(*Visit)(MGraph G,int v)){ //将函数复制给全局的函数指针变量，待调用DFS时使用 VisitFunc = Visit;int v;//将访问标记初始化为false for(v=0;v void BFSTraverse(MGraph G,Status(*Visit)(MGraph G,int v)){ //按广度优先非递归遍历图G，使用辅助队列Q和访问标志数组Visited int v;int u;//将访问标记数组初始化为false for(v = 0;v //判断顶点V是否被访问 if(!visited[v]){//将第一次访问的顶点对应的访问标记数组位置赋值为TRUE visited[v] = TRUE;//输出顶点v Visit(G,v);EnQueue(Q,v);while(!QueueEmpty(Q)){//按入队序列取出顶点，便于查找此顶点的邻接点 DeQueue(Q,u);//查找当前顶点邻接点 for(int w=FirstAdjVex(G,u);w>=0;w = NextAdjVex(G,u,w)) if(!visited[w]){visited[w] =TRUE;Visit(G,w);EnQueue(Q,w);}}} //销毁队列 DestroyQueue(Q);} int main(){ printf(“====图的创建及其应用====n”);//创建一个图 MGraph G;CreateUDN(G);//用邻接矩阵输出图 printf(“n图的邻接矩阵输出如下:n”);printArcs(G);//深度优先遍历 printf(“n深度优先遍历序列:n”);DFSTraverse(G,printAdjVex);printf(“n”);//广度优先遍历 } printf(“n广度优先遍历序列:n”);BFSTraverse(G,printAdjVex);printf(“n”);四.运行结果： 五.实验心得： 通过本次课程设计，对图的概念有了一个新的认识，在学习离散数学的时候，总觉得图是很抽象的东西，但是在学习了《数据结构与算法》这门课程之后，我慢慢地体会到了其中的奥妙，图能够在计算机中存在，首先要捕捉他有哪些具体化、数字化的信息，比如说权值、顶点个数等，这也就说明了想要把生活中的信息转化到计算机中必须用数字来完整的构成一个信息库，而图的存在，又涉及到了顶点之间的联系。图分为有向图和无向图，而无向图又是有向图在权值双向相等下的一种特例，如何能在计算机中表示一个双向权值不同的图，这就是一件很巧妙的事情。有了这次课程设计的经验和教训，我能够很清楚的对自己定一个合适的水平。第四篇：湘潭大学 数据结构实验5 实验报告 源代码 图的应用
点击咨询 