广度优先搜索和深度优先搜索的区别（广度优先搜索序列和深度优先搜索序列）

第七章 图 学习要点 理解图的基本概念及有关术语，掌握图的四种存储结构的表示方法，并能根据实际问题选择合适的存储结构； 熟练掌握图的两种遍历（深度优先搜索和广度优先搜索）的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列； 理解最小生成树的概念，能按Prim算法构造最小生成树； 体会求最短路径、拓扑排序以及关键路径的算法思想。 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 以邻接表为存储结构的深度优先遍历算法: 7.2.3 十字链表 　　十字链表是将有向图的邻接表和逆邻接表结合起来的一种有向图链式存储结构。 结点结构 有向图的每一条弧有一个弧结点，每一个顶点必有一个顶点结点，其结构为： ? 弧结点 顶点结点 tailvex: 指示弧尾顶点的位置； headvex: 指示弧头顶点的位置； hlink: 指向弧头相同的下一条弧； tlink: 指向弧尾相同的下一条弧 info: 　　指向该弧的相关信息 vertex: 存放顶点的有关信息 （如顶点的名称，或位置） firstin: 指向以该顶点为弧头的 第一个弧结点； firstout: 指向以该顶点为弧尾 的第一个弧结点。 headvex tlink hlink info tailvex firstout firstin vertex 整体结构 　　通过hlink将弧头相同的弧连在一个链表上； 　　通过tlink将弧尾相同的弧连在一个链表上; 　　hlink链和tlink链的头结点就是顶点结点 例 1 2 3 4 1 2 3 4 1 3 1 2 3 4 3 1 4 3 4 2 4 1 ^ ^ ^ ^ ^ ^ ^ ^ 1 4 3 2 特点： ① 顶点结点数=顶点数 ； 弧结点数=弧的条数 ② 求入度：从顶点Vi出发，沿着hlink所经过的弧结点数 求出度：从顶点Vi出发，沿着tlink所经过的弧结点数 有向图的十字链表存储结构： #define MAX_VERTEX_NUM 20 typedef struct ArcBox { int tailvex,headvex; struct ArcBox * hlink,tlink; InfoType info; }ArcBox; typedef struct VexNode { VertexType vertex; ArcBox fisrin, firstout; }VexNode; typedef struct { VexNode xlist[MAX_VERTEX_NUM]; int vexnum,arcnum; }OLGraph; /*弧的尾和头顶点的位置*/ /*指向头相同和尾相同弧的链域 */ /*该弧相关信息*/ /*指向该顶点第一条入弧和出弧*/ /*顶点相关信息 */ /*有向图的顶点数和弧数*/ /*表头数组*/ 建立有向图的十字链表： void CreateDG(LOGraph *G) { scanf(G-brcnum,G-arcnum); for(i=0;iG-vexnum;i++){ scanf(G-xlist[i].vertex); G-xlist[i].firstin=NULL;G-xlist[i].firstout =NULL; } for(k=0;kG.arcnum;k++){ scanf(v1,v2); i=LocateVex(G,v1); j=LocateVex(G,v2); p=(ArcBox*)malloc(sizeof(ArcBox)); p-tailvex=i; p-headvex=j; p-tlink=G-xlist[i].firstout; G-xlist[i].firstout=p; p-hlink=G-xlist[j].fistin; G-xlist[j].fisrtin=p; } } /*构造表头数组*/ /*输入各弧并构造十字链表*/ /*确定v1和v2在G中位置*/ /*结点赋值*/ /*出弧的插入*/ /*入弧的插入*/ 7.2.4 邻接多重表 　　邻接多重表是无向图的另一种链式存储结构。 　　每一个顶点有一个顶点结点，顶点结点结构为： 　　图的每一条边有一个边结点，边结点的结构为： 其中：vertex存放顶点的信息。 firstedge指向第一条依附于该顶点的边结点。 mar

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/rgzn-sdxx/49543.html