计算机软件技术基础-课件 第3章 非线性结构

线性结构（线性表、栈、队、串、数组）数据结构逻辑结构物理（存储）结构数据运算非线性结构树结构图结构顺序结构链式结构插入运算删除运算修改运算查找运算排序运算数据结构课程的内容第三章非线性结构3.1树和二叉树

3.1.1树的定义和基本术语

3.1.2树的存储结构

3.1.3二叉树定义和性质 3.1.4二叉树的存储与实现

3.1.5二叉树的遍历

3.1.6树、森林和二叉树的转换3.2图

3.2.1图的定义和基本概念 3.2.2图的存储结构 3.2.3图的遍历非线性结构★非线性结构：至少存在一个数据元素有两个或两个以上的直接前驱（或直接后继）元素的数据结构。★树型结构、图型结构。树形结构,用于描述层次结构的关系。图型结构,用于描述网状结构的关系。3.1树（

Tree）和二叉树3.1.1树的定义和基本术语3.1.2树的存储结构3.1.3二叉树定义和性质3.1.4二叉树的存储与实现3.1.5二叉树的遍历3.1.6树、森林和二叉树的转换特点：

非线性结构，一个直接前驱，但可能有多个直接后继（1：n）,是具有层次关系的数据结构，又是一种递归结构。 3.1.1树的定义和基本术语

1、树的定义

定义：树(Tree)是n(n>=0)个结点的有限集T当n＝0时，T称为空树；当n>0时，它必须满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；（2）其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。注：树的定义具有递归性，即“树中还有树”。树的定义：n（n0）个结点的有限集合。

A

C

G

T2D

H

I

T3J

M

B

E

L

KT1

F3.1.1树的定义和基本术语例某校学生档案管理的组织方式3.1.1树的定义和基本术语树形结构——结点间具有分层次的连接关系3.1.1树的定义和基本术语树形结构——结点间具有分层次的连接关系

总理

国防部

总统

司法部

体育部

内政部…国家警察总局巴黎分局国家宪兵法国的警察机构结点（Node）： 树中的元素，包含数据项及若干指向其子树的分支。根，即根结点(没有前驱)2.树的基本术语结点的度（Degree）：结点拥有的子树数。树的度：树中各结点的度的最大值。叶结点（Leaf）：度为零的结点，也称终端结点（没有后继）。分枝结点：度不为0的结点，也称非终端结点（除了根节点外，也称内部结点）。问：右上图中的结点数＝；树的度＝；133ABCGEIDHFJFLK子结点：一个结点的直接后继。

父结点：一个结点的直接前驱。2.树的基本术语兄弟结点：同一父结点的子结点之间。祖先结点：从根结点到该结点所经分支上的所有结点。子孙结点：以一个结点为根的子树中的任一结点称为该结点的子孙结点。ABCGEIDHFJFLK结点的层次：从根结点到该结点的层数。根结点层次为1；其余结点层次等于其父结点的层次加1。2.树的基本术语树的深度（高度）：树中结点的最大层次。有序树：在树T中，各子树之间有先后次序。森林(Forest)：m(m>=0)棵互不相交的树的集合。问：右上图中树的深度＝4ABCGEIDHFJFLK3.树的基本操作1)建立一空树：Initree()

2)创建树CreatTree(T,规则)3)判断树是否为空：IsEmptyTree(T)

4)求树的深度：DepthTree(T)

5)求树T的树根结点：RootTree(T,x)6)求树T中结点p的父结点：ParentTree(T,p)7)求树T中结点p的最左边的子结点：LeftChild(T,p)树的基本操作8)求树T中结点p的最右边的子结点：RightChild(T,p)9)按某种方式遍历树T：TraverseTree(T)3.1.2树的存储结构讨论1：树是非线性结构，该怎样存储？

——顺序存储、链式存储?

1、树的逻辑结构特点：一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。

2、树的物理结构2、树的物理结构1．)子结点表示法也称树的标准形式存储结构。每一个结点用包含一个结点信息域和多个（指向该结点子结点的）指针域的结构来表示各指针域反映树中结点与结点之间的关系。子结点表示法的结点结构图结点信息子结点1子结点2…子结点m树的子结点表示法的结构图ATBC^^^DEFGHIJ^^K^^^1．)子结点表示法

如何安排指针域的个数？每个结点的指针域个数有两种设置方法：(1)等于该结点的度。(2)等于树的度。2．)父结点表示法结点信息父结点父结点表示法的结点结构图树的父结点表示的结构图A^BCDEFGHIJKT树的示例

