当前位置：文档之家 › 数据结构 北邮 徐雅静 第六章 课件

数据结构 北邮 徐雅静 第六章 课件

  • 格式：ppt
  • 大小：1.29 MB
  • 文档页数：117

下载文档原格式

  / 117

合集下载

第6章B--数据结构课件(吴伟民-严蔚敏编著)

第6章B--数据结构课件(吴伟民-严蔚敏编著)
6
4. 二叉树的存储结构
一,顺序存储结构 按二叉树的结点" 按二叉树的结点 " 自上而 B 从左至右" 编号, 下 , 从左至右 " 编号 , 用 一组连续的存储单元存储. 一组连续的存储单元存储 . D E
H I A
T[0]一 T[0]一 般不用
C F G
问:顺序存储后能否复原成唯一对应的二叉树形状? 顺序存储后能否复原成唯一对应的二叉树形状? 若是完全/满二叉树则可以做到唯一复原. 答:若是完全/满二叉树则可以做到唯一复原. 而且有规律:下标值为i的双亲, 而且有规律:下标值为i的双亲,其左孩子的下标值必为 性质5 2i,其右孩子的下标值必为2i 2i+ 2i,其右孩子的下标值必为2i+1(即性质5) 例如,对应[2]的两个孩子必为[4] [5],即 [2]的两个孩子必为[4]和 例如,对应[2]的两个孩子必为[4]和[5],即B的左孩子必 是D,右孩子必为E. D,右孩子必为E 右孩子必为
性质5: 对完全二叉树,若从上至下,从左至右编号, 性质5: 对完全二叉树,若从上至下,从左至右编号,
则编号为i 的结点,其左孩子编号必为2i, 则编号为 的结点,其左孩子编号必为 ,其右孩子编号 时为根,除外). 为2i+1;其双亲的编号必为 (i=1 时为根,除外). ;其双亲的编号必为i/2(
1. 2. 3.
二叉树的定义 二叉树的性质 二叉树的存储结构 二叉树的运算见下一节) (二叉树的运算见下一节)
2
2. 二叉树的性质
(3+2)
性质1: 在二叉树的第i层上至多有2 个结点(i>0). 性质1: 在二叉树的第i层上至多有2i-1个结点(i>0). 性质2: 深度为k的二叉树至多有2 个结点(k>0). 性质2: 深度为k的二叉树至多有2k-1个结点(k>0). 性质3: 对于任何一棵二叉树, 度的结点数有n 性质3: 对于任何一棵二叉树,若2度的结点数有n2个, 则叶子数( 必定为n 则叶子数(n0)必定为n2+1 (即n0=n2+1) )

数据结构严蔚敏第6章

数据结构严蔚敏第6章

整理ppt
2
线性表
A．线性结构 栈
队
数
1．数据的逻辑结构
据 结
树形结构 B．非线性结构
构
的
图形结构
三
个 主
2、数据的存储结构 A 顺序存储
要 问
B 链式存储
题
3、数据的运算：检索、排序、插入、删除、修改等。
整理ppt
3
树形结构
全校学生档案管理的组织方式
整理ppt
4
A
D
B
C
E F GH
A
B
C
D
E
11
插入类：
InitTree(&T) // 初始化置空树
CreateTree(&T, definition) // 按定义构造树
Assign(T, cur_e, value) // 给当前结点赋值
InsertChild(&T, &p, i, c)
// 将以c为根的树插入为结点p的第i棵子树
整理ppt
证明：
设 二叉树上结点总数 n = n0 + n1 + n2
又 二叉树上分支总数 b = n1+2n2
而 b = n-1 = n0 + n1 + n2 - 1
由此， n0 = n2 + 1 。整理ppt
30
两类特殊的二叉树： 1
满二叉树：指的是
2
3
深度为k且含有2k-1个 4 5 6 7
结点的二叉树。
} TriTNode, *TriTree;
结点结构: parent lchild data rchild
整理ppt
41

数据结构.ppt

数据结构.ppt

