霍夫曼编码(构造算法思想和过程)

1、回顾n霍夫曼编码（构造算法思想和过程）n线性结构n操作受限的线性结构n树结构n图结构v图的定义和术语图的定义和术语v图的存储结构图的存储结构v图的遍历图的遍历v最小生成树最小生成树v有向无环图与拓扑排序有向无环图与拓扑排序v最短路径最短路径图定义图定义 图是由顶点集合图是由顶点集合(vertex)及顶点间的关系及顶点间的关系集合组成的一种数据结构：集合组成的一种数据结构： ADT Graph 数据对象数据对象V V: V是具有相同特性的数据元素的集合，称为顶顶 点集点集。 数据关系数据关系R R: R=VR VR= | v, w V & P (v, w) , 表示从 v 到 w 的一条

2、弧弧,v为弧尾弧尾，w为弧头弧头；P(v,w) 定义了弧的意义或信息 弧是有方向的，图为有向图n无向图无向图 若若 VR 则必有则必有 VR, 则则用用边边(v,w)记之，此图称为记之，此图称为无向图无向图。 有向图中，顶点对有向图中，顶点对 是有序的。是有序的。无向图中顶点对无向图中顶点对(v, w)是无序的。是无序的。n完全图完全图若有若有 n 个顶点的无向图有个顶点的无向图有 n(n-1)/2 条边条边, 则则此图为此图为无向完全图无向完全图。有。有 n 个顶点的有向图有个顶点的有向图有n(n-1) 条边条边, 则此图为则此图为有向完全图有向完全图。00001111222265433 n

3、邻接点邻接点(Adjacent) 如果如果 (u, v) 是是 E(G) 中的一条边，则称中的一条边，则称 u 与与 v 互为邻接点。互为邻接点。n子图子图(Subgraph)设有两个图设有两个图 G(V, E) 和和 G(V, E)。若。若 V V 且且 E E, 则称则称 图图G 是是 图图G 的子图。的子图。n权权(Weight)某些图的边具有与它相关的数某些图的边具有与它相关的数, 称称之为权。这种带权图叫做之为权。这种带权图叫做网网(network)。0123子图子图0130123023n顶点的度顶点的度(Degree)一个顶点一个顶点v的度是与它相关的度是与它相关联的边的条数。记作

4、联的边的条数。记作TD(v)。n顶点顶点 v 的入度的入度(InDegree)是以是以 v 为终点的有为终点的有向边的条数向边的条数, 记作记作 ID(v); 顶点顶点 v 的出度的出度是以是以 v 为始点的有向边的条数为始点的有向边的条数, 记作记作 OD(v)。 有向图中有向图中, TD(v)= ID(v)+ OD(v) n路径路径(Path) 在图在图 G(V, E) 中中, 若从顶点若从顶点 vi 出发出发, 沿一些边经过一些顶点沿一些边经过一些顶点 vp1, vp2, , vpm，到达顶点到达顶点vj。则称顶点序列。则称顶点序列 (vi vp1 vp2 vpm vj) 为从顶点为从顶

5、点vi到顶点到顶点 vj 的的路径路径。它经过的边。它经过的边(vi ,vp1 )、(vp1, vp2)、.、(vpm ,vj) 应是属于应是属于E的边。的边。顶点的出度顶点的出度: : 以顶点以顶点v 为弧尾的为弧尾的 弧的数目弧的数目; ;顶点的入度顶点的入度: : 以顶点以顶点v v为弧头的为弧头的 弧的数目。弧的数目。ABECF有向图有向图顶点的度(TD)=出度(OD)+入度(ID)TD(B) =OD(B)+ID(B) = 3例如例如: :n路径长度路径长度非带权图的路径长度是指此路径上边非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权的条数。带权图的路径长度

6、是指路径上各边的权之和。之和。n简单路径简单路径若路径上各顶点若路径上各顶点 v1,v2,.,vm 均不均不 互互相重复相重复, 则称这样的路径为则称这样的路径为简单路径简单路径。n简单回路简单回路 若路径上第一个顶点若路径上第一个顶点 v1 与最后一个顶与最后一个顶点点vm重合重合, 则称这样的路径为则称这样的路径为回路回路或或环环(Cycle)。012301230123ABECF如如: : 从从A A到到F F长度为长度为 3 的路径：的路径：A,B,C,F还有其他长还有其他长度为度为3 3的路径的路径吗？吗？n连通图与连通分量连通图与连通分量在无向图中在无向图中, 若从顶点若从顶点v1到

7、顶点到顶点v2有路径有路径, 则称顶点则称顶点v1与与v2是是连通连通的。如的。如果图中果图中任意任意一对顶点都是连通的一对顶点都是连通的, 则称此图是则称此图是连连通图通图。非连通图的。非连通图的极大连通子图极大连通子图叫做叫做连通分量连通分量。n强连通图与强连通分量强连通图与强连通分量在有向图中在有向图中, 若对于若对于每一对每一对顶点顶点vi和和vj, 都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径的路径, 则称此图是则称此图是强连通图强连通图。非强连通图的。非强连通图的极极大强连通子图大强连通子图叫做叫做强连通分量强连通分量。无向图无向图中任意两个顶点中任意两个顶点之间