树的逆形式存储结构。树中每一个结点用包含一个结点信息域和一个指向该结点父结点的指针域来表示。左图所示的树的父结点表示法如右图所示。3.)子结点兄弟结点表示法子结点兄弟结点表示法的结点结构图A^B^CD^^E^F^G^^H^IJ^^K^对树中结点用包含该结点的信息域、一个指向该结点第一个子结点的指针域和一个指向其下一个兄弟结点的指针域来表示。子结点兄弟结点表示法的结点结构图结点信息指向子结点的指针指向下一个兄弟结点指针树的示例

研究意义：二叉树的结构最简单，规律性最强，算法操作简单；任何树都可以转为唯一对应的二叉树；解决了树的存储结构及其运算中存在的复杂性。二叉树(BinaryTree)二叉树(BinaryTree)3.1.3二叉树定义和性质3.1.4二叉树的存储与实现3.1.5二叉树的遍历3.1.6树、森林和二叉树的转换3.1.3二叉树定义和性质定义：是n（n≥0）个结点的有限集合，该集合或为空、或由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：

一对二（1：2）

基本特征:①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒（有序树）。1.二叉树的定义二叉树的五种基本形态空二叉树仅有根结点右子树为空左子树为空左右子树均非空3.1.3二叉树定义和性质基本形态：3.1.3二叉树定义和性质问：具有3个结点的二叉树可能有几种不同形态？

有5种。树与二叉树的区别：A．树中结点的最大度数没有限制，二叉树结点最大度数为2。B．树的结点子树无左、右之分，二叉树的结点子树有明确的

左、右之分。

二叉树树2.二叉树的性质性质1

二叉树的第i层上至多有2i-1（i

1）个结点。423167891011121314155第三层上(i=3)，有23-1=4个节点。第四层上(i=4)，有24-1=8个节点。2.二叉树的性质(3+2)性质2

深度为k的二叉树中至多含有2k-1个结点。此树的深度h=4，共有24-1=15个结点。2.二叉树的性质(3+2)深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数：20+21+22+……+2k-1=2k-1423167891011121314155性质3

对于任意一棵非空二叉树，如果叶子结点数为n0，度为2的点有n2个，则有n0=n2+1n0=8n2=72.二叉树的性质(3+2)物理意义：叶子数＝2度结点数＋1423167891011121314155性质3

对于任意一棵非空二叉树，如果叶子结点数为n0，度为2的点有n2个，则有n0=n2+12.二叉树的性质(3+2)证明：1、二叉树中全部结点数n＝n0+n1+n2

(叶子数＋1度结点数＋2度结点数)2、二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：n＝B＋1。3、而分支总数

B=n1+2n2

(1度结点必有1个直接后继，2度结点必有2个)三式联立可得：n0+n1+n2=

n1+2n2+1,即n0=n2+13.二叉树的分类满二叉树一棵深度为k且有2k-1个结点的二叉树。

（特点：每层都“充满”了结点）AOBCGEKDJFIHNML深度为4的满二叉树2）完全二叉树如果深度为k、有n个结点的二叉树，按层编号，如果编号为i(1≤i≤

n)的结点与深度为k的顺序编号的满二叉树中编号为i的结点相对应，则称这样的二叉树为完全二叉树A深度为4的完全二叉树BCGEIDHFJ满二叉树和完全二叉树有什么区别？答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。2.二叉树的性质(3+2)对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：性质4：具有n个结点的完全二叉树的深度为

log2n＋1符号

X表示不大于x的最大整数。假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－1<n≤2k-1或2k-1≤n<2k取对数得到：k－1≤log2n<k

因为k是整数。所以有：k＝

log2n

＋1。4231678910

11125

完全二叉树性质5

对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有：（3）如i＝1，则序号为i的结点是根结点，无父结点；如i>1，则序号为i的结点的父结点序号为

i/2；（1）如(2×i)>n，则序号为i的结点无左子结点；如(2×i)≤n，则序号为i的结点的左子结点的序号为2×i；（2）如(2×i＋1)>n，则序号为i的结点无右子结点；如(2×i＋1)≤n，则序号为i的结点的右孩子结点的序号为2×i+1；2.二叉树的性质(3+2)一、顺序存储结构按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF问：顺序存储后能否复原成唯一对应的二叉树形状？答：若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的父结点，其左子结点的下标值必为2i，其右孩子的下标值必为2i＋1（即性质5）。

例如，对应[2]的两个孩子必为[4]和[5]，即B的左孩子必是D，右孩子必为E。T[0]一般不用3.1.4二叉树的存储与实现顺序存储结构的描述:#defineMAXNODE100//二叉树的最大结点数TypedefElemTypeSqBiTree[MAXNODE]

