5-2图的逻辑结构

5-2图的逻辑结构v第五章图图的定义和基本术语图的抽象数据类型定义学什么？欧拉1707年出生在瑞士，19岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线、多面体的欧拉定理、立体解析几何的欧拉变换公式、四次方程的欧拉解法到数论中的欧拉函数、微分方程的欧拉方程、数论的欧拉常数、变分学的欧拉方程、复变函数的欧拉公式等等。欧拉对哥尼斯堡七桥问题的提出和解答开创了图论的研究。图的遍历操作5-2-1图的定义和基本术语v第五章图图的定义图：由顶点的集合和顶点之间边的集合组成，通常表示为：

数据元素G=(V，E)顶点的集合顶点之间边的集合v0v1v2v4v3空表、空栈、空队列、空树、空二叉树、空图、零图等均表示一种可能的状态，一般作为条件判断V

=

Φ的图称为空图，V

≠

Φ但E

=Φ的图称为零图。v0v1无向边：表示为(vi,vj)，顶点vi和vj之间的边没有方向v2v4v3无向图：图中任意两个顶点之间的边都是无向边v0v1有向边（弧）：表示为<vi,vj>，从vi到vj的边有方向v2v4有向图：图中任意两个顶点之间的边都是有向边图（边是否有方向）无向图有向图图的分类权：对边赋予的有意义的数值量v0v1v2v4v3带权图（网图）：边上带权的图v0v1v2v427852785635423树结构中，权通常赋予在结点图（边上是否带权）非带权图带权图图的分类v0v1v2v4v3稠密图：边数很多的图v0v1v2v4v3稀疏图：边数很少的图图（边数的多寡）稠密图稀疏图图的分类图的逻辑关系邻接、依附：无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vjv0v1v2v4v3v0的邻接点：v1、v4v2的邻接点：v1、v3v0v1v2v4邻接、依附：有向图中，对于任意两个顶点vi和顶点vj，若存在弧<vi，vj>，则称顶点vi邻接到

vj，顶点vj邻接自vi，同时称弧<vi，vj>依附于顶点vi和顶点vjv0的邻接点：v1、v4v2的邻接点：v0a1ai-1aiana2ACBDEFv0v1v2v4v3线性结构中，数据元素之间具有线性关系，逻辑关系表现为前驱-后继；树结构中，结点之间具有层次关系，逻辑关系表现为双亲-孩子图结构中，任意两个顶点之间都可能有关系，逻辑关系表现为邻接

图的逻辑关系完全图无向完全图：无向图中，任意两个顶点之间都存在边v0v1v2v4v0v1v2有向完全图：有向图中，任意两个顶点之间都存在方向相反的两条弧n个顶点的无向完全图有多少条边？n×(n-1)/2

n个顶点的有向完全图有多少条弧？n×(n-1)

度、入度和出度顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)顶点的入度：在有向图中，顶点v

的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v

的出度是指以该顶点为弧尾的弧的数目，记为OD(v)；v0v1v2v4TD(v0)=2，TD(v3)=3ID(v0)=1，OD(v0)=2

v0v1v2v4v3v0v1v2v4v0v1v2v4v3在具有n个顶点、e条边的无向图中，各顶点的度之和与边数之和有什么关系？在具有n个顶点、e条边的有向图中，各顶点的入度之和与各顶点的出度之和有什么关系？与边数之和有什么关系？度、入度和出度路径、回路v0v1v2v4v3路径：在无向图中，顶点vp和顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,…,vim=vq)，其中(vij-1,vij)∈E(1≤j≤m)顶点v0和顶点v4之间的路径：v0v4、v0v1v3v4、v0v1v2v3v4、从顶点v0到顶点v4的路径：v0v4、v0v1v4路径：在有向图中，从顶点vp到顶点vq的路径是一个顶点序列(vp=vi0,vi1,…,vim=vq)，其中<vij-1,vij>∈E(1≤j≤m)v0v1v2v4v0v1v2v4v3简单路径：序列中顶点不重复出现的路径简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。不致混淆的情况下，路径和回路都是简单的路径、回路v0v1v2v4回路（环）：第一个顶点和最后一个顶点相同的路径v0v1v2v4v3子图：若图G=(V,E)，G'=(V',E')，如果V'

V

且E'