....
2020/6/18
(*L).data[数(*据L结)构.last] an
21
2.2 线性表的顺序存储
二、 顺序表上的基本运算（实现） SETNULL（L）： (*L).last = -1
LENGTH(L):
(*L).last+1
GET(L,i):
(*L).data[i-1]
LOCATE(L,x)
2020/6/18
数据结构
6
存储结构： •顺序存储方法：数据元素在内存中按序连续存储，
结点间的逻辑关系由存储单元的邻接关系来体现 •链接存储方法：用指针指出其直接后继结点的存储位置，
结点间的逻辑关系由存储单元的邻接关系来体现 •索引存储方法：数据元素连续存放，再设一个索引表（有 序），索引表由索引项组成，每个索引项由关键字和地址构成
2020/6/18
} 数据结构
30
2.3.2 单链表上的基本运算（实现）
尾插法建表：将新结点插入到当前链表的表尾（需引入r）
Head a
r
b
c^
sr d ^
•不带头结点的尾插法：插入时，第一个结点的处理与其 它结点的处理有区别。
结束时，空表和非空表的处理有区别。
•带头结点的尾插法：1）链表第一个位置上的操作与其
线性表的常见基本运算包括：
（1）置空表SETNULL(L) （2）建表CREATLIST(L) （3）求表长LENGTH(L) （4）取结点GET(L,i) （5）定位LOCATE(L,x) （6）插入INSERT(L,x,i) （7）删除DELETE(L,i)
复杂的运算可以由这些基本运算组合来实现
=（语句频度×语句执行一次所需时间） =语句频度 •算法的时间复杂度：就是算法的时间耗费T(n)

数据结构说课ppt课件

数据结构说课ppt课件
（1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数
基本概念与术语
据结构。
数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。
依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种：
1.集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。
单链表
链表操作算法：初始化、插入、输出、删除、遍历
8. 在一个单链表中删除q所指结点时，应执行如下操作：
q=p->next;
p->next=( p->next->next );
free(q);//这种题目靠一根指针是没有办法完成的，必须要借助第二根指针。
9. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行：
(2) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元
问答题
素，这时，应采用哪种存储表示？为什么？
应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。
03
栈和队列
数据结构说课ppt课件
演讲人
数据结构概述
01
线性表
02
栈和队列
03
目录
01
数据结构概述
基本概念与术语
2.数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。
（补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。）
在右侧编辑区输入内容
顺序表的存储效率高，存取速度快。此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。

【课件】数据结构第6章图ppt

【课件】数据结构第6章图ppt

6.1 图的逻辑结构
V1 V3
V4 V1
V3
V2 若顶点vi和vj之间的边没有方向，则 称这条边为无向边，表示为(vi,vj)。 如果图的任意两个顶点之间的边都
V5 是无向边，则称该图为无向图。
V2 若从顶点vi到vj的边有方向，则称这 条边为有向边，表示为<vi,vj>。 如果图的任意两个顶点之间的边都
第6章 图
本章的主要内容是:
图的逻辑结构 图的存储结构及实现 图的连通性 最小生成树 最短路径 AOV网与拓扑排序 AOE网与关键路径
2019/10/26
第6章 图
图是一种非常复杂的非线性结构，并且具有极强的表达能力， 现实世界中的许多问题都可以抽象为图结构。本章是本课程 的难点和重点。通过本章的学习，要求学生：
i =1
V1
V2
V3
V4
V5
在具有n个顶点、e条边的无向图G中，各顶点 的度之和与边数之和的关系？
6.1 图的逻辑结构
图的基本术语
V1
V2
n
n
ID(vi ) = OD(vi ) = e
i=1
i=1
V3
V4
在具有n个顶点、e条边的有向图G中，各顶点 的入度之和与各顶点的出度之和的关系？与边 数之和的关系？
A
B
C
D
E
F
线性结构
A
V1
V2
B
C
V3
D
EF
V4
V5
树结构
图结构
在线性结构中，元素之间的关系为前驱和后继； 在树结构中，结点之间的关系为双亲和孩子； 在图结构中，顶点之间的关系为邻接。
6.1 图的逻辑结构