//0号单元存放根结点SqBiTree bt;

//将bt定义为含有MAXNODE个ElemType类型元素的一维数组。讨论：不是完全二叉树怎么办？答：一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9]…[16]ABECD缺点：①浪费空间；②插入、删除不便；二、链式存储结构用二叉链表即可方便表示，每个结点由数据域、左子结点域和右子结点域组成。一般从根结点开始存储。

（相应地，访问树中结点时也只能从根开始）datalchildrchilddataleft_childright_childlchildDatarchildA^DB^C^^E^^F^一般二叉树的二叉链表结构AECBDF二、链式存储结构二叉树链式存储举例：^AB^D^C^^E^优点：①不浪费空间；②插入、删除方便

ABECD二叉树结点数据类型定义：typedefcharElemType;typedefstructbitnode{ElemTypedata;

//数据域

structbitnode

*lchild;//左指针域

structbitnode*rchild;//右指针域}BiTNode,*BiTree;

BiTNode*BT;//定义BT为指向BiTNode类型的指针注：如果需要查询某结点的父结点?如何实现可以再增加一个指向父结点的指针域（直接前驱），将二叉链表变成三叉链表。二、链式存储结构方法二(三叉链表)：每个结点由数据域、左子结点域、右子结点域和父结点域组成。lchildDataParentrchildA^^DB^C^^E^^F^一般二叉树的三叉链表结构AECBDF二、链式存储结构三、二叉树的基本操作3.1.5二叉树的遍历定义：按某条搜索路径遍访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。用途：是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。方法：寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。对每个结点的查看通常都是“先左后右”。遍历规则———二叉树由根、左子树、右子树构成，定义为D、L、RD:processingtheDataofthenode;L:traversingtheLeftsubtreeR:traversingtheRightsubtree注：“先、中、后”的意思是指访问结点的D是先于子树出现还是后于子树出现。

D、L、R的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLD

若限定先左后右，则有三种实现方案：

DLRLDRLRD先(根)序遍历中(根)序遍历后(根)序遍历1遍历二叉树的递归实现例1：先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：ABDE

CFDBEAFCDEB

FCA口诀：DLR—先序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根

ABCDEF二叉树的二叉链表存储用C语言描述如下：typedefstructbinode{ElemTypedata;structbinode*lchild;*rchild;//左右子结点指针}BiTNode;

1遍历二叉树的递归实现BiTNode*BT;//定义BT为指向BiTree类型的指针

1)先序遍历(DLR)

先序遍历的递归过程为：若二叉树为空，遍历结束。否则，

(1)访问根结点；

(2)先序遍历根结点的左子树；

(3)先序遍历根结点的右子树。算法如下：voidPreOrder(BiTNode*bt){//先序遍历二叉树btif(bt!=NULL) {visit(bt->data);//访问结点的数据域

PreOrder(bt->lchild);//先序递归遍历bt的左子树

PreOrder(bt->rchild);//先序递归遍历bt的右子树 }}1遍历二叉树的递归实现算法如下：voidInOrder(BiTNode*bt){//中序遍历二叉树btif(bt!=NULL){

InOrder(bt->lchild);//中序递归遍历bt的左子树visit(bt->data);//访问结点的数据域

InOrder(bt->rchild);//中序递归遍历bt的右子树}}1遍历二叉树的递归实现

2)中序遍历(LDR)

中序遍历的递归过程为：若二叉树为空，遍历结束。否则，

(1)中序遍历根结点的左子树；

(2)访问根结点；

(3)中序遍历根结点的右子树。

算法如下：voidPostOrder(BiTNode*bt){//后序遍历二叉树btif(bt!=NULL){

PostOrder(bt->lchild);//后序递归遍历bt的左子树

PostOrder(bt->rchild);//后序递归遍历bt的右子树visit(bt->data);//访问结点的数据域 }}1遍历二叉树的递归实现3)后序遍历(LRD)

后序遍历的递归过程为：若二叉树为空，遍历结束。否则，

(1)后序遍历根结点的左子树；

(2)后序遍历根结点的右子树。

(3)访问根结点；1遍历二叉树的递归实现问题：怎样从顶部开始逐层输出二叉树结点数据?（即按ABCDEF顺序来遍历，二叉树的层次遍历）先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：ABDECFDBEAFCDEBFCA

ABCDEF采用队列结构。遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：(1)访问该元素所指结点；(2)若该元素所指结点的左、右子结点非空，则将该元素所指结点的左子结点指针和右子结点指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。在层次遍历算法中，二叉树以二叉链表存放，一维数组Queue[MAXNODE]用以实现队列，变量front和rear分别表示当前队首元素和队尾元素在数组中的位置。2二叉树的层次遍历

所谓二叉树的层次遍历，是指从二叉树的第一层(根结点)开始，从上到下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。

ABCDEFvoidLevelOrder(BiTNode*bt)//层次遍历二叉树bt{BiTNode

*Queue[MAXNODE];intfront,rear;if(bt==NULL)return;

front=-1;rear=-1;rear++;Queue[rear]=bt;while(front!=rear){front++;visit(Queue[front]->data);//访问队首结点的数据域

if(Queue[front]->lchild!=NULL)

//将队首结点的左子结点入队列

{rear++;Queue[rear]=Queue[front]->lchild;}

if(Queue[front]->rchild!=NULL)

//将队首结点的右子结点入队列

{rear++;Queue[rear]=Queue[front]->rchild;}}}3二叉树遍历的非递归实现（*）⊕⊕⊕⊕⊕⊕⊕*******△△△△△△△ABDCEFG4二叉树遍历的应用（*）5由遍历序列恢复二叉树1).重构二叉树是遍历二叉树的逆运算

