实验报告1_图课件

《实验报告1_图课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第2章线性表LinearList实验：图形结构此次实验包括4个课时，要求撰写实验报告，并按照实验报告格式认真填写并提交电子版实验报告。由于课时紧张，所以要求同学们除了在上机课上编写调试程序外，还需要认真保存结果，并利用课余时间继续编写调试，直至完成实验报告要求！2第2章线性表LinearList实验：图形结构实验目的：熟练掌握图形结构的两种存储方法和遍历方法。3第2章线性表LinearList实验：图形结构实验内容：编写一个程序，实现图的相关运算，并在此基础上设计一个主程序完成一下功能：建立图8.26所示

2、的有向图G的邻接矩阵并输出2.建立图8.26所示的有向图G的邻接表并输出3.由有向图G的邻接矩阵产生邻接表并输出4.输出有向图G从顶点0开始的深度优先遍历序列5.输出有向图G从顶点0开始的广度优先遍历序列4第2章线性表LinearList实验：图形结构实验环境：操作系统：WindowsXP编程语言：C/C++编程工具：VisualC++6.05第2章线性表LinearList实验：图形结构实验方法和步骤（例如）建立图8.26所示的有向图G的邻接矩阵并输出设G=(V,E)是具有n(n＞0)个顶点的图，顶点的顺

3、序依次为(v0,v1,…,vn-1)，则G的邻接矩阵A是n阶方阵，如果G是有向图,则：A[i][j]=1:若∈E(G)0:其他则由图8.26可得下列矩阵：（略）则需要创建一个二维数组edges[MAXV][MAXV]来存放该矩阵。。。。。。。。。。6第2章线性表LinearList实验：图形结构实验方法和步骤（例如）2.建立图8.26所示的有向图G的邻接表并输出表头结点表结点。。。。。画出相应的邻接表图7第2章线性表LinearList实验：图形结构实验方法和步骤（例如）3.由有向图G的邻接矩

4、阵产生邻接表并输出算法思路：在邻接矩阵上查找值不为0的元素，找到这样的元素后创建一个表结点并在邻接表对应的单链表中采用前插法插入该结点。。。。。。。。8第2章线性表LinearList实验：图形结构实验方法和步骤（例如）4.输出有向图G从顶点0开始的深度优先遍历序列过程:……..9第2章线性表LinearList实验：图形结构实验方法和步骤（例如）5.输出有向图G从顶点0开始的广度优先遍历序列过程:……..10第2章线性表LinearList实验：图形结构Tips：11第6章图Graph6.2.2邻接表存储

5、方法例9.2给定一个具有n个结点的无向图的邻接矩阵和邻接表。(1)设计一个将邻接矩阵转换为邻接表的算法；(2)设计一个将邻接表转换为邻接矩阵的算法；(3)分析上述两个算法的时间复杂度。解：(1)在邻接矩阵上查找值不为0的元素，找到这样的元素后创建一个表结点并在邻接表对应的单链表中采用前插法插入该结点。算法如下：12第6章图GraphvoidMatToList(MGraphg,ALGraph*&G)/*将邻接矩阵g转换成邻接表G*/{inti,j,n=g.vexnum;ArcNode*p;/*n为顶点数*/G

6、=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;iadjlist[i].firstarc=NULL;for(i=0;i=0;j--)if(g.edges[i][j]!=0){p=(ArcNode*)malloc(sizeof(ArcNode));/*创建结点*p*/p->adjvex=j;p->nextarc=G->adjlist[i].firsta

7、rc;/*将*p链到链表后*/G->adjlist[i].firstarc=p;}G->n=n;G->e=g.arcnum;}13第6章图Graph6.3.2深度优先搜索遍历深度优先搜索遍历的过程是：从图中某个初始顶点v出发，首先访问初始顶点v，然后选择一个与顶点v相邻且没被访问过的顶点w为初始顶点，再从w出发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。显然，这个遍历过程是个递归过程。以邻接表为存储结构的深度优先搜索遍历算法如下(其中，v是初始顶点编号，visited[]是一个全局数

8、组，初始时所有元素均为0表示所有顶点尚未访问过)：14第6章图Graph6.3.2深度优先搜索遍历voidDFS(ALGraph*G,intv){ArcNode*p;visited[v]=1;/*置已访问标记*/printf("%d",v);/*输出被访问顶点的编号*/p=G->adjlist[v].firstarc;/*p指向顶点v的第一条弧的弧头结点*/while(p!=NULL){if(visited[p-