E，则称图G'是G的子图子图v0v1v0v1v3v0v1v2v3v0v1v2v4v3v0v2v3v0v1v3v0v1v2v3v0v1v2v4v3连通顶点：在无向图中，如果顶点vi和顶点vj(i≠j)之间有路径，则称顶点vi和vj是连通的连通图连通图：在无向图中，如果任意两个顶点都是连通的，则称该无向图是连通图v0v1v2v3v6v4v5对于非连通图，实际处理中会有什么问题？从某顶点出发进行遍历，不能访问所有顶点连通分量连通分量：非连通图的极大连通子图含有极大顶点数依附于这些顶点的所有边v0v1v2v3v6v4v5v0v1v2v3连通分量1v6v4v5连通分量2连通分量是对无向图的一种划分强连通图、强连通分量强连通顶点：在有向图中，如果从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称顶点vi和vj是强连通的强连通图：在有向图中，如果任意两个顶点都是强连通的，则称该有向图是强连通图v0v1v2v3v0v1v2v3强连通分量：非强连通图的极大连通子图强连通分量1强连通分量2v0v2v4v15-2-2图的抽象数据类型定义v第五章图图的抽象数据类型定义图是一种与具体应用密切相关的数据结构，基本操作有很大差别ADTGraphDataModel

顶点的有穷非空集合和顶点之间边的集合Operation

CreateGraph：图的建立DestroyGraph：图的销毁DFTraverse：深度优先遍历图BFTraverse：广度优先遍历图endADT简单起见，只讨论图的遍历图的遍历图的遍历：从图中某一顶点出发访问所有顶点，并且每个结点仅被访问一次抽象操作，可以是对顶点的各种处理，这里简化为输出顶点的数据在图中，如何选取遍历的起始顶点？ACBDEFa1ana2ai-1ai解决方案：将图中的顶点按任意顺序排列起来，从编号最小的顶点开始v0v1v2v4v3图的遍历图的遍历：从图中某一顶点出发访问所有顶点，并且每个结点仅被访问一次从某顶点出发能访问其他所有顶点吗？解决方案：多次调用图遍历算法下面仅讨论从某顶点出发遍历图的算法v6v7v5如何避免遍历不会因回路而陷入死循环？解决方案：附设访问标志数组visited[n]v0v1v2v4v3图的遍历图的遍历：从图中某一顶点出发访问所有顶点，并且每个结点仅被访问一次a1ana2ai-1aiACBDEF采用什么次序依次访问图中所有顶点？解决方案：深度优先遍历和广度优先遍历先序：A

BD

CEF中序：DB

A

ECF后序：DB

EFC

A线性序：a1a2…

an图的深度优先遍历（1）访问顶点v（2）从v

的未被访问的邻接点中选取一个顶点w，从w

出发进行深度优先遍历（3）重复上述两步，直至访问所有和v

有路径相通的顶点从顶点v

出发进行深度优先遍历的基本思想是：是一个递归的过程算法：DFTraverse输入：顶点的编号v输出：无1.访问顶点v;修改标志visited[v]=1;2.w=顶点v的第一个邻接点；3.while(w存在)3.1if(w未被访问)从顶点w出发递归执行该算法;3.2w=顶点v的下一个邻接点;v5v0v3v2v1v4

v0

v1

v4运行实例——深入理解操作过程深度优先遍历序列：v0v1v4图的深度优先遍历v5v0v3v2v1v4

v0

v1

v2深度优先遍历序列：v0v1v4v2

v3v3运行实例——深入理解操作过程图的深度优先遍历v5v0v3v2v1v4

v0深度优先遍历序列：v0v1v4v2v3

v5v5运行实例——深入理解操作过程图的深度优先遍历从顶点v

出发进行广度优先遍历的基本思想是：⑴访问顶点v⑵依次访问v

的各个未被访问的邻接点v1,v2,…,vk⑶分别从v1,v2,…,vk出发依次访问它们未被访问的邻接点，直至访问所有与顶点v

有路径相通的顶点“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”图的广度优先遍历采用队列作为辅助存储结构运行实例——深入理解操作过程广度优先遍历序列：v0v1v2v0v1v3v2v4v0v1v2图的广度优先遍历广度优先遍历序列：v0v1v2v0v1v3v2v4v1v2v4v3v4v3运行实例——深入理解操作过程图的广度优先遍历广度优先遍历序列：v0v1v2v0v1v3v2v4v4v3v4v3运行实例——深入理解操作过程图的广度优先遍历用伪代码描述广度优先遍历的操作定义算法：BFTraverse输入：顶点的编号v输出：无1.队列Q初始化;2.访问顶点v;修改标志visited[v]=1;顶点v入队列Q;3.