先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：ABDE

CFDBEAFCDEB

FCA问题：如何根据遍历结果重构二叉树？

ABCDEF问题：若已知先序/后序遍历结果和中序遍历结果，

能否“恢复”出二叉树？答：由一棵二叉树的先序/后序序列和中序序列可唯一确定这棵二叉树。

5由遍历序列恢复二叉树1).重构二叉树是遍历二叉树的逆运算

用DLR(先序序列)+LDR(中序序列)

或LRD(后序序列)+LDR(中序序列)重构二叉树2)特点先序遍历序列(DLR)特点：<根>

<左子树上的所有结点><右子树上的所有结点>中序遍历序列(LDR)特点：<左子树上的所有结点>

<根><右子树上的所有结点>3)构造步骤：1)从DLR中找出第一个结点为二叉树的根，然后在LDR中找出根结点，根结点前面的结点序列就是左子树的LDR，根结点后面的结点序列就是右子树的LDR。2)对左子树的DLR和LDR及右子树的DLR和LDR，再执行第一步，直到找到所有的叶子结点。5由遍历序列恢复二叉树中序遍历：BDCEAFHG

后序遍历：DECBHGFA（BDCE）（FHG）ABF（DCE）（HG）CDEGHABBFF例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，请画出这棵二叉树。分析：①由后序遍历特征，根结点必在后序序列尾部（即A）；②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必全部是右子树子孙（即FHG）；③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。二叉树小结树二叉树森林1、定义和性质2、存储结构3、遍历顺序结构链式结构二叉链表三叉链表中序遍历后序遍历先序遍历层次遍历3.1.6树、森林和二叉树的转换树转换成二叉树森林转换成二叉树二叉树转换为森林方法：加线—抹线—旋转

abeidfhgc树转二叉树举例：abeidfhgc兄弟相连长兄为父孩子靠左根结点没有右子结点！转换步骤：step1:在树中所有兄弟结点之间加一连线;step2:只保留结点与最左子结点的连线，删除结点与其它子结点的连线；step3:以树根为轴心，顺时针旋转45度角。加线抹线旋转树所对应的二叉树里，一个结点的左子结点是它在树中的第一个子结点，树中此结点的兄弟结点依次作为前一个兄弟结点的右子结点。讨论1：树如何转为二叉树？

I

A

B

C

DE

F

G

H(b)

A

B

CD

E

G

H

FI(a)ABEFCDGHI(d)ABCDEFGHI(c)例回顾：树的子结点兄弟结点表示法子结点兄弟结点表示法的结点结构图A^B^CD^^E^F^G^^H^IJ^^K^对树中结点用包含该结点的信息域、一个指向该结点子结点的指针域和一个指向其下一个兄弟结点的指针域来表示。子结点兄弟结点表示法的结点结构图结点信息指向子结点的指针指向下一个兄弟结点指针树的示例

讨论2：二叉树怎样还原为树？abeidfhgc要点：把所有右子结点变为兄弟结点！

