北京大学：《数据结构与算法》课程教学资源（实习课件PPT）图论习题课

图论习题课 喻立久 2007-12-12 图论习题课

图论习题课 图论习题课 喻立久 2007-12-12

主要内容 图的存储结构 图的周游 图的典型应用 AcM题目选讲 图论习题课

图论习题课 主要内容 „ 图的存储结构 „ 图的周游 „ 图的典型应用 „ ACM题目选讲

图的存储结构 边集数组 ■相邻矩阵 邻接表(逆邻接表) 十字链表 图论习题课

图论习题课 图的存储结构 „ 边集数组 „ 相邻矩阵 „ 邻接表（逆邻接表） 邻接表（逆邻接表） „ 十字链表

图的存储结构 边集数组 例: (13) (24) (14) 图论习题课

图论习题课 图的存储结构 „ 边集数组 „ 例： „ (1,2) „ (1,3) „ (2,4) „ (1,4)

图的存储结构 边集数组 好处: 存储结构简单 缺点 使用不够灵活 图论习题课

图论习题课 图的存储结构 „ 边集数组 „ 好处： „ 存储结构简单 „ 缺点 „ 使用不够灵活

图的存储结构 ■相邻矩阵 优点 容易判断两点是否有边 快速求得入度和出度 判断两点之间是否有长度为m的路径。A 缺点 n稀疏图时浪费空间。 图论习题课

图论习题课 图的存储结构 „ 相邻矩阵 „ 优点 „ 容易判断两点是否有边 „ 快速求得入度和出度 „ 判断两点之间是否有长度为m的路径。A „ 缺点 „ 稀疏图时浪费空间。 m

图的存储结构 邻接表 解决了邻接矩阵当图稀疏时浪费空间的问题 对一个确定的图邻接表不唯一 需要|V|+|E(无向图|V|+2|E)个存储单元 计算无向图顶点的度:单锥表中锥接的结点个数 计算有向图顶点的出度和入读: 出度:单出边表中接的结点数 入度:历全表 图论习题课

图论习题课 图的存储结构 „ 邻接表 „ 解决了邻接矩阵当图稀疏时浪费空间的问题 解决了邻接矩阵当图稀疏时浪费空间的问题 „ 对一个确定的图邻接表不唯一 对一个确定的图邻接表不唯一 „ 需要|V|+|E|( |V|+|E|(无向图|V|+2|E|) |V|+2|E|)个存储单元 „ 计算无向图顶点的度 计算无向图顶点的度:单链表中链接的结点个数 单链表中链接的结点个数 „ 计算有向图顶点的出度和入读 计算有向图顶点的出度和入读: „ 出度：单链出边表中链接的结点数 „ 入度：遍历全表

图的存储结构 十字链表 弧结点 tailvexheadvex hlink tlink in」顶点结点 data Firstin Firstout tai lex:弧尾顶点位置 headvex:弧头顶点位置 hl ink:弧头相同的下一弧位置 data:顶点信息 tlink:弧尾相同的下一弧位置 info:弧信息 Firstin:以顶点为弧头的第一条弧结点 Firstout:以顶点为弧尾的第一条弧结点 注:图时只有 图论习题课

图论习题课 图的存储结构 „ 十字链表 tailvex tailvex headvex headvex hlink tlink info 弧结点 tailvex: 弧尾顶点位置 headvex: 弧头顶点位置 hlink: 弧头相同的下一弧位置 tlink: 弧尾相同的下一弧位置 info: 弧信息 顶点结点 data : 顶点信息 Firstin : 以顶点为弧头的第一条弧结点 Firstout: 以顶点为弧尾的第一条弧结点 注:无向图时只有一个链接域 data Firstin Firstin Firstout Firstout

图的存储结构 十字链表 顶点结点 弧结点 01A 03 12AN 23 E +40An 图论习题课

图论习题课 图的存储结构 „ 十字链表 顶点结点 弧结点 D A E B C

图的存储结构 十字链表 优点 在比较复杂的处理中,有时需要给某些边加标记 如果用邻接表来表示,使用很不方便,因为对于无 向图需要在不同的单链表中找到节点。如果用十字 链表就很方便。 图论习题课

图论习题课 图的存储结构 „ 十字链表 „ 优点 „ 在比较复杂的处理中，有时需要给某些边加标记， 在比较复杂的处理中，有时需要给某些边加标记， 如果用邻接表来表示，使用很不方便，因为对于无 如果用邻接表来表示，使用很不方便，因为对于无 向图需要在不同的单链表中找到节点。如果用十字 向图需要在不同的单链表中找到节点。如果用十字 链表就很方便。 链表就很方便