数据结构课件第六章

数据结构课件第六章

6
广义表表示法
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) )
根作为由子树森林组成的表的名字写在表的左边
data link 1 link 2 ... 麻烦问题：应当开设多少个链域? link n
7
左孩子－右兄弟表示法
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) 数据 右兄弟 左孩子
数据结构课程的内容
1
第6章 树和二叉树（ Tree & Binary Tree ）
特点：非线性结构，一个直接前驱，但可能有多个 直接后继（1：n）
6.1 6.2 6.3 6.4 6.5
树的基本概念 二叉树 遍历二叉树和线索二叉树 树和森林 赫夫曼树及其应用
2
6.1
1.
2 3. 4. 5.
树的基本概念
24
3. 二叉树的存储结构
一、顺序存储结构 按二叉树的结点“自上而 B 下、从左至右”编号，用 一组连续的存储单元存储。 D E
H I A
T[0]一 般不用
C F G
问：顺序存储后能否复原成唯一对应的二叉树形状？ 答：若是完全/满二叉树则可以做到唯一复原。 而且有规律：下标值为i的双亲，其左孩子的下标值必为 2i，其右孩子的下标值必为2i＋1（即性质5） 例如，对应[2]的两个孩子必为[4]和[5],即B的左孩子必 是D,右孩子必为E。
（除根结点外，每个结点必有一个直接前趋，即一个分支）
而 总分支数B= n1+2n2 (1度结点必有1个直接后继，2度结点必有2个)
三式联立可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1

北京邮电大学-数据结构讲义PPT

关系的映象 两种根本方法及其组合使用。 顺序映象：以相对的存储位置表示关系 链式映象：以附加信息(指针)表示关系 注意：数据的逻辑构造和存储构造的关系 可以用数组等线形存储的方式存储逻辑上的树形构造 也可以用树状的复杂的存储构造来存储逻辑上的集合关系以到达提高
检索速度的目的
数据的逻辑结构与存储结构
正确性〔最重要的标准〕 算法应满足具体问题的需求 对于典型的、苛刻而带有刁难性的一组有效输入得到
正确的结果 强健性 算法应具有容错处理。当输入非法数据时，算法应对
其作出反响，而不是产生莫名其妙或随机的输出结果 可读性 算法应该好读。以有利于阅读者对程序的理解和维护 高效性：时间复杂度 算法执行占用的CPU时间，随问题规模n的变化函数 高效性：空间复杂度 算法执行占用的内存总量，随问题规模n的变化函数
a1 a2 a3 … ai … an
根本术语
数据 被计算机加工处理的对象。 数据元素〔记录、表目〕 数据的根本单位，
是数据集合中的一个有意义的个体。 数据项 一个数据元素可由假设干个数据项组成。
பைடு நூலகம்
学 号姓 名班 号性别出生日期入学成绩
原子项
年月日
组合项
根本术语2
数据对象 是性质一样的数据元素的集合，是 数据的一个子集。
学号 姓名 班号 性别 出生日期 数据入元学素 成绩
增长率一样
时间复杂度曲线
常见的时间复杂度：
O(1), O(log2n), O(n), O(n log2n), O(n2), O(n3), O(2n)
O(1)<O(log2n)＜O(n)＜ O(nlog2n)＜(n2)＜O(n3) ＜＜O(2n)
空间复杂度
算法所需存储空间的度量

数据结构课件PPT