abeidfhgc方法：(1)各树先各自转为二叉树；(2)把每棵树的根结点用线连起来，后一棵二叉树的根结点作为前一棵二叉树根结点的右子结点。(3)以第一棵树的根结点作为二叉树的根结点，顺时针旋转。讨论3：森林如何转为二叉树？即F={T1,T2,…,Tm}B={root,LB,RB}ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ例：森林转换成二叉树讨论4：二叉树怎样还原为森林？要点：森林F的第一棵树T1的根结点为二叉树BT的根结点Root；T1的子树是二叉树BT的左子树构成。森林F中其余的树组成的森林{T2,…,Tn}是由二叉树BT的右子树转换而成的森林。步骤若某结点是其父结点的左子结点，则把该结点的右子结点、右子结点的右子结点都与该结点的父结点用线连起来。删掉原二叉树中所有父结点与右子结点的连线。旋转ADCBEFHIGJADCBEFHIGJADCBEFHIGJADCBEFHIGJ例：二叉树还原为森林步骤1：若某结点是其父结点的左子结点，…步骤2：删掉原二叉树中所有父结点与右子结点的连线。步骤3：旋转二叉树小结树二叉树森林1、定义和性质2、存储结构3、遍历顺序结构链式结构二叉链表三叉链表中序遍历后序遍历先序遍历层次遍历作业：习题3：树题：3.3二叉树题：3.6，3.7(1)(2)，3.8

线性结构（线性表、栈、队、串、数组）数据结构逻辑结构物理（存储）结构数据运算非线性结构树结构图结构顺序结构链式结构插入运算删除运算修改运算查找运算排序运算数据结构课程的内容多对多（m:n)3.2图

3.2.1图的定义和基本概念

3.2.2图的存储结构

3.2.3图的遍历3.2.1图的定义和基本概念1.图的基本概念图：记为G＝(V,E)

其中：V

是G的顶点集合，是有穷非空集；

E

是G中边的集合，是V中两个顶点之间关系的集合。V=vertexE=edge

V＝{vi|vi∈data_object}E＝{(vi,vj)|vi,vj∈V∧P(vi,vj)}其中，P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(vi,vj)表示一条边。在该图中：集合V＝集合E＝v1v2v3v4v53.2.1图的定义和基本概念{v1,v2,v3,v4,v5}；{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}3.2.1图的定义和基本概念（1）无向图: 在一个图中，如果任意两个顶点构成的偶对（vi,vj）∈E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。（2）有向图: 在一个图中，如果任意两个顶点构成的偶对（vi,vj）∈E是有序的，即顶点之间的连线是有方向的，则称该图为有向图。2.图的术语BACDv1v2v3v4v5无向图有向图3.2.1图的定义和基本概念(3)顶点、边、弧、弧头、弧尾。BACD数据元素vi称为顶点(vertex)；P(vi,vj)表示在顶点vi和顶点vj之间有一条直接连线。如果是在无向图中，则称这条连线为边；用顶点的无序偶对（vi,vj）来表示。如果是在有向图中，一般称这条连线为弧；用顶点的有序偶对<vi,vj>来表示。有序偶对的第一个结点vi被称为始点（或弧尾），在图中就是不带箭头的一端；有序偶对的第二个结点vj被称为终点（或弧头），在图中就是带箭头的一端。在有向图中，<V1，V3>表示从V1到V3的一条弧。

V1为弧尾或始点，V3为弧头或终点。在无向图中，(V1，V3)表示V1和V3之间的一条边。3.2.1图的定义和基本概念V1V3V2V4有向图V1V3V2V4无向图3.2.1图的定义和基本概念完全图，图G（有n个顶点）任意两个顶点都有一条边/弧相连接。有向完全图：至少有

条弧的有向图若是完全有向图，则顶点1必与所有其他顶点各有2条连线，即有2(n-1)条边，顶点2有2(n-2)条边，…，顶点n-1有2条边,顶点n有0条边.总边数＝2(n-1＋n-2＋…＋1＋0)=2(n-1+0)n/2=n(n-1)无向完全图：至少有

条边的无向图若是完全无向图，则顶点1必与所有其他顶点各有1条连线，即有n-1条边，顶点2有n-2条边，…，顶点n-1有1条边,顶点n有0条边。总边数＝n-1＋n-2＋…＋1＋0=（n-1+0)n/2=n(n-1)/2稀疏图（边数<nlogn）和稠密图n×(n－1)n×(n－1)/2V1V2V3V4有向图V1V2V3V4无向图3.2.1图的定义和基本概念邻接点对于无向图G＝（V，E），如果边（v1，v2）

E，则称顶点v1，v2互为邻接点。边（v1,v2）依附于顶点v1和v2，边（v1,v2）和顶点v1与v2相关联。对于有向图G＝（V，E），若弧<v1，v2>

E，则称顶点v1邻接到顶点v2，顶点v2邻接自顶点v1。例：判断下列4种图形各属什么类型？无向无向图(树)有向图有向n(n-1)/2条边n(n-1)条边（a）G1的顶点集合为V(G1)={0,1,2,3}------无向图边集合为E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}完全图完全图（b）G3的顶点集合为V(G3)={0,1,2}------有向图