8、都有路径相通，则之间都有路径相通，则称此图为称此图为连通图连通图;若无向图为非连通图，若无向图为非连通图，则图中各个极大连通子则图中各个极大连通子图称作此图的图称作此图的连通分量连通分量。BACDFEBACDFE有向图有向图中任意两个顶点之间都存在一条有向路径，则中任意两个顶点之间都存在一条有向路径，则称此有向图为称此有向图为强连通图强连通图。否则，其各个极大强连通子图称作它的否则，其各个极大强连通子图称作它的强连通分量强连通分量。ABECFABECF生成树生成树（Spanning tree): : 假设一个连通图有假设一个连通图有 n 个顶点和个顶点和 e 条边，其中条边，其中 n-1 条边

9、和条边和 n 个顶点构成一个个顶点构成一个极小连通子图极小连通子图，称该极小连，称该极小连通子图为此连通图的通子图为此连通图的生成树生成树。 在极小连通子图中极小连通子图中增加增加一条边，则一定有环；一条边，则一定有环； 在极小连通子图中极小连通子图中去掉去掉一条边，则成为非连通图。一条边，则成为非连通图。BACDFEBACDFE有有n个顶点和个顶点和n-1条边条边的子图必定是生成树吗？的子图必定是生成树吗？ 生成森林：生成森林：一个有向图的一个有向图的生成森林生成森林由若干棵有由若干棵有向树组成，含有图中全部顶点，且仅包含足以向树组成，含有图中全部顶点，且仅包含足以构成若干棵不相交的有向树的