二分查找
二分查找法
将有序数据集分成两个部分，每次取中间位置的值与目标值进行比较，根据比 较结果缩小查找范围，直到找到目标值或确定目标值不存在。
优缺点
查找速度快，但要求数据集必须是有序的。
哈希查找
哈希表
利用哈希函数将数据元素映射到内存中的地址，实现数据的 快速查找。
优缺点
查找速度快，但需要解决哈希冲突问题，并可能存在哈希表 过大或过小的问题。
。
数据结构的基本概念
数据结构的基本概念包括：数据、数据 元素、数据类型、数据结构等。
数据结构是指数据的组织形式，即数据 元素之间的相互关系。
数据类型是指一组具有相同特征和操作 的数据对象（如整数、实数、字符串等 ）。
数据是信息的载体，是描述客观事物的 符号记录。
数据元素是数据的基本单位，一个数据 元素可以由若干个数据项组成。
稳定排序
归并排序是一种稳定的排序算法，即相等的元素在排序后 保持其原有的顺序。
非递归算法
归并排序是一种非递归算法，即通过迭代方式实现算法过 程。
需要额外的空间
归并排序需要额外的空间来存储中间结果和临时变量。
查找算法
06
线性查找
顺序查找
逐一比对数据元素，直到找到目 标值或遍历完整个数据集。
优缺点
简单易懂，但效率较低，适用于 数据量较小的情况。
拓扑排序的应用
拓扑排序是一种对有向无环图进行排序的算法， 它按照拓扑关系将图的节点排列成一个线性序列 。
有向无环图是一种没有环路的有向图，拓扑排序 可以有效地解决有向无环图的排序问题。
拓扑排序的应用非常广泛，包括确定任务的执行 顺序、确定事件的发生顺序等。
拓扑排序的基本思路是从有向无环图的任一节点 开始，删除该节点，并记录下该节点的所有后继 节点的编号，然后按编号从小到大的顺序重复以 上步骤。

数据结构.ppt

一、算法定义
算法是对特定问题求解步骤的一种描述，
由有限的指令序列构成，其中每一条指令表示 一个或多个操作。
2020/5/12
数据结构
10
二、算法应具有的五个特性：
（1）输入 一个算法有零个或多个的输入，它们是算法 开始前给出的最初量
（2）输出 一个算法至少有一个输出，它们是同输入 有某种关系的量
（3）有穷性 每一条指令的执行次数必须是有限的 （4）确定性 每一条指令必须有确切的含义，无二义性 （5）可行性 每条指令的执行时间都是有限的。
while (ch!=‘$’) {s=malloc(sizeof(linklist));
s->data=ch;
s->next=head;
head=s;
ch=getchar( );
}
return head;
}
2020/5/12
数据结构
28
2.3.2 单链表上的基本运算（实现）
尾插法建表：将新结点插入到当前链表的表尾（需引入r）
申请一个结点 p=(linklist *)malloc(sizeof(linklist)); 释放一个结点 free(p);
2020/5/12
数据结构
26
2.3.2 单链表上的基本运算（实现）
1.建立单链表
方法:从一个空表开始,重复读入数据,生成新结点,将读入数 据存放在新结点的数据域,然后将新结点插入当前链表 中,直到结束。
集合上的一组操作。
4、数据结构
原子数据类型(atomic data type) 结构数据类型(aggregate data type)
• 数据的逻辑结构
• 数据的存储结构
• 数据的运算：既对数据施加的操作

数据结构课件文字版

数据结构就是研究数据之间的相互关系（结构），并相应于这种关系定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
概括地说：
数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。
解决问题的步骤：通过对问题进行详细地分析,抽象出相应的数学模型,确定使用的数据结构；在此基础上设计对此数据结构实施各种操作的算法；选用某种语言将算法转换成程序；调试并运行这些程序。
{设线性表为(a1，a2, . . .，ai，. . .，an),称i为ai在线性表中的位序。}
基本操作：
结构初始化操作
结构销毁操作
引用型操作
加工型操作
} ADT List
例2-1已知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。
1.2基本概念和术语
一、基本概念二、数据类型三、结构的定义四、数据结构的定义五、数据结构的分类六、抽象数据类型
一.基本概念
数据(Data)：是对信息的一种符号表示。所有能输入到计算机中并被计算机程序处理的符号的总称。
是计算机操作的对象的总称。
例：编译程序处理的数据：
数据元素(Data Element):是数据（集合）中的一个“个体”,是组成数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
ADT有两个重要特征:
数据抽象
数据封装
1.4算法和算法分析一、算法及其描述二、算法设计的要求三、算法效率的度量四、算法的存储空间的需求
一、算法及其描述
算法：是对特定问题求解步骤的一种描述。算法是指令的有限序列，其中每一条指令表示一个或多个操作。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