边集合为E(G3)={<0,1>,<1,0>,<1,2>}注意点：1）对于有向图<Vi，Vj>和<Vj，Vi>是两条不同的边。2）对于无向图（Vi，Vj）和（Vj，Vi）是两条相同的边。3.2.1图的定义和基本概念图的基本概念图：记为G＝(V,E)

其中：V

是G的顶点集合，是有穷非空集；

E

是G中边的集合，是V中两个顶点之间关系的集合。

V＝{vi|vi∈data_object}E＝{(vi,vj)|vi,vj∈V∧P(vi,vj)}其中，P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(vi,vj)表示一条边。问：当E(G)为空时，图G＝(V,E)存在否？答：还存在！但此时图G只有顶点而没有边。3.2.1图的定义和基本概念子图：设有两个图G＝（V，E）和图G’＝（V’，E’），若V’

V且E’

E，则称G’为G的子图ABCDABCDABDG的子图G的子图不是G的子图图G与图的边或弧相关的数据信息。带权的图。依附于该顶点的边数或弧数。以该顶点为始点(尾)的弧数。以该顶点为终点(头)的弧数。BACD631542对于有向图，TD(V)=OD(V)＋ID(V)BACD3.2.1图的定义和基本概念无论是有向图，还是无向图，顶点数n、边数e和度数TD(vi)之间的关系如下：权:网（或赋权图）：顶点的度（TD(V)）：出度(OD(V))(仅对有向图):入度(ID(V))(仅对有向图):简单路径：路径上各顶点v1,v2,...,vm

均不互相重复。回路：若路径上第一个顶点v1

与最后一个顶点vm

重合，则称这样的路径为回路或环。路径：在图G＝(V,E)中,若从顶点

vi出发,沿一些边经过一些顶点

vp1,vp2,…,vpm，到达顶点vj。则称顶点序列

(vi

vp1vp2...vpm

vj)

为从顶点vi到顶点

vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应当是属于E的边。路径长度：路径上边的条数。3.2.1图的定义和基本概念简单回路：除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路。例：连通图：在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。强连通图：在有向图中,

若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。3.2.1图的定义和基本概念V0V4V3V1V2连通图V0V4V3V1非连通图V2V0V4V3V1强连通图V0V4V3V1非强连通图连通分量：无向图的极大连通子图称为连通分量。极大连通子图：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。强连通分量：有向图的极大连通子图称为强连通分量。3.2.1图的定义和基本概念连通分量1

连通分量2生成树：连通图G的生成树，是G的包含其全部n个顶点的一个极小连通子图。它必定包含且仅包含G的(n-1)条边。生成森林：非连通图中，每个连通分量的生成树构成了非连通图的生成森林。3、图的基本操作 3.2.1图的定义和基本概念V0V4V3V1V2连通图G1V0V4V3V1V2连通图G1的生成树V0V4V3V1V2=V0V4V3V1非连通图V23.2.2图的存储结构图的特点：非线性结构（m:n）邻接表邻接多重表十字链表设计为邻接矩阵链式存储结构：顺序存储结构：无简单形式！（多个顶点，无序可言）但可用数组描述元素间关系。可用多重链表重点：邻接矩阵(数组)表示法邻接表(链式)表示法存储方式：用一维数组存储图中顶点的信息：顶点表V(G)用邻接矩阵表示图中各顶点间的邻接关系（边或弧）：E(G)设图G=(V,E)有n

个顶点，则无向图的邻接矩阵是一个二维数组A[n][n]，定义为：一、邻接矩阵（数组）表示法v1v2v3v5v4v4A例1：邻接矩阵：A

=（

v1v2

v3v4v5

）v1v2v3v4v500

0

0000

0000

00000000000000分析1：无向图的邻接矩阵是对称的；分析2：顶点i

的度＝第i

行(列)中1的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。分析3：矩阵中1的个数的一半为图中边的个数。01

0

1010

1010

101110101011

1001

0

1010

1

010

1

0111

010101110顶点表：v1v2v3v4v5无论是有向图，还是无向图，顶点数n、边数e和度数TD(vi)之间的关系如下：例2：有向图的邻接矩阵分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点的出度=第i行元素之和，OD(Vi)=

顶点的入度=第i列元素之和。ID(Vi)=

顶点的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD(Vi)+ID(Vi)分析3：

矩阵中1的个数为图中弧的数目v1v2v3v4A注：在有向图的邻接矩阵中，第i行含义：第i列含义：邻接矩阵：A=(

v1v2

v3v4)v1v2v3v400

0

000

000

0000000顶点表：01

1

000

000

0

01

1

00001

1

000

000

0

01

