《MATLAB程序设计基础与应用》图论.ppt

树和图的简单介绍;

树的定义和基本术语

定义：树(Tree)是n(n=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：

（1）有且仅有一个特定的称为根(Root)的结点；

（2）其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3…Tm,其中每个子集又是一棵树，并称其为子树(Subtree)。;例：下面的图是一棵树;树的基本术语

树结点：包含一个数据元素及若干指向子树的分支；

孩子结点：结点的子树的根称为该结点的孩子；

双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；

兄弟结点：同一双亲的孩子结点；

堂兄结点：同一层上结点；

结点层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；

树的高（深）度：树中最大的结点层

结点的度：结点子树的个数

树的度：树中最大的结点度。

叶子结点：也叫终端结点，是度为0的结点；

分枝结点：度不为0的结点（非终端结点）；

森林：互不相交的树集合；

有序树：子树有序的树，如：家族树；

无序树：不考虑子树的顺序；;;;A;完全图：有n(n-1)/2条边的无向图。其中n是结点个数。

有向完全图：有n(n-1)条边的有向图。其中n是结点个数。

边的权值:边有权的图称之为网。

邻接点：

无向图结点的度/次数

有向图结点的出度和入度;1.关联矩阵;2.邻接矩阵;返回;图的建立：图顶点号从1开始计，数组下标按C/C++习惯从0计算;3、邻接表;边表中的结点的形式;实例：;逆邻接表——对有向图而言;有向图邻接表建立;图的遍历：

深搜（dfs）用堆栈

广搜（bfs）用队列

;从某个源点到其余各顶点的最短路径（单源最短路径问题）;3.算法实现分析

设一个集合U，存放已产生的最短路径的顶点。初始，U只包含源点v0;4.Dijkstra算法描述;7.Dijkstra算法的C语言描述

由于C/C++的下标从0开始，所以算法中作相应的改动，用NUM代表图的顶点数;生成树：极小连通子图。包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。;最小代价生成树（简称：最小生成树）;2.求最小生成树的原则

（1）选取n-1条边连通图

（2）尽量选取边??小的边;例;4.Prim算法;Prim算法实现：;lowcost:;lowcost:;lowcost:;lowcost: