数据结构图研究.ppt

　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,w是一条弧，则称v邻接到w，或者w邻接自v。 * 极大就是不能再大，或者说再大也不能超过自己。因此，极大连通子图就是： 设 ? ? 1) ? S为G的子图，S连通， ? ? 2) ? 如果有S ’也是G的连通子图，且S是S ’的子图，可推出S ? = ? S ’， 则称S是G的极大连通子图。 极小连通子图正好相反，极小就是不能再小，再多小一点就会不连通或点不足。因此，极小连通子图就是： 设 ? ? 1) ? S为G的子图，S连通， ? ? 2) ? 如果有S ’也是G的连通子图，S ’包含G的所有顶点，且S ’是S的子图，可推出S ’? = ? S， 则称S是G的极小连通子图。  * * 指针就是一个变量，里面存储的是另一个变量的地址。 * 指针就是一个变量，里面存储的是另一个变量的地址。 * 指针就是一个变量，里面存储的是另一个变量的地址。 * 其余最短路径的特点： 再下一条路径长度次短的路径的特点: 它可能有三种情况：或者是，直接从源点到该点(