数据结构4（图）.pptVIP

　1. 熟悉图的存储结构及其构造算法： 邻接矩阵 和 邻接表 　2. 熟练掌握图的两种有哪些信誉好的足球投注网站路径的遍历算法： 深度优先有哪些信誉好的足球投注网站 和 广度优先有哪些信誉好的足球投注网站。 在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。 总 结 3. 应用图的遍历算法求解： 顶点i到顶点s的简单路径； 两个顶点之间路径长度最短的路径； 4. 理解教科书中各种图的算法： 最小生成树：普里姆算法和克鲁斯卡尔算法 最短路径：一点到其余各点：Dijkstra 任意两点之间：Floyd 拓扑排序： 关键路径： * * 两种常用存储结构 （1）顺序存储结构: 用存储结点间的位置关系表示数据元素之间的逻辑关系。 元素n …….. 元素i …….. 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+(n-1)*m 存储地址 存储内容 Loc(元素i)=L0+ (i-1)*m 例如：(133，400，749，840) 1200 1202 1204 1206 749 400 840 133 存储内容 存储地址 * （2）链式存储结构：用附加的指针表示数据元素之间的逻辑关系。 1536 400 1400 133 1346 749 NULL 840 1200 h 例如：(133，400，749，840) 1346 749 1536 ……. …….. ……. 1536 400 1400 ……. …….. ……. NULL 840 1346 1400 133 …… 指针 存储内容 存储地址 1200 …… …… 指针就是一个变量，里面存储的是另一个变量的地址。 * 指针就是一个变量，里面存储的是另一个变量的地址。 zhang typedef struct student{ int no; char name[4]; struct student *next; }ST, *PST; PST pointer; PST pref=pointer; pointer 1 1012 1000 wang 2 2010 1012 li 3 0 2010 1000 指针就是一个变量，里面存储的是另一个变量的地址。 引用 相当于给一个变量起别名 1.普通的引用变量 int a; int b = a; 2.函数的形参为引用变量 int CreateTree(Tree T) * typedef struct student{ int no; char name[4]; struct student *next; }ST, *PST; PST pointer; PST pref=pointer; b 20 a A B E C D 15 9 7 21 11 3 2 写出图的邻接矩阵 ∞ 15 ∞ ∞ 9 ∞ ∞ 3 ∞ ∞ ∞ ∞ ∞ 2 ∞ 11 7 ∞ ∞ ∞ ∞ ∞ 21 ∞ ∞ D B A C F E A 1 4 B 0 4 5 C 3 5 D 2 5 E 0 1 F 1 2 3 0 1 2 3 4 5 * 画出图的邻接表 指针就是一个变量，里面存储的是另一个变量的地址。 * 指针就是一个变量，里面存储的是另一个变量的地址。 * 指针就是一个变量，里面存储的是另一个变量的地址。 * 设置一个辅助数组，对当前V－U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边： struct { VertexType adjvex; // U集中的顶点序号 VRType lowcost; // 边的权值 } closedge[MAX_VERTEX_NUM]; a b c d e g f 19 5 14 18 27 16 8 21 3 12 7 a e d c b a a a 19 14 18 14 例如: e 12 e e 8 16 8 d 3 d d 7 21 3 c 5 5 19 m m 14 m 18 19 5 7 12 m m m 5 3 m m m m 7 3 8 21 m 14