数据结构第三次实验报告概论13814.pdf

实验报告 2013-2014 学年第 1 学期 任课老师：刘安丰 课程名称 数据结构 班级 学号 姓名 实验名称 实验三 图的操作算法 实验时间 12 月 5 号 实验环境 C+实验目的和内容要求 实验三 图的操作算法 一、实验要求与内容 实现图的常用操作算法：包括建立图的存储结构、深度优先搜索和广度优先搜索，求图的最小生成树、拓扑排序、最短路径等。二、实验目的 1掌握图的基本存储方法。2掌握有关图的操作算法并用高级语言实现。3熟练掌握图的两种搜索路径的遍历方法。4.掌握图的有关应用。实验过程记录 1、最小生成树 PrimKruskal 算法#include#include#include#define MAX_VERTEX_NUM 20#define OK 1#define ERROR 0#define MAX 1000 using namespace std;typedef struct Arcell double adj;Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_VERTEX_NUM;/节点数组 AdjMatrix arcs;/邻接矩阵 int vexnum,arcnum;/图的当前节点数和弧数 MGraph;typedef struct Pnode/用于普利姆算法 char adjvex;/节点 double lowcost;/权值 Pnode,ClosedgeMAX_VERTEX_NUM;/记录顶点集 U 到 V-U 的代价最小的边的辅助数组定义 typedef struct Knode/用于算法中存储一条边及其对应的 2 个节点 char ch1;/节点 1 char ch2;/节点 2 double value;/权值 Knode,DgevalueMAX_VERTEX_NUM;/-int CreateUDG(MGraph&G,Dgevalue&dgevalue);int LocateVex(MGraph G,char ch);int Minimum(MGraph G,Closedge closedge);void MiniSpanTree_PRIM(MGraph G,char u);void Sortdge(Dgevalue&dgevalue,MGraph G);/-int CreateUDG(MGraph&G,Dgevalue&dgevalue)/构造无向加权图的邻接矩阵 int i,j,k;coutG.vexnumG.arcnum;cout请输入节点：;for(i=0;iG.vexsi;for(i=0;iG.vexnum;+i)/初始化数组 for(j=0;jG.vexnum;+j)G.arcsij.adj=MAX;cout请输入一条边依附的定点及边的权值：endl;for(k=0;k dgevaluek.ch1 dgevaluek.ch2 dgevaluek.value;i=LocateVex(G,dgevaluek.ch1);j=LocateVex(G,dgevaluek.ch2);G.arcsij.adj=dgevaluek.value;G.arcsji.adj=G.arcsij.adj;return OK;int LocateVex(MGraph G,char ch)/确定节点 ch 在图 G.vexs 中的位置 int a;for(int i=0;iG.vexnum;i+)if(G.vexsi=ch)a=i;return a;/typedef struct Pnode/用于普利姆算法/char adjvex;/节点/double lowcost;/权值/Pnode,ClosedgeMAX_VERTEX_NUM;/记录顶点集 U 到 V-U 的代价最小的边的辅助数组定义 void MiniSpanTree_PRIM(MGraph G,char u)/普利姆算法求最小生成树 int i,j,k;Closedge closedge;k=LocateVex(G,u);for(j=0;jG.vexnum;j+)if(j!=k)closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0;for(i=1;iG.vexnum;i+)k=Minimum(G,closedge);cout(closedgek.adjvex,G.vexsk,closedgek.lowcost)endl;closedgek.lowcost=0;for(j=0;jG.vexnum;+j)if(G.arcskj.adj closedgej.lowcost)closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj.adj;int Minimum(MGraph G,Closedge closedge)/求 closedge 中权值最小的边，并返回其顶点在 vexs 中的位置 int i,j;double k=1000;for(i=0;iG.vexnum;i+)if(closedgei.lowcost!=0&closedgei.lowcost k)k=closedgei.lowcost;j=i;return j;void MiniSpanTree_KRSL(MGraph G,Dgevalue&dgevalue)/克鲁斯卡尔算法求最小生成树 int p1,p2,i,j;int bjMAX_VERTEX_NUM;/标记数组 for(i=0;iG.vexnum;i+)/标记数组初始化 bji=i;Sortdge(dgevalue,G);/将所有权值按从小到大排序 for(i=0;iG.arcnum;i+)p1=bjLocateVex(G,dgevaluei.ch1);p2=bjLocateVex(G,dgevaluei.ch2);if(p1!=p2)cout(dgevaluei.ch1,dgevaluei.ch2,dgevaluei.value)endl;for(j=0;jG.vexnum;j+)if(bjj=p2)bjj=p1;void Sortdge(Dgevalue&dgevalue,MGraph G)/对 dgevalue 中各元素按权值按从小到大排序 int i,j;double temp;char ch1,ch2;for(i=0;iG.arcnum;i+)for(j=i;j dgevaluej.value)temp=dgevaluei.value;dgevaluei.value=dgevaluej.value;dgevaluej.value=temp;ch1=dgevaluei.ch1;dgevaluei.ch1=dgevaluej.ch1;dgevaluej.ch1=ch1;ch2=dgevaluei.ch2;dgevaluei.ch2=dgevaluej.ch2;dgevaluej.ch2=ch2;void main()int i,j;MGraph G;char u;Dgevalue dgevalue;CreateUDG(G,dgevalue);cout图的邻接矩阵为：endl;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)cout G.arcsij.adj;coutendl;cout=普利姆算法=n;coutu;cout构成最小代价生成树的边集为：n;MiniSpanTree_PRIM(G,u);cout=克鲁斯科尔算法=n;cout=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(-1);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;/if *(S.top)=e;S.top+;return 1;/Push int Pop(SqStack&S,SElemType&e)if(S.top=S.base)return 0;-S.top;e=*S.top;return 1;/Pop int StackEmpty(SqStack&S)if(S.top=S.base)return 1;else return 0;/StackEmpty int LocateVex(ALGraph G,char u)int i;for(i=0;iG.vexnum;i+)if(u=G.verticesi.data)return i;if(i=G.vexnum)printf(Error u!n);exit(1);return 0;void CreateALGraph_adjlist(ALGraph&G)int i,j,k,w;char v1,v2,enter;ArcNode*p;printf(Input vexnum&arcnum:n);scanf(%d,&G.vexnum);scanf(%d,&G.arcnum);printf(Input Vertices(以回车隔开各个数据):n);for(i=0;iG.vexnum;i+)scanf(%c%c,&enter,&G.verticesi.data);/注意点，解说 G.verticesi.firstarc=NULL;/for printf(Input Arcs(v1,v2,w)以回车分开各个数据:n);for(k=0;kadjvex=j;/p-info=w;p-nextarc=G.verticesi.firstarc;/前插法,即每次都插入到头结点的后面 G.verticesi.firstarc=p;printf(Nextn);/for return;/CreateALGraph_adjlist void FindInDegree(ALGraph&G)int i,j;for(i=0;iG.vexnum;i+)G.verticesi.count=0;/for for(j=0;jnextarc)G.verticesp-adjvex.count+;/for /FindInDegree int TopoSort(ALGraph&G)SqStack S;FindInDegree(G);InitStack(S);for(int i=0;inextarc)int k;k=p-adjvex;if(!(-G.verticesk.count)Push(S,k);/for /while if(counttG.vexnum)return 0;else return 1;/TopoSort int main()ALGraph G;CreateALGraph_adjlist(G);TopoSort(G);return 1;深度优先搜索和广度优先搜索 深度优先搜索：图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索 广度优先搜索：图的广度优先遍历 BFS 算法是一个分层搜索的过程，和树的层序遍历算法类同，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。/*采用邻接表的存储结构*构建无向图*图的创建过程中暂不支持重复验证，因此不能对一条边进行重复定义*/#include#include#include#define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex;struct ArcNode*nextarc;/InfoType*info;ArcNode;/*链表结点的结构用于创建栈或是队列*/typedef struct LinkNode ArcNode*parc;/存储指针地址 struct LinkNode*next;/指向一下个结点 LinkNode;typedef struct VNode char cData;/顶点元素值 ArcNode*firstarc;/指向第一条依附于该点的边 VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum;/图的当前顶点数和弧数 int arcnum;ALGraph;int VisitedMAX_VERTEX_NUM;/*将生成的图打印出来以便确认正确性*/int PrintCheck(ALGraph*pag)int i;ArcNode*p;printf(nCheck the Graph!n);printf(Notdatatnexttnextt.n);for(i=0;ivexnum;i+)printf(%dt%ct,i,pag-verticesi.cData);p=pag-verticesi.firstarc;while(p)printf(%dt,p-adjvex);p=p-nextarc;printf(n);return 1;/*采用前插法创建邻接表*/int CreateGraph(ALGraph*pag,int start,int end)ArcNode*arcNodes=(ArcNode*)malloc(sizeof(ArcNode);ArcNode*arcNodee=(ArcNode*)malloc(sizeof(ArcNode);ArcNode*p;if(!arcNodes|!arcNodee)return 0;/从 start-end 生成关系 arcNodes-adjvex=end;/下一结点的位置 p=pag-verticesstart.firstarc;if(!p)/第一个结点单独构造 arcNodes-nextarc=pag-verticesstart.firstarc;pag-verticesstart.firstarc=arcNodes;else while(p-nextarc)p=p-nextarc;p-nextarc=arcNodes;arcNodes-nextarc=NULL;/end-start 的关系生成 arcNodee-adjvex=start;/下一结点的位置 p=pag-verticesend.firstarc;if(!p)/第一个结点单独构造 arcNodee-nextarc=pag-verticesend.firstarc;pag-verticesend.firstarc=arcNodee;else while(p-nextarc)p=p-nextarc;p-nextarc=arcNodee;arcNodee-nextarc=NULL;return 1;/*深度优先遍历,非递归方式*结点先访问再入栈*栈的存储结构直接采用了 LinkNode 构成的链表*采用前插法进行插入与删除，从而也可以完成栈的功能*栈空条件 Stack-next=NULL*/void DFSTraverse(ALGraph ag,int start)LinkNode*Stack=(LinkNode*)malloc(sizeof(LinkNode);/链表头结点，用做栈 LinkNode*pStack=(LinkNode*)malloc(sizeof(LinkNode);/对栈操作的指针 LinkNode*temp;/临时存储 ArcNode*p;int i;if(!pStack|!Stack)return;Stack-next=NULL;p=ag.verticesstart.firstarc;Visitedstart=1;/Flag printf(n 输出深度优先遍历顺序:);printf(%c,ag.verticesstart.cData);/访问第一个点 while(1)/正常情况下执行一次，为了打印孤立结点 /push stack pStack-parc=p;pStack-next=Stack-next;/将 p 接入链式栈中 Stack-next=pStack;/push over while(p&(Stack-next)/当并且栈不为空时 while(p)if(Visitedp-adjvex)p=p-nextarc;else Visitedp-adjvex=1;printf(%c,ag.verticesp-adjvex.cData);/Visit Function /push stack pStack=(LinkNode*)malloc(sizeof(LinkNode);if(!pStack)return;/结点建立不成功 pStack-parc=p;pStack-next=Stack-next;Stack-next=pStack;/push over p=ag.verticesp-adjvex.firstarc;/pop stack temp=Stack-next;Stack-next=temp-next;p=temp-parc-nextarc;free(temp);/pop over for(i=0;inext=NULL*/void BFSTraverse(ALGraph ag,int start)LinkNode*Queue=(LinkNode*)malloc(sizeof(LinkNode);/链表头结点，用做队列 LinkNode*pQueue=(LinkNode*)malloc(sizeof(LinkNode);/对队列操作的指针 LinkNode*temp;/临时存储 LinkNode*last;/指向最后一个元素的指针 ArcNode*p;int i;if(!Queue|!pQueue)return;printf(n 输出广度优先遍历次序:);printf(%c,ag.verticesstart.cData);p=ag.verticesstart.firstarc;Visitedstart=1;while(1)/正常情况下执行一次循环 /EnQueue pQueue-parc=p;Queue-next=pQueue;pQueue-next=NULL;last=pQueue;/指向最后一个元素的指针 /EnQueue over while(p&Queue-next)while(p)if(!Visitedp-adjvex)Visitedp-adjvex=1;printf(%c,ag.verticesp-adjvex.cData);/Visit Function /EnQueue pQueue=(LinkNode*)malloc(sizeof(LinkNode);if(!pQueue)return;pQueue-parc=p;pQueue-next=NULL;last-next=pQueue;last=last-next;/指向最后一个元素的指针 /EnQueue over p=p-nextarc;/DeQueue temp=Queue-next;p=ag.verticestemp-parc-adjvex.firstarc;Queue-next=temp-next;/DeQueue over for(i=0;iag.vexnum;i+)/打印出孤立点 if(!Visitedi)printf(%c,ag.verticesi.cData);p=ag.verticesi.firstarc;if(i=ag.vexnum)break;printf(nn);/*主函数负责对图的初始化工作*其中包括图的结点初始化，边初始化*其中大部分的 while(1)语句 用于验证输入数据的有效性*/void main()ALGraph ag;int i,n,m;int choose;/选择遍历结点 int start,end;/边的起点与终点的位置 printf(说明:采用邻接表的存储结构，生成无向图n 输入数据请回车确认nn);while(1)/结点个数有效性验证 printf(请输入图的结点个数,并回车:);scanf(%d,&n);if(n0)break;else printf(n 请注意结点个数不能大于 20,并且不能为 0!n);ag.vexnum=n;printf(n 初始化图的结点，输入字符并回车:n);for(i=0;iag.vexnum;i+)/图的结点数据 printf(No.%d=,i);fflush(stdin);scanf(%c,&ag.verticesi.cData);ag.verticesi.firstarc=NULL;m=(n-2)*(n+1)/2+1;/顶点数为 n 的图最多的边的数量为 m while(1)/边的数量有效性验证 printf(请输入边的数量:);fflush(stdin);scanf(%d,&i);if(i=0)break;else printf(n 请注意边的数量不能大于%d,并且不能小于 1!n,m);ag.arcnum=i;printf(n 初始化图的边，结点从 0 开始计，最大为%dn,n-1);for(i=1;i=ag.arcnum;i+)while(1)/起点有效性验证 printf(第条边的起点:,i);fflush(stdin);scanf(%d,&start);if(start=0)break;else printf(重新输入);while(1)/终点有效性验证 printf(第条边的终点:,i);fflush(stdin);scanf(%d,&end);if(end=0&end!=start)break;else printf(重新输入);printf(n);CreateGraph(&ag,start,end);PrintCheck(&ag);/打印出生成的图 printf(n 开始进行图的遍历!n);while(1)/起始点有效性验证 printf(请输入深度优先遍历的开始结点:);fflush(stdin);scanf(%d,&choose);if(choose=0&choose=0&choosen)break;else printf(重新输入 );BFSTraverse(ag,choose);/广度优先遍历 system(pause);4、最短路径#include#include#define MAX 100#define MAXINT 1000/*typedef struct node int number;struct node*next;edgeNode;*/typedef struct int vexnum;int arcnum;int arcsMAXMAX;Mgragh;int creat_mgragh(Mgragh&mg)int i=0;int j=0;int k=0;int weight;cout输入顶点数mg.vexnum;cout输入边数mg.arcnum;for(i=0;img.vexnum;i+)for(j=0;jmg.vexnum;j+)mg.arcsij=MAXINT;for(k;kmg.arcnum;k+)cout输入边依附的两个顶点：endl;cout输入边的起点：endl(起点的顶点不可超过mg.vexnum)i;if(i=mg.vexnum)cout 输 入 边 的 终 点：endl(终 点 的 顶 点 不 可 超 过mg.vexnum)j;if(j=mg.vexnum)cout输入权值weight;mg.arcsi-1j-1=weight;mg.arcsj-1i-1=weight;break;else cout重新输入！endl;break;else cout重新输入！endl;for(i=0;img.vexnum;i+)for(j=0;jmg.vexnum;j+)coutmg.arcsij;coutt;coutendl;coutendl;return 0;void Dijkstra(Mgragh&g,int v0)creat_mgragh(g);int pathMAX;int distMAX;int sMAX;/s 数组用来放在 s 中的顶点，开始的时候只有 v0；当 sv=0时，则 v 没有在 s 数组中 int v;for(v=1;vg.vexnum;v+)/初始化 sv=0;distv=g.arcsv0v;if(distvMAXINT&v!=v0)pathv=v0;else pathv=-1;/coutpathv0endl;distv0=0;sv0=1;for(int i=0;ig.vexnum-1;i+)int min=MAXINT;v=-1;/int w；for(int w=1;wg.vexnum;w+)if(sw=0&distwmin)/w 若没在 s 数组中且路径小于当前存在的最小路径 v=w;min=distw;if(v!=-1)sv=1;/将该 v 放入 s 数组中 for(int j=0;jg.vexnum;j+)if(sj=0&(min+g.arcsvjdistj)distj=min+g.arcsvj;pathj=v;for(int i=1;ig.vexnum;i+)if(distiMAXINT&i!=v0)coutvi-;int next=pathi;while(next!=v0)coutvnext-;next=pathnext;coutv0:distiendl;else if(i!=v0)coutvi-v0:no pathendl;int main()Mgragh mg;/creat_mgragh(mg);int v0=0;Dijkstra(mg,v0);system(PAUSE);return 0;实验结果分析与总结 1、程序运行结果（请提供所完成的各道题运行结果界面截图）：最小生成树 拓扑排序 3、图的深度优先搜索和广度优先搜索 4、最短路径 3、实验过程中的发现与收获，未解决或需进一步解决的问题：1）了解了最小生成树中的 Prime 算法 Prim 算法 设 G=(V,E)是连通带权图，V=1,2,n。构造 G 的最小生成树 Prim 算法的基本思想是：首先置 S=1，然后，只要 S 是 V 的真子集，就进行如下的贪心选择：选取满足条件 i S,j V S,且 cij最小的边，将顶点 j 添加到 S 中。这个过程一直进行到 S=V 时为止。在这个过程中选取到的所有边恰好构成 G的一棵最小生成树 Kruskal 算法 当图的边数为 e 时，Kruskal 算法所需的时间是 O(eloge)。当 e=(n2)时，Kruskal 算法比 Prim 算法差；但当 e=o(n2)时，Kruskal 算法比 Prim 算法好得多。2）图的深度优先搜索可以用递归，非递归实现 递归实现（1）访问顶点 v；visitedv=1；/算法执行前 visitedn=0（2）w=顶点 v 的第一个邻接点；（3）while（w 存在）if（w 未被访问）从顶点 w 出发递归执行该算法；w=顶点 v 的下一个邻接点；非递归实现 （1）栈 S 初始化；visitedn=0；（2）访问顶点 v；visitedv=1；顶点 v 入栈 S （3）while(栈 S 非空)x=栈 S 的顶元素(不出栈)；if(存在并找到未被访问的 x 的邻接点 w)访问 w；visitedw=1；w 进栈;3）了解了拓扑排序的算法及需要注意的问题 拓扑排序算法思想 1、在 AOV 网络中选一个没有直接前驱的顶点,并输出之;2、从图中删去该顶点,同时删去所有它发出的有向边;3、重复以上步骤,直到 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或者图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时 AOV 网络中必定存在有向环。（拓扑排序完成；AOV 网络中必定存在有向环）4）了解了最短路径算法 单源最短路径 单源最短路径问题：已知有向带权图(简称有向网)G=(V，E)，找出从某个源点 sV 到 V 中其余各顶点的最短路径。迪杰斯特拉(Dijkstra)算法求单源最短路径。心得：本次实验内容较多，涉及图的重点知识很多，与之前相比稍有难度，在实验中不断整合书本上的知识，并通过与同学老师的交流对图的内容加深了理解。指导老师评阅意见 指导老师：年 月 日 填写内容时，可把表格扩大。附：实验源程序代码