当前课程知识点：数据结构 > 第6章 图 > 6.1 概念和术语 > 讲解
同学们好
今天，我们来学习图这一章
本章分为以下六部分内容
现在，我们来看第一部分，概念和术语，第一个概念，图(Graph)
图是由两部分组成的
分别是顶点集合V
顶点就代表数据结构当中，所包含的数据元素
比如，在右边的图当中
我们给出来了5个顶点
1、2、3、4、5
图的第二部分，是由边组成的集合，边就代表顶点之间的关系
比如，在右边这个图当中
5个顶点，一共有7条边
在写每一条边的时候
我们就是用圆括号
然后，将两个顶点
放在里面，就可以了
如果顶点v和w之间有一条边
我们就写成这样
这时候，我们就称v和w互为邻接点
或者说，v和w是邻接的
第二个概念，无向图(Undirected Graph)
简称UDG
如果图当中的边没有方向
那么，从v到w这条边，也可以说成，从w到v有一条边
实际上，图当中的边没有方向
我们就说，v和w之间有一条边
这两条边是等价的
第三个概念，有向图(Directed Graph)，简称为DG
这时候的边，是有方向的
我们用尖括号，而不是圆括号
这条边代表的是，从顶点v到w
有一条边
而右边这条边，代表的是从w到v
有一条边
这二者是不等价的
有向图当中的边，也称为弧(Arc)
箭尾依附的顶点
我们称为弧尾(Tail)，箭头依附的顶点
我们称为弧头(Head)
比如，v到w有一条边，那么v，我们就称为tail
因为，这条边是从v出发的
是箭尾端
而它指向的顶点w，箭头端
我们称为弧头
如果有一条弧
我们就可以说，弧尾邻接到弧头，弧头邻接自弧尾
这些都很好理解
第四个概念，完全图
完全图是指边数达到最大的图
比如，图有n个顶点
对于无向图
它的边数
应该是n(n-1)/2，也就是C(n,2)
我们在n个顶点当中，任选2个顶点
这时候，每2个顶点之间，只有1条边
所以是C(n,2)
如果是有向图
应该是无向图对应的最大边数
再乘以2，也就是它乘以2
因为，每一对顶点
它们之间最多有2条边
这时候，边是带方向的
第五个概念，带权的图，或者网
如果图当中的每一条边，带有一个权值，这个值
表示这条边的距离、代价或者成本，这时候的图就称为带权的图，带权的图也称为网
第六个概念，子图，子图的概念非常简单
如果一个图，它的顶点
集合
和边的集合，分别是另外一个图的顶点和边的集合的子集
那么，我们称这个图为另外一个图的子图
比如，这个G'
它就是上面这个G的子图
因为，G'的3个顶点是来自于G的，G'当中的3条边也是来自于G的
第七个概念，顶点的度，顶点的度是指与顶点v邻接的边的数量
比如，右边这个图，2这个顶点
它有3条边
那么，它的度就是3，1的度就是1
如果是有向图
我们还可以分为入度和出度
有向图，顶点的入度是指，以v为弧头的边的数量，也就是指向v的
边的数量，同样是2这个顶点
因为有
2条边指向2，也就是以2为弧头
那么，2的入度
我们简称为ID(In-degree)
它的入度
就是2
与之对应的，还有一个出度
以v为弧尾的边
也就是，从v顶点出去的边的数量，我们简称为OD(Out-degree)
因为，有3条边从2顶点出去
再看路径
路径，是由若干顶点构成的顶点序列
简单路径，是指路径中不出现重复的顶点
比如2、1、3
我们从2，经过这条边
然后，再经过这条边，到达3
那么，在这个路径当中，没有出现重复的顶点
环，是指路径中首、尾顶点相同
比如，我们走2、1、3
然后，再经过<3,2>这条边
最终到达2
那么，这条路径上，第一个顶点和最后一个顶点是相同的
这时候，就构成了一个环
现在，我们来对比一下图与我们之前讲的树
树当中，结点呈一对多的关系
图当中，任何两个顶点之间都可能有关系
是多对多的关系
一对多，实际上是多对多的一种特例
所以，我们可以把树看作图的特例
但是，这二者之间，具有很明显的区别
具体表现在，树有一个特殊的元素
这个元素叫根结点
因为，树当中，根结点是没有父结点的
所以它比较特殊
图的每个元素的地位都是一样的
在图当中，没有一个所谓的、比较特殊的顶点，图当中
所有的顶点，它们的地位都是一样的
纵向看，树当中的元素，是有父子(或者层级)关系的
因为，树当中，元素与元素之间，实际上是一种隶属和包含的关系
从上往下看
横向地看，元素之间是有左、右之分的
比如，左孩子、右孩子
但是对于图
图当中的元素，没有上、下、左、右之分
意味着，我们可以任意地旋转、扭曲图当中的那些边
不管怎么旋转
这个图本身，它是不变的
比如，我们把这个
当做一个图的话
可以任意地旋转
顶点之间的边，它会变成这样
这两个图是等价的
因为，顶点之间的关系没有发生任何变化
树中任意两个元素之间，有唯一的简单路径
如果我们把左边的，当做一个树
我们知道
在树当中
任何两个顶点之间
如果不经历重复的结点
它们的路径一定是有的
而且是唯一的
但是对于图
图当中的顶点，可能有多条简单路径
也就是说，存在环，比如这个图
我们从2走到3
可以直接走这条边
也可以走这条边和这条边
说明2和3之间，有多条简单路径
这时候
实际上存在环，也可以没有路径(0条)
比如2、3、0
这些顶点
它们到1，都没有路径
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