10、弧。构成若干棵不相交的有向树的弧。BACDFEBACDFE有向树：有向树： 恰有一个顶点入度为恰有一个顶点入度为0，其余顶点入度，其余顶点入度均为均为1的有向图。的有向图。n在图的邻接矩阵表示中，有一个记录各个顶点信在图的邻接矩阵表示中，有一个记录各个顶点信息的息的顶点表顶点表，还有一个表示各个顶点之间关系的，还有一个表示各个顶点之间关系的邻接矩阵邻接矩阵。n设图设图 A = (V, E)是一个有是一个有 n 个顶点的图个顶点的图, 图的邻图的邻接矩阵是一个二维数组接矩阵是一个二维数组 A.arcsnn，定义：，定义：邻接矩阵邻接矩阵 (Adjacency Matrix) , ),( , ,

11、.否否则则 或或若若01AEjiEjijiarcsn无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的;n有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。01230101101001011010A.arcs012000101010A.arcsn在在有向图有向图中中, 统计第统计第 i 行行 1 的个数可得顶的个数可得顶点点 i 的的出度出度，统计第，统计第 i 列列 1 的个数可得顶的个数可得顶点点 i的的入度入度。n在在无向图无向图中中, 统计第统计第 i 行行 (列列) 1 的个数可的个数可得顶点得顶点i 的度。的度。816329542031068053290410A.arc

12、sjiji,ji,jiji,ji,jijiji若若或或且且若若或或且且若若,)(,)(),(0EEEEWA.arcs#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /最大顶点个数typedef enumDG,DN,UDG,UDN GraphKind; /图的类型typedef struct ArcCell VRType adj; / VRType为顶点关系类型 InfoType *info; /该弧相关信息指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM ; typedef struct

13、 VertexType vexMAX_VERTEX_NUM; /顶点向量 AdjMatrix arcs; /邻接矩阵 int vexnum,arcnum; /顶点数和弧数 GraphKind kind; /图的种类标志 MTGraph; Status CreateUDN(Mgraph &G) /无向网的构造 scanf(&G.vexnum,&G.arcnum,&IncInfo); for (i=0;iG.vexnum;+i) scanf(&G.vexsi); for (i=0 ;iG.vexnum;+i) /初始化邻接矩阵 for (j=0;jG.vex

14、num;+j) G.arcsij=INFINITY,NULL; for(k=0 ;kG.arcnum;+k) scanf(&v1,&v2,&w); /读入边依附的顶点和权值 i=LocateVex(G,v1); j=LocateVex(G,v2); /顶点定位 G.arcsij.adj=w; /弧的权值 if (IncInfo) Input(* G.); /输入弧的相关信息 G.arcsji=G.arcsij; /置对称弧 return OK; 算法7.2 邻接表邻接表:是图的一种链式存储结构。是图的一种链式存储结构。弧的结点结构弧的结点结构adj

15、vex; / 该弧所指向的顶点的位置该弧所指向的顶点的位置nextarc;/ 指向下一条弧指针指向下一条弧指针 info; / 该弧相关信息的指针该弧相关信息的指针adjvex nextarc info顶点的结点结构顶点的结点结构 data firstarc data; / 顶点信息顶点信息firstarc; /指向第一条依附该顶点的弧指向第一条依附该顶点的弧表结点表结点头结点头结点ABCdata firstarcABC012adjvex nextarc adjvex nextarc 邻接表邻接表 (出边表出边表)102 data firstarcABC012adjvex nextarc 逆邻

16、接表逆邻接表 (入边表入边表) 011求出度方便求入度方便头结点数=n 表结点数=e 同一个顶点发出的边链接在同一个边链表中，同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边每一个链结点代表一条边(边结点边结点), 结点中有另结点中有另一顶点的下标一顶点的下标 adjvex 和指针和指针 nextarc。ABCDdata firstarcadjvex nextarc adjvex nextarc ABCD0123 130210头结点数=n 表结点数=2eBACD69528data firstarcABCD0123adjvex cost nextarc 1 53 62 83 21

17、9(出边表出边表)(顶点表顶点表)#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc;/ 指向下一条弧指针 InfoType *info; / 该弧相关信息的指针 ArcNode;typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertice

18、s; int vexnum,arcnum;/图的当前顶点数和弧数 int kind;/图的种类标志ALGraph;n有向图的另一种链式存储结构有向图的另一种链式存储结构 邻接表表 + 逆邻接表tailvex headvex hlink tlink info弧结点data firstin firstout顶点结点n无向图的另一种链式存储结构无向图的另一种链式存储结构mark ivex ilink jvex jlink info边结点边结点data firstedge顶点结点顶点结点每条边对应一个边结点图的遍历图的遍历n从图中某一顶点出发访遍图中所有的顶点，且使从图中某一顶点出发访遍图中所有的顶点

19、，且使每个顶点仅被访问一次，这一过程就叫做每个顶点仅被访问一次，这一过程就叫做图的遍图的遍历历 (Traversing Graph)。n图中可能存在回路，且图的任一顶点都可能与其图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。某些边又回到了曾经访问过的顶点。n为了避免重复访问，可设置一个标志顶点是否被为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组访问过的辅助数组 visited 。n辅助数组辅助数组 visited 的初始状态为的初始状态为 0, 在图的遍历过程中在图的遍历

20、过程中, 一旦某一个顶点一旦某一个顶点 i 被被访问访问, 就立即让就立即让 visited i 为为 1, 防止它防止它被多次访问。被多次访问。n两种图的遍历方法两种图的遍历方法:u深度优先搜索深度优先搜索 DFS (Depth First Search)u广度优先搜索广度优先搜索 BFS (Breadth First Search)深度优先搜索深度优先搜索DFS ( Depth First Search )n深度优先搜索过程深度优先搜索过程67ACDEGBFIHACDEGBFIH1234589123456789前进回退深度优先生成树深度优先生成树nDFS 在访问图中某一起始顶点在访问图中某

21、一起始顶点 v 后后, 由由 v 出发出发, 访问它的任一邻接顶点访问它的任一邻接顶点 w1; 再从再从 w1 出发出发,访问与访问与 w1邻邻 接但还没有访问过的顶接但还没有访问过的顶点点 w2; 然后再从然后再从 w2 出发出发, 进行类似的访进行类似的访问问, 如此进行下去如此进行下去, 直至到达所有的邻接直至到达所有的邻接顶点都被访问过的顶点顶点都被访问过的顶点 u 为止。接着为止。接着, 退退回一步回一步, 退到退到前一次刚访问过的顶点前一次刚访问过的顶点, 看是看是否还有其它没有被访问的邻接顶点。如果有否还有其它没有被访问的邻接顶点。如果有, 则访问此顶点则访问此顶点, 之后再从此

22、顶点出发之后再从此顶点出发, 进行进行与前述类似的访问与前述类似的访问; 如果没有如果没有, 就再退回一就再退回一步进行搜索。重复上述过程步进行搜索。重复上述过程, 直到连通图中直到连通图中所有顶点都被访问过为止所有顶点都被访问过为止。图的深度优先搜索算法图的深度优先搜索算法Boolean visitedMAX;Status (* VisitFunc)(int v);void DFSTraverse (Graph G,Status (* Visit)(int v) VisitFunc =Visit; for ( v= 0; v G.vexnum; v+ ) visited v = FALSE;

23、 /访问数组 visited 初始化 for ( int v = 0; v =0;w=NextAdjVex(G,v,w) if ( !visitedw ) DFS (G, w, visited ); /若顶点 w 未访问过, 递归递归访问顶点 w 算法算法 7.5时间复杂度分析：DFS是对每个顶点查找其邻接点的过程 邻接矩阵O(n2) vs. 邻接表O(n+e)广度优先搜索广度优先搜索BFS ( Breadth First Search )n广度优先搜索过程广度优先搜索过程7ACDEGBFIHACDEGBFH12345678912345689广度优先生成树广度优先生成树InBFS在访问了起始顶点在访问了起始顶点 v 之后之后, 由由 v 出发出发, 依次访依次访问