图的操作算法.doc

实验报告20132014学年第一 学期 任课老师： 刘安丰 课程名称Java语言与系统设计班级计科1204班学号0909121916姓名崔姝瑶实验名称实验三 图的操作算法实验时间第14周星期 四第7、8节实验环境Dev-C+4.9.9.2实验目的和内容要求设计程序：实现图的常用操作算法：包括建立图的存储结构、深度优先搜索和广度优先搜索，求图的最小生成树、拓扑排序、最短路径等实验过程记录（1） 首先要建立图的存储结构，图的存储结构有两种：一种是邻接矩阵表示，这种存储方式便于判定任意两个顶点之间是否有边，便于求各个顶点的度。便于查找任一顶点的下一个邻接点或所有的邻接点，适用于边数较多的稠密图。一种是邻接表表示法，这种存储方式在边数较少的时候比较节省存储空间，便于找到任一顶点的第一个邻接点个下一个邻接点，便于得到无向图中顶点的度和有向图中顶点的出度。（2） 进行图的遍历：所谓“图的遍历”是指从图的某一个顶点出发访问图中的所有顶点，而且每个顶点都被访问一次的额过程。图的遍历分为优化深度遍历和广度遍历两种，图的深度遍历搜索类似于树的先根遍历，图的广度遍历类似于树的层次遍历。遍历的话从图的哪一个顶点开始都可以，但是最后要确认所有的顶点都已经被访问过了（程序见源代码）。（3） 深度遍历，即从图的某个顶点出发，访问该顶点，然后依次从与这个顶点邻接的顶点出发继续实行深度优先搜索，直至所有的顶点都被访问到。若此时图中还有顶点没有被访问到，则从它们中间选取一个，重复实施深度优先搜索过程。实现深度遍历的存储结构最好是邻接表（程序见源代码）。（4） 广度遍历，即是从某个顶点出发访问该结点，然后一次去访问与该结点相邻接的顶点，然后依次去访问这些已访问过的每个邻接顶点的邻接顶点，如此继续下去，直至图中所有的顶点都得到访问，且制备访问了一次。（5） 求最小生成树的算法有两种：一个是普里姆算法，一个是克鲁斯卡尔算法。（6） 求图的最短路径一般采用邻接矩阵的存储方式。要用几个数组来说明每个顶点的性质，dist【】存放当前找到的从源点v0到每个终点的最短路径的长度，其初态为图中直接路径权值。数组path【】表示从v0到各终点的最短路径上，此顶点的前一顶点的序号：若从v0到某终点无路径，则用0作为其前一项点的序号。数组S【】的值用来说明这个元素是不是在s集合中。(程序见源代码)（7） 最后要将最短路径输出，可以建立一个变量next用来指向数组path【】中的前一个顶点，然后逆向输出。实验结果分析与总结1、程序运行结果（请提供所完成的各道题运行结果界面截图）：（1）输入数据（2）存储矩阵（3）图的最短路径（4）深度搜索（5）广度搜索的输出结果(6)拓扑排序的运行结果：（7）最小生成树的运行结果：2、在实验过程中遇到的问题与解决方法： 图的操作对于我们来说是一道难题，我们之前没有接触过类似的程序，因为图是没有一个固定的顶点了，所有的点都可以作为顶点，这也是图与数最大的区别。图是一种多对多的结构，对于图的操作来说，最关键的是要建立不同顶点之间的联系，通过变量的改变或者其他操作使得两个顶点建立了联系。求最短路径之类的操作就是在顶点建立联系的基础上对于图的更深一步的操作，通过对于顶点之间联系的变动来建立新的联系。开始的时候不知道如何通过逻辑关系建立图中各个顶点的关系。后来通过查课本和资料，建立了各个顶点之间的联系。指导老师评阅意见指导老师： 2013 年 12 月 5 日填写内容时，可把表格扩大。附：实验源程序代码（1） 存储矩阵和最短路径的程序： #include#include#define MAX 100#define MAXINT 1000/*typedef struct nodeint number;struct node *next;edgeNode;*/typedef structint 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;（2） 最小生成树的程序#include #include #define TURE 999 typedef struct ArcNode char vexs10; int edgs1010; int n,e; MGraph; struct edg int v1; int v2; int cost; A10,B10; /创建图 void GreateMGraph(MGraph *G) int i,j,k,weight,m,n; int ch1,ch2; char a,b; printf(输入图的顶点数和边数（中间由空格隔开）); scanf(%d %d,&(G-n),&(G-e); /输入顶点数,边数 for(i=0;in;i+) getchar(); printf(请输入第%d个顶点:,i+1); scanf(%c,&(G-vexsi); /输入顶点 for(i=0;in;i+) for(j=0;jn;j+) G-edgsij=0; printf(输入边的权重：格式如 i（边的起始顶点） j（边的终点） w（边的权重）n【中间由空格隔开】n) ; for(k=0;ke;k+) printf(请输入第%d条边的顶点权值):,k+1); getchar(); scanf(%c %c %d,&a,&b,&weight); m=0;n=0; for( m=0;G-vexsm!=a;m+); for( n=0;G-vexsn!=b;n+); ch1=m;ch2=n; G-edgsch1ch2=weight;G-edgsch2ch1=weight; void prim(MGraph *G, int v) int i,j,k,min; struct int adjvex; int lowcost; closedge10; for (i=0;in;i+) closedgei.lowcost=G-edgsvi; closedgei.adjvex=v; closedgev.lowcost=TURE; for (i=1;in;i+) min=100; for(j=0;jn;j+) if (closedgej.lowcost!=TURE & closedgej.lowcost!=0) if (closedgej.lowcostvexsclosedgek.adjvex, G-vexsk, min); closedgek.lowcost=TURE; for (j=0;jn;j+) if (closedgej.lowcost!=TURE) if(G-edgskjedgskj; closedgej.adjvex=k; int main(void) MGraph *G,a; char ch1; G=&a; printf(建立图的邻接矩阵n); GreateMGraph(G); getchar(); ch1=1; printf(n); printf(最小生成树 ); printf(prim算法输出为a：); prim(G,0); system(pause); （3）存储链表和深度优先搜索、广度优先搜索的程序：/*采用邻接表的存储结构*构建无向图*/#include#include#include#define MAX_VERTEX_NUM 20typedef struct ArcNodeint adjvex;struct ArcNode* nextarc;/InfoType* info;ArcNode;/*链表结点的结构用于创建栈或是队列*/typedef struct LinkNodeArcNode* parc;/存储指针地址struct LinkNode* next;/指向一下个结点LinkNode;typedef struct VNodechar cData; /顶点元素值ArcNode* firstarc;/指向第一条依附于该点的边VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum; /图的当前顶点数和弧数int arcnum; ALGraph;int VisitedMAX_VERTEX_NUM;/*采用前插法创建邻接表*/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;elsewhile(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;elsewhile(p-nextarc)p = p-nextarc;p-nextarc = arcNodee;arcNodee-nextarc = NULL;return 1;/*深度优先遍历,非递归方式*/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;/Flagprintf(n输出深度优先遍历顺序:);printf( %c ,ag.verticesstart.cData);/访问第一个点while(1)/正常情况下执行一次，为了打印孤立结点/push stackpStack-parc = p;pStack-next = Stack-next;/将p接入链式栈中Stack-next = pStack;/push overwhile(p & (Stack-next)/当并且栈不为空时while(p)if(Visitedp-adjvex)p = p-nextarc;elseVisitedp-adjvex=1;printf( %c ,ag.verticesp-adjvex.cData);/Visit Function/push stackpStack = (LinkNode*)malloc(sizeof(LinkNode);if(!pStack)return;/结点建立不成功pStack-parc = p;pStack-next = Stack-next;Stack-next = pStack;/push overp = ag.verticesp-adjvex.firstarc;/pop stacktemp = Stack-next;Stack-next = temp-next;p = temp-parc-nextarc;free(temp);/pop overfor(i=0; iparc = p;Queue-next = pQueue;pQueue-next = NULL;last = pQueue;/指向最后一个元素的指针/EnQueue overwhile(p & Queue-next)while(p)if(!Visitedp-adjvex)Visitedp-adjvex = 1;printf( %c ,ag.verticesp-adjvex.cData);/Visit Function/EnQueuepQueue = (LinkNode*)malloc(sizeof(LinkNode);if(!pQueue)return;pQueue-parc = p;pQueue-next = NULL;last-next = pQueue;last = last-next;/指向最后一个元素的指针/EnQueue overp = p-nextarc;/DeQueuetemp = Queue-next;p = ag.verticestemp-parc-adjvex.firstarc;Queue -next = temp-next;/DeQueue overfor(i=0; iag.vexnum; i+)/打印出孤立点if(!Visitedi)printf( %c ,ag.verticesi.cData);p = ag.verticesi.firstarc;if(i = ag.vexnum)break;printf(nn);int 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的图最多的边的数量为mwhile(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);printf(n开始进行图的遍历!n);while(1)/起始点有效性验证printf(请输入深度优先遍历的开始结点:);fflush(stdin);scanf(%d,&choose);if(choose=0 & choose=0 & choosen) break;else printf(重