Algorithms and Datastrucstures: Graphs 图的存储结构 3、十字链表 向图G1 实例: 用途:用于有向图,査询 进入结点和离开结点 的边容易 tailvex headyex hlink tlink 01彐[02_入 A 0 c 0 2 3 F30彐F3132入入 16 data firstin firstout ALDS
16 物料管理 ALDS 16 Algorithms and DataStrucstures:Graphs 图的存储结构 3、十字链表 •实例： A B C D 向图 G1 0 1 2 3 A B C D 0 1 0 2 2 2 2 0 3 0 3 3 3 1 ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ data firstin firstout tailvex headvex hlink tlink •用途：用于有向图， 查询 进入结点和离开结点 的边容易
Algorithms and Datastrucstures: Graphs 图的存储结构 4、邻接多重表 data:结点的数据场,保存结点的 结点表中的结点的表示: 数据值 firstedge:结点的指针场,给出自该 结点出发的的第一条边的 data firstedge 边结点的地址。 边结点表中的结点的表示: info:边结点的数据场,保存边的 mark ivex ilink jvex jlink 权值等。 fo mark:边结点的标志域,用于标识 ivex:本条边依附的一jvex:本条边依附的另 该条边是否被访问过 个结点的地址。 一个结点的地址 link:依附于该结点(地jink:依附于该结点(地 址由ⅳvex给出)的 址由vex给出)的 边中的下一条边的 边中的下一条边的 的地址。 的地址。 ALDS
17 物料管理 ALDS 17 Algorithms and DataStrucstures:Graphs 图的存储结构 4、邻接多重表 data firstedge mark ivex ilink •边结点表中的结点的表示： •结点表中的结点的表示： data:结点的数据场，保存结点的 数据值。 firstedge: 结点的指针场，给出自该 结点出发的的第一条边的 边结点的地址。 info: 边结点的数据场，保存边的 权值等。 mark:边结点的标志域，用于标识 该条边是否被访问过。 jvex info ivex: 本条边依附的一 个结点的地址。 ilink: 依附于该结点（地 址由ivex给出）的 边中的下一条边的 的地址。 jlink jvex: 本条边依附的另 一个结点的地址。 jlink: 依附于该结点（地 址由jvex给出）的 边中的下一条边的 的地址
Algorithms and Datastrucstures: Graphs 图的存储结构 4、邻接多重表 实例: 无向图G2 用途:用于无向图,边表中 的边结点只需存放 次,节约内存。 mark ivex ilink jex jlink data firstedge 112 1∧3 B 3 凵3T5 2^4 4|D 5E 5■[2 5∧ 18 ALDS
18 物料管理 ALDS 18 Algorithms and DataStrucstures:Graphs 图的存储结构 4、邻接多重表 •实例： 无向图 G2 •用途：用于无向图，边表中 的边结点只需存放一 次，节约内存。 A B C D E A B 1 2 3 4 5 data firstedge C D E 1 2 3 5 5 2 4 2 1 3 4 5 ∧ ∧ ∧ ∧ markivex ilink jvex jlink ∧
Algorithms and Datastrucstures: Graphs 图的遍历 图的两种常见的遍历形式 深度优先搜索 广度优先搜索 1、深度优先搜索 注意:每个结点只能被访问一次,又因为一个结点可以和其它的任何结点相邻接, 为了避免对一个结点的重复访问,必须对访问过的结点加以标记。 结点的邻接结点的次序是任意的,因此深度优先搜索的序列可能有多种。 深度优先搜索类似于树的前序周游。 访问方式:1、选中第一个被访问的结点。 2、对结点作已访问过的标志。 3、依次从结点的未被访问过的第一个、第二个、第三个…邻接结 点出发,进行深度优先搜索。转向2。 4、如果还有顶点未被访问,则选中一个起始结点,转向2 5、所有的结点都被访问到,则结束。 ALDS
19 物料管理 ALDS 19 Algorithms and DataStrucstures:Graphs 图的遍历 图的两种常见的遍历形式： •深度优先搜索 •广度优先搜索 1、深度优先搜索 •注意：每个结点只能被访问一次，又因为一个结点可以和其它的任何结点相邻接， 为了避免对一个结点的重复访问，必须对访问过的结点加以标记。 结点的邻接结点的次序是任意的，因此深度优先搜索的序列可能有多种。 深度优先搜索类似于树的前序周游。 •访问方式：1、选中第一个被访问的结点。 2、对结点作已访问过的标志。 3、依次从结点的未被访问过的第一个、第二个、第三个…… 邻接结 点出发，进行深度优先搜索。转向2。 4、如果还有顶点未被访问，则选中一个起始结点，转向2。 5、所有的结点都被访问到，则结束
Algorithms and Datastrucstures: Graphs 图的遍历 1、深度优先搜索:续 有向图的实例:为了说明问题,邻接结点的访问次序以序号为准。序号小的先访问。如: 结点5的邻接结点有两个6、7,则先访问结点6,再访问结点7 从结点1出发的搜索序列 1、2、3、4没有搜索 到所有的结点,必 须另选图中未访 问过的结点 从结点(5出发的搜索序列 继续进行 5、6、2、3、14、7 搜索。 适用的数据结构:栈 ALDS
20 物料管理 ALDS 20 Algorithms and DataStrucstures:Graphs 图的遍历 1、深度优先搜索:续 •有向图的实例：为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。如： 结点 5 的邻接结点有两个 6、7，则先访问结点 6，再访问结点 7。 5 6 7 2 4 1 3 5 6 7 2 3 1 4 · · · · · · · 从结点 出发的搜索序列： 5、6、2、3、1、4、7 适用的数据结构：栈 5 1 2 4 3 · · · · 从结点 出发的搜索序列： 1、2、3、4没有搜索 到所有的结点，必 须另选图中未访 问过的结点， 继续进行 搜索。 1