-34-
v1
v5
v4
2．建立图
v2
v3
有向图G
0 v1 1 v2 ∧ 2 v3 3 v4 4 v5
1
3 ∧
vertex[5]= v0 v1 v2 v3 v4
1 4 ∧ 0 ∧
3
4 ∧
G1=
0 0 0 0 1
1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 邻接矩阵
0 0 1 1 0
-35-
数据结构
第6章
图
北京邮电大学信通院 网络搜索中心
1
主要内容
6.1 6.2 6.3 6.4 图的逻辑结构 图的存储结构及实现 最小生成树 最短路经
-2-
6.1 图的逻辑结构
3
6.1 图的逻辑结构
图的定义 G = (V, E) G表示一个图，V代表图中顶点的集合，E 代表顶点之间的关系。 （v1,v2）代表v1和v2之间有一条边 <v1,v2> 代表v1到v2之间有一条弧
-28-
图的存储——邻接表
29
1．图的存储结构
邻接表(顺序结构和链式存储的组合)
0 1 2 3 4 v1 v2 ∧ 1 3 ∧
v1
v4
v5
v3 v4 v5
1 4 ∧ 0 ∧
3
4 ∧
v2
v3 有向图G
-30-
1.邻接表结点的C++描述
邻接表结点的C++描述
struct VertexNode{ char Vertex; //顶点 ArcNode *firstarc; //第一条弧 }; struct ArcNode{ int adjvex; //邻接顶点 Arcnode * next; //下一条弧 };
弧的结点 headvex tailvex tlink hlink
-3939
《数据结构与STL》
3. 十字链表
v1 v2
0
v3
v1
0 1
∧
2 0∧∧
1
2
v2
v3
2 1∧
0 2∧∧
-40-
4.邻接多重表(无向图)
0 v1 1 v2 0 1 1 2 0 ∧ 3∧ 1 ∧ 4
2 v3
3 v4
2 ∧ 4 3 4∧
v3 G2
v5
-5-
2.图的基本术语
顶点：数据元素通常称为顶点V 弧：顶点之间的有向连线，G2 边：顶点之间的无向连线，G1 有向图：G2 无向图：G1
-6-
2.图的基本术语
简单图
不存在顶点到其自身的边，且同一条边不 重复。 G1和G2都不是简单图。
v1
v3 v4 G1
v2
v1
v2
v5
4 v5
-41-
4.邻接多重表
邻接多重表头结点的C++描述
struct VertexNode{ char Vertex; //顶点 ArcNode *firstedge; //第一条邻接边 };
头结点 vertex firstedge
-42-
4.邻接多重表
邻接多重表结点的C++描述 struct ArcNode{ int ivex; int jvex; //边的两个顶点 Arcnode* ilink; //下一条依附 i 的边 Arcnode* jlink; //下一条依附 j 的边 };
20
1．图的存储结构
vertex[4]= v0 v1 v2 v3 0 arc[4][4]= 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0
邻接矩阵
-21-
1．图的存储结构
1、邻接矩阵 (顺序存储)
使用二维数组表示顶点之间相邻关系的矩阵。 设G=(V,E)是具有n个顶点的图 ，顶点序号依次 为0，1，…，n-1，则邻接矩阵：
ivex 弧的结点 ilink jvex jlink
-4343
《数据结构与STL》
5.边集数组
v0 9 v1 5 3 v3 8 v4 4 6 vertex[5]= v0 v1 v2 v3 v4
v2
7
0
1
2
3
4
5
6
起点 0 终点 1 权值 9
0
1
1
2
3
4
2
6
3
5
2
4
4
7
0
3
3
8
-44-
图的基本操作——图的遍历
//建图的构造函数
v1
v5
template <class T> v4 class ALGraph<T>:: MGraph(T a[], int n, int e) v2 { v3 vNum = n; arcNum = e; for(int k=0;k<n;k++) 有向图G { （1）//初始化顶点和弧 adjlist[i].vertex = a[i]; //初始化顶点 adjlist[i].firstarc = NULL; //初始化弧 } for(k=0;k< e;k++) （2）//输入弧所依附的顶点信息 { cin>>i>>j; ArcNode *s =new ArcNode; s->adjvex = j; s->nextarc = adjlist[i].firstarc ; //头插法 adjlist[i].firstarc = s; } -36}

-14-
2.图的基本术语
强连通图：在有向图中，任何一对顶点都存在路 径，则称其为强连通图，否则为非强连通图。 强连通分量：有向图中的极大连通子图。
v1 v2 v1 v2
v3 G
v5
v3
v5 两个连同分量
-15-
2.图的基本术语
生成树：连通图中一个极小连通子图，含有全 部顶点，但只有足以构成树的n-1条边。
-4-
6.1 图的逻辑结构
图G1
v1 v3 v4 G1
v2
v5
V={v1,v2,v3,v4,v5} E={(v1,v2), (v1,v4), (v2,v3), (v2,v5), (v3,v4), (v3,v5)}
图G2
v1 V={v1,v2,v3,v4} E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>} v2
v3
v5
G2
-7-
2.图的基本术语
邻接、依附 如果 (vi, vj) 是图中的一条边，则称 vi 与 vj 互为邻接点。 如果 < vi, vj > 是图中的一条弧，则称 vj是vi 的邻接点。
v1 v2 v1 v2
v3 v4
G1 v5
v3 G2
v5
-8-
2.图的基本术语
若有n 个顶点， 有n(n-1)/2 条边的，称为完全无向图。 有n(n-1) 条弧的，称为完全有向图。 边或弧很少的图，称为稀疏图。 边或弧较多的图，称为稠密图。
头结点 vertex firstarc
弧的结点 adjvex nextarc
-31-
1．图的存储结构
邻接表表示无向图，每条边=两条弧
v1
0 v1 1 v2 2 v3 3 v4 1 0 0 1 2 ∧ 2 1 2 ∧ 3 ∧ 3 ∧
v2
v3 无向图G
v4
-32-
1．图的存储结构
邻接表表示网，每条边+权值
Vertex //顶点 //第一条以此顶点为弧头的弧
//第一条以此顶点tout
-38-
3. 十字链表
十字链表弧结点的C++描述 struct ArcNode{ int headvex, tailvex; //弧头，弧尾 Arcnode* hlink; //下一条相同弧头的弧 Arcnode* tlink; //下一条相同弧尾的弧 };
3. 十字链表(有向图)
0 v1 v2
∧
v1 v4 v2
v5
v3 有向图G
0 1
0 3 ∧∧
1
2
v3 ∧
v4 v5
2 1 ∧ 3 4 ∧∧ 4 0 ∧∧
2 3
2 4
∧
3
4
-37-
3. 十字链表
十字表头结点的C++描述
struct VertexNode{ char Vertex; ArcNode *firstin; ArcNode *firstout; };
-9-
2.图的基本术语
度：一个顶点的度是与它相关联的边的条数。
入度：有向图中，到达顶点的边数 出度：有向图中，顶点出发的边数
A的入度：1 出度：2
-10-
2.图的基本术语
网： 带权的图 子图：图的子集。
-11-
2.图的基本术语
路径：接续的边的端点构成的顶点序列 路径长度：路径上边或弧的数目；在网中为路 径上的边或弧的权值之和。 回路：起点和终点相同的路径

-16-
2.图的基本术语
生成森林： 在非连通图中每个连通分量，都可以得到 一棵生成树，这些连通分量的生成树构成声称 森林。

-17-
6.2 图的存储结构及实现
18
6.2 图的存储结构及实现
图的存储结构 1. 邻接矩阵 2. 邻接表 3. 十字链表 4. 邻接多重表 5. 边集数组
-19-
图的存储——邻接矩阵
0 v1 1 1 0 1 1 1 0 3 1 4 3 3 ∧ 2 1 4 2∧ 4 5∧ 2 2 弧的结点 adjvex weight nextarc