1000

v1v2

v3v4以结点Vi为始点(尾)的弧(即出度边）；以结点Vi为终点(头)的弧(即入度边）。有向网

A

B

C

D

A

∞3∞2

B

∞

∞54

C

∞

∞

∞6

D1∞

∞

∞BACD632154例3：网图的邻接矩阵

îíìÎ==

<Vi,Vj>

[j][i]

]][[

否则如果0或∞,wij,AAEji图的邻接矩阵数据类型描述#defineMaxVertexNum100//图中顶点数

typedefintVertexType;typedefintEdgeTypetypedefstruct

{

VertexTypeV[MaxVertexNum];//顶点表

EdgeTypeedges[MaxVertexNum][MaxVertexNum]；//邻接矩阵

intn,e; //顶点数和边数}MGraph; //邻接矩阵存储的图类型无向图的邻接矩阵的建立voidCreateMGraph(MGraph*G){ inti,j,k; for(k=1;k<=G->n;k++) Scanf(“%d”,&G->V[k]);//输入顶点信息

for(i=1;i<=G->n;i++) for(j=1;j<=G->n;j++) G->edges[i][j]=0;//邻接矩阵初始化 for(k=1;k<=G->e;k++) { Scanf(“%d”,&i); Scanf(“%d”,&j); G->edges[i][j]=1;//输入顶点i到j的边 G->edges[j][i]=1;//无向图 }}v1v2v3v5v4v4邻接矩阵的插入与删除邻接矩阵的插入：无向图G->edges[i][j]=G->edges[j][i]=1有向图G->edges[i][j]=1邻接矩阵的删除：无向图G->edges[i][j]=G->edges[j][i]=0有向图G->edges[i][j]=0容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。

邻接矩阵法优点：邻接矩阵法缺点：邻接矩阵法结论：n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。

对稀疏图而言尤其浪费空间，此时可以采用邻接表存储法。5432154321顶点表v5v4v3v2v1图的邻接表表示法：顶点表+邻接表对图G中的每个顶点vi，将所有邻接于vi的顶点（即邻接矩阵中同一行的非0元素）链接在一个单链表（边表）中。称为vi的邻接表。所有顶点的邻接表的表头（头指针）放到数组中（顺序表），构成图的顶点表。顺序存储与链式存储相结合的方法。二、邻接表（链式）表示法头指针邻结点^24^2453^153^145^245^234^234^253^153^1邻接表例1：无向图的邻接表无向图的邻接表性质：1）第i链表中结点的数目为顶点vi的度（头结点不算）2）所有顶点邻接表中结点数目总和的一半为图中的边数3）占用存储单元的数目为n＋2e个v1v2v3v5v4v4头指针邻结点12345^2445^253^1注：邻接表不唯一，因各个边结点的链入顺序是任意的。v1v2v3v4v534^253^1顶点表邻接表有向图的邻接表性质：1）第i个链表中结点的数目为顶点i的出度2）第i个顶点的入度为该顶点在所有链表中出现的次数3）占用存储单元的数目为n＋ev1v2v3v4V4V3^V2V13^4^1^2邻接表^4^1^3^1V4V3V2V1逆邻接表例2：有向图的邻接表例3：已知某网的邻接（出边）表，请画出该网络。当邻接表的存储结构形成后，图便唯一确定！邻接表结构的数据类型描述#defineMaxVexNum100typedefintVertexType;typedefstructnode{//邻接表结点

VertexTypeadjvex;// WeightTypewdata;//边上信息 structnode*next;}EdgeNode;typedefstructvnode{//顶点表结点

VertexTypevertex;

EdgeNode*firstedge;//邻接表头指针}VertexNode;typedefstruct{ VertexNodeadjlist[MaxVexNum];// intn,e; //顶点数和边数}ALGraph //以邻接表方式存储的图类型顶点表结点：VertexNodefirstedgevextex数据域：存储顶点vi的名链域：指向vi的邻接表中第一个结点邻接表结点：EdgeNodenextinfoadjvex邻接点域：指示与顶点vi邻接的点在图中的位置链域：指向vi下一个边或弧的结点数据域：与边有关信息（如权值）建立有向图的邻接表voidCreateALGraph(ALGraph*G){ inti,j,k;

EdgeNode*s; //邻接表结点 scanf(“%d,%d”,&G->n,&G->e); for(i=1;i<=G->n;i++) //建立n个顶点的顶点表 { scanf(“\n%c”,&(G->adjlist[i].vertex)) //顶点信息

G->adjlist[i].firstedge=NULL; //顶点的边表头指针设为空 } for(k=1;k<=G->e;k++) //建立边表 { scanf(“\n%d,%d”,&i,&j); //读入<vi,vj>顶点对应序号

s=(EdgeNode*)malloc(sizeof(EdgeNode));

s->adjvex=j; //邻接点序号j

//将新邻接表结点s插入到顶点vi的邻接表的头部 s->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=s; }}邻接表结点：EdgeNodenextinfoadjvex邻接点域：指示与顶点vi邻接的点在图中的位置链域：指向vi下一个边或弧的结点数据域：与边有关信息（如权值）顶点表结点：VertexNodefirstedgevextex数据域：存储顶点vi的名链域：指向vi的邻接表中第一个结点邻接表的缺点：邻接表的优点：空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两顶点对应的单链表，没有邻接矩阵方便。邻接表结论讨论：邻接表与邻接矩阵有什么异同之处？联系： 邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于邻接矩阵一行中非零元素的个数。2.区别：①对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号有关）。②对于无向图，邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+2e)。v1v2v3v5v4v4A图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。一、深度优先搜索二、广度优先搜索

3.2.3图的遍历遍历定义：遍历实质：图的特点：解决思路：图常用的遍历：怎样避免重复访问？找每个顶点的邻接点的过程。 可设置一个辅助数组

visited[n]，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i

被访问，就立即改visited[i]为1，防止它被多次访问。从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，这样的过程称为图的遍历，它是图的基本运算。一、深度优先搜索(DFS)基本思想—仿（二叉）树的先序遍历过程。以图中某一结点作为当前结点，进行：1)处理或输出当前结点，并记录当前结点的查访标志。2)若当前结点有邻接点，则取第一个邻接点。若该邻接点未被查访过，则以该邻接点为当前结点用深度优先搜索法进行查访。如下例所示：Depth_FirstSearch深度优先搜索(DFS)仿树的先序遍历过程：v1v1v2v3v8v7v6v4v5DFS结果例1：→→→→→→→v2v4v8v5v3v6v7例2：v2→v1→v3→v5→DFS结果v4→v6起点起点遍历步骤首先设置一个辅助数组visited[i]，用来标记每个被访问过的顶点i，它的初态为0，访问后置“1”标识。1)首先访问顶点i，并标识visited[i]=1,表示访问过。2）搜索与顶点i有边相连的下一个顶点j；①若j未被访问过就标识visited[j]=1，然后从j开始重复此过程；②若j已被访问过，再看与i有边相连的其它顶点。3）若图中尚有顶点未被访问，则另选一个未被访问的顶点作为起始顶点，重复上述过程，直到图中所有的顶点都被访问过。

记

visited[i]=0图中第i个顶点未被访问过1图中第i个顶点被访问过深度优先搜索（遍历）操作：起点DFS:213546讨论1：邻接矩阵如何实现DFS？123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111DFS结果邻接矩阵A辅助数组visited[n]起点v2→v1→v3→v5→v4→v6——开辅助数组

visited[n]！例：123456101110021000103100010410000150110006000100邻接矩阵的DFS算法如何编程？DFS1(MGraph*g,inti)

{intj；printf(“%d”,g->V[i]);visited[i]=1;for(j=1;j<=n;j++)if((g->edges[i][j]==1)&&(!visited[j]))

DFS1(g,j);}——可以用递归算法！//g邻接矩阵，i为起始顶点(编号）//访问（例如打印）顶点v

//DFS1edges[i,j]＝1有邻接点visited[j]=0未访问过//访问后立即修改辅助数组标志//从v所在行从头搜索邻接点起点DFS:213546讨论2：在图的邻接表中如何进行DFS？v0→v1→v2→v3DFS结果00000123辅助数组visited[n]1000110011101111例：—照样借用visited[n]！起点0123

邻接表的DFS算法如何编程？DFS2(ALGraph*G，inti){EdgeNode

*p;printf(“%d”,G->adjlist[i]->vextex);visited[i]=1;p=G->adjlist[i].firstedge;while(p!=null){if(visited[p->adjvex]==0) DFS2(G,p->adjvex);p=p->next;}}//访问后立即修改辅助数组标志//若指针为空，则结束本次遍历//取Vi链表的头指针——仍可用递归算法//递归调用//指向下一邻接点邻接表结点：EdgeNodenextinfoadjvex邻接点域：指示与顶点vi邻接的点在图中的位置链域：指向vi下一个边或弧的结点数据域：与边有关信息（如权值）顶点表结点：VertexNodefirstedgevextex数据域：存储顶点vi的名链域：指向vi的邻接表中第一个结点typedefstruct{VertexNodeadjlist[MaxVexNum];intn,e;}ALGraph深度优