第7章 图 7.1基本术语 7.2存储结构 7.3图的遍历 7.4图的其他运算 7.5图的应用
1 7.1 基本术语 7.2 存储结构 7.3 图的遍历 7.4 图的其他运算 7.5 图的应用 第7章 图
7.2 图的存储结构 1.邻接矩阵（数组）表示法 顺序存储 2.邻接表（链式）表示法 3.十字链表表示法 链式存储 4.邻接多重表表示法 各种表示法成立的原则： 一存入电脑后能惟一复原！ 2
2 7.2 图的存储结构 1.邻接矩阵(数组)表示法 2.邻接表(链式)表示法 3. 十字链表表示法 4. 邻接多重表表示法 顺序存储 链式存储 各种表示法成立的原则： —— 存入电脑后能惟一复原！
3。十字链表表示法 它是有向图的另一种链式结构。 思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。 1、开设弧结点，设5个域（每段弧是一个数据元素) 2、开设顶点结点，设3个域（每个顶点也是一个数据元素) 弧结点 顶点结点 tailvex headvex hlink tlink info data Firstin Firstout tai lvex:弧尾顶点位置 data:顶点信息 headvex: 弧头顶点位置 Firstin：以顶点为弧头的第一条弧结点 hlink: 弧头相同的下一弧位置 Firstout::以顶点为孤尾的第一条孤结点 tlink: 弧尾相同的下一弧位置 info: 弧信息 逆邻接表 邻接表
3 它是有向图的另一种链式结构。 思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。 1、开设弧结点，设5个域（每段弧是一个数据元素） 2、开设顶点结点，设3个域（每个顶点也是一个数据元素） tailvex headvex hlink tlink info data : 顶点信息 Firstin : 以顶点为弧头的第一条弧结点 Firstout: 以顶点为弧尾的第一条弧结点 data Firstin Firstout 弧结点 顶点结点 3. 十字链表表示法 tailvex: 弧尾顶点位置 headvex: 弧头顶点位置 hlink: 弧头相同的下一弧位置 tlink: 弧尾相同的下一弧位置 info: 弧信息 邻接表 逆邻接表
例：画出有向图的十字链表。 顶点结点data Firstin Firstout 孤结点 tailvex headvex hlink tlink 无权图可省最后分量 2 A 3 是邻接表、逆 邻接表的结合 十字链表优点：容易操作，如求顶点的入度、出度等。 空间复杂度和建表的时间复杂度都与邻接表相同
4 v1 v2 v3 v4 2 0 2 3 ^ ^ 3 0 ^ 3 1 ^ ^ 例：画出有向图的十字链表。 十字链表优点：容易操作，如求顶点的入度、出度等。 顶点结点 data Firstin Firstout 弧结点 tailvex headvex hlink tlink info 0 v1 1 v2 2 v3 3 v4 0 1 2 3 0 1 0 2 ^ ^ 无权图可省最后分量 空间复杂度和建表的时间复杂度都与邻接表相同。 是邻接表、逆 邻接表的结合
4、邻接多重表表示法 这是无向图的另一种存储结构，当对边操作时建议采用此种结构存储。 1、设立边结点，6个域（每条边是一个数据元素) 2、设立顶点结点， 2个域（每个顶点也是一个数据元素)》 边结点 顶点结点 mark ivex ilink jvex jlink info data Firstedge mark:标志域（标记该边是否被访问】 data 存储顶点信息 ivex, jvex:边依附的两个顶点位置 Firstedge:依附顶点的第一 ilink:指向下一条依附顶点i的边位置 条边结点 jlink；指向下一条依附顶点j的边位置 info: 边信息 十字链表其实就是有向图的邻接多重表！
5 这是无向图的另一种存储结构，当对边操作时建议采用此种结构存储。 1、设立边结点， 6个域（每条边是一个数据元素） 2、设立顶点结点， 2个域（每个顶点也是一个数据元素） mark ivex ilink jvex jlink info 边结点 data : 存储顶点信息 Firstedge : 依附顶点的第一 条边结点 data Firstedge 顶点结点 4. 邻接多重表表示法 mark：标志域（标记该边是否被访问） ivex， jvex : 边依附的两个顶点位置 ilink: 指向下一条依附顶点 i 的边位置 jlink; 指向下一条依附顶点 j 的边位置 info: 边信息 十字链表其实就是有向图的邻